By Mosharaf on October 29, 2009
D. Wetherall, “Active Network Vision and Reality: Lessons from a Capsule-Based System,” 17th Symposium on Operating Systems Principles, (December 1999). [PDF]
Summary
Active networks were a radical concept of allowing untrusted sources to execute codes on network operators’ hardware to allow faster and easier deployment of diverse distributed applications. Consequently, it also ran the risk of security violations on multiple levels, which essentially dissuaded most people – specially network operators or ISPs – to actually deploy it. Over time, the proponents of active networks had to make some compromise to increase its security and viability. This paper addresses different issues in three areas of active networks based on the authors’ experience of using ANTS, an experimental active networks implementation.
Active Networks (ANTS) Overview
Active networks consists of active nodes, which are basically programmable routers and can execute active codes carried around in capsules based on a type field. To develop a new service, the first step is to write a new set of forwarding routines implementing the desired behavior using a subset of Java (16KB max code size). The ANTS toolkit provides a core set of APIs that restricts what sort of routines can be developed. Once the code is written, it is signed and put up on a directory service. Anyone, who wants to use that service, can lookup the directory, fetch the code and register the service with the local active node. Once the local node calculates the types it is expected to find in capsules for that particular service and disseminate the code throughout the network (through caching and lazy dissemination), the service is ready to go. Capsule processing is pretty straightforward once the code is distributed: after reception, capsules are first demultiplexed using their type field to find references to code, which are then securely executed inside sandboxes, and the process goes on till capsules reach their destinations. There are additional mechanisms such as TTL, fingerprints etc. to provide security at the cost of performance.
Practicality of Active Networks
The authors argue that practical implementation and deployment of active networks hinge on the feasibility of using capsules, the openness of the framework regarding who can introduce new services, and the flexibility of the framework in respect to possible new applications.
- While capsules provide a more secure way of code dissemination (using fingerprints) and can be performance optimized (by carrying references to code instead of carrying the actual code, using caching), there is still a performance tradeoff. The authors argue that performance overhead of using capsules is minimal and can be contributed mostly to the use of Java.
- Making active networks more open attracts security risks in terms of protection against attacks as well as from global and local resource management perspective. To mitigate threats, the authors propose using (hierarchical) fingerprinting, restricted API, and strict isolation between different services’ codes. To avoid resource management threats, the authors propose partial solutions using TTL, restricted API, and eventually fall back to using trusted authority provided digital signature.
- Finally, this paper argues that the biggest gain of active networks is not some “killer app”, rather the flexibility it provides to gradually change things over time. Five different applications are reported to be implemented using active networks methodologies. The authors postulate that successful active network app must be: expressible using the available API, compact and fast, and incrementally deployable.
Comments
This paper does an excellent job in summarizing the active networks landscape as well as providing a overview of the challenges that exist toward its realization, complimented by solution hints. Active and programmable networks were one of the very few really awesome networking concepts that could do a lot in changing the research and commercial landscape. Unfortunately, at that time the available hardware were not fast nor programmable enough. In addition, there was and still is a lot of skepticism and prejudice among network operators regarding opening up their networks to untrusted sources.
However, in last couple of years, network virtualization has emerged as the solution for a secure, flexible, and extensible future networking platform that combines the programmability of active and programmable networks with concepts of overlay networks and VPNs. The main reasons behind this is, first and most importantly, programmability nowadays is cheaper and faster (with the wide-spread use of FPGAs and/or network processors) and secondly, using so-called “safe” hardware or execution environments do not take as much performance hit as they used to a decade ago.
To conclude, active network was too futuristic for its time and no one is still completely sure whether its time has come yet!
Posted in Reviews | Tagged active network, capsule, UCB CS268 F09, Wetherall |
By Mosharaf on October 29, 2009
D. Andersen. H. Balakrishnan, F. Kaashoek, R. Morris, “Resilient Overly Networks,” 18th Symposium on Operating Systems Principles, (December 2001). [PDF]
Summary
Routing scalability in BGP comes at the cost of reduced fault-tolerance and slower fault-recovery procedures. BGP hides paths due to policy concerns, damps routing updates to avoid route flapping, and has or uses little information about live traffic. As a result, sometimes it takes many minutes to sense and recover from an outage or traffic overload. This paper proposes using an overlay (RON) to actively and passively probe and monitor traffic conditions on links to provide resilient and faster paths circumventing faults in the network, given that there is physical path redundancy.
A RON creates a clique of distributed overlay nodes that are tightly connected and continuously share information between themselves (using a link state protocol) through aggressive probing and monitoring to maintain high throughput virtual links (with minimal bandwidth usage). Whenever a usual physical path experiences excessive delay or completely goes out, a RON node uses RON virtual links to route packets through other RON nodes. As a result, RON can detect route faults faster and can provide alternative paths quicker than BGP. Other goals of RON include, application defined path selection (by allowing applications to define their own metric of the “goodness” of a link) and to provide a framework for implementing expressive routing policies.
A RON client interacts with RON using an API interface, called conduit. The entry RON node conduit classifies a packet, tags it, selects a path, encapsulates it in RON header, and forwards it to the next RON node (if the usual physical path is experiencing outage or performance hit). Intermediate RON nodes keep forwarding the packet by guided by their database of policies as well as tag-action mappings until the packet reaches the exit RON node where it is decapsulated and delivered to the destination host. Forwarding component of a RON node also uses caching based on flow id for faster processing of packets. Each RON node maintains three different metrics – loss rate, latency, and TCP throughput – for each link. In addition, RON also allows creation of app-defined metrics and update mechanisms for further flexibility.
RON provides very high connectivity among its nodes and provides guarantees that there is always a path to reach from one RON node to another unless the RON graph is partitioned. The bootstrapping of RON nodes starts with a static list and dynamically updates and adds new RON nodes over time. The cost of keeping such tight coupling through periodic flooding is postulated to be negligible to the gain provided by maintaining them.
The authors evaluated the RON system on two RON networks, one with 12 nodes (RON1) and the other with 16 nodes (RON2) distributed over the Internet, each with N*(N-1) links. RON nodes were hosted two types of networks: highly reliable educaional and research network (Internet2) and commercial networks. All improvement regarding commercial paths came from commercial network by explicitly prohibiting them from using Internet2 paths. Major results are as follows:
- RON1 managed to successfully detect and recover from 100% of total outages and all periods of sustained high loss rates of 30% or more; RON2 did the same with 60% success rate. The authors did not shed much light on why RON2 couldn’t do as well as RON1; they just mentioned that in the RON2 almost always unreachable node was completely isolated due to network disruption.
- For a RON of 50 nodes, there is a 30Kbps overhead to keep its nodes informed and operational.
- RON took 18s on the average to route around an outage or a failure. An emulated 3-node RON topology was used to show that there is a 13s turn-around time for RON facing a flooding attack; however, how it would’ve performed with larger number of nodes remains open.
- RON doubled TCP throughput in 5% of the samples and reduced the loss probability by 0.05 or more in 5% of the samples (may or may not be different).
- Most importantly, they found that in most cases going through a single RON node is good enough. The whole paper revolves around this observation and RON workflow is also influenced by this.
Critique
The idea presented in this paper is interesting from a conceptual point of view and really worth reading or thinking about. However, from a practical point of view, there are several reasons why RON is not going to make it:
- First of all, RON will mess with the underlying traffic matrices of the ISPs, which might result in route instability; as RON starts flowing traffic in some routes that ISP traffic matrices do not want to use, ISPs will update their traffic matrices to counter RON and eventually there will be a cat-and-mouse chase between them.
- Second, RON will introduce extra latency and bandwidth consumption in intermediate nodes and specific links due to probing, encapsulating/decapsulating etc; the evaluation provided in the paper is limited to only two scenarios which may or may not generalize to larger cases.
- Third, RON depends on cliques between all the RON nodes and uses flooding between them; this will not scale.
- Fourth, the authors do not discuss how someone will pick nodes where to put RON nodes; it seems there should be strategic configurations that will give more leverage than others.
- In addition, there are NAT issues as pointed out by the authors.
Overall, it is a nice paper and a good conceptual exercise, but not practical for the current Internet ecosystem.
Posted in Reviews | Tagged Andersen, Balakrishnan, Kaashoek, Morris, overlay, RON, UCB CS268 F09 |
By Mosharaf on October 24, 2009
L. Gao, “On Inferring Autonomous System Relationships in the Internet,” IEEE/ACM Transactions on Networks, V. 9, N. 6, (Dec. 2001), pp. 733-745. [PDF]
Summary
Business relationships among the ASes in the Internet are kept secret, similar to any other business deals. The only thing available to outsiders are the BGP route announcements that can be accumulated and read from different vantage points. This paper presents heuristics to infer the different business relationships (customer-provider, peer-to-peer, and sibling-to-sibling) seen in the Internet with a very high accuracy (99.1% in some cases).
The inference procedure depends on rational selective export rules for announcing routes to customers, providers, peers, and siblings; e.g., peers never transits for each other, siblings always transits for each other, and customer-provider share a one-way transit from provider-to-customer direction and not vice versa. Based on this observation, the authors also define the Valley-Free property of routes, which says that
- A provider-to-customer edge can be followed by only provider-to-customer or sibling-to-sibling edges, and
- A peer-to-peer edge can be followed by only provider-to-customer or sibling-to-sibling edges.
Essentially there are some patterns of different types of routes, and the authors exploit their presence to identify different relationships. They also assume that larger ASes have higher degree and provider ASes are bigger than their customer ASes.
There are 3 phases to the proposed inference algorithm. First, all AS-pairs are coarsely classified into customer-provider and sibling relationships. Next, all AS-pairs that cannot have peering relationships are identified. Finally, peering relationships are identified from the remaining connected AS-pairs based on the heuristic that their comparative sizes remain within a factor R.
The authors used RouteViews-collected BGP routing table entries and using their algorithms found AS relationships, which were validated by secret AT&T data. By changing the approximation parameters they managed to achieve 99.1% accuracy. It should be noted that they were mostly wrong-inferring sibling relationships. They postulate that this error can happen due to several possible reasons: router configurations errors, misconfiguration of export rules, unusual AS relationships, and possible problem with the proposed heuristics, but they do not elaborate on that.
Critique
The contribution is great and important, but somehow the way its written makes a reader want not to read it. Unfortunately, it is unnecessarily long and artificially complicated. Also some of the mathematical stuff seemed not-so-necessary. When a few lines can clearly explain something, why bother using equations, mathematical symbols, theorems, lemmas just to scare people away!!! Plus, this paper should’ve been read with other BGP related papers.
Posted in Reviews | Tagged BGP, Gao, Internet, UCB CS268 F09 |
By Mosharaf on October 24, 2009
M. Faloutsos, P. Faloutsos, C. Faloutsos, “On Power-Law Relationships of the Internet Topology,” ACM SIGCOMM Conference, (September 1999). [PDF]
Summary
This paper explores the underlying regularities of the Internet structure and uses power laws to capture the properties of the AS-graph. The results presented in this paper are based on three AS-level as-complete-as-possible traces of the Internet over a 14 months period from Nov’97 to Dec’98. Within this 14 months, the Internet had a 45% growth. To include the intra-domain characteristics, the authors also used a node-level trace of the whole Internet circa ’95.
The authors observed that the then-existing metrics to capture the characteristics of the Internet were mostly minimum, maximum or average values, which failed to capture the inherent skewness of Internet-related distributions. Based on this observation, they tried and managed to fit the collected trace data to power-law curves with very high accuracy.
This paper proposes three power laws and one approximation (due to lack of data points, they couldn’t strongly suggest it to be a law!), and define four exponents/power-law curves:
- Rank exponent, R: The out-degree of a node is proportional to its rank to the power of a constant R. From the traces, the authors found that the rank exponent R significantly varies between different types of graphs (e.g., AS-level and node-level) to be able identify them.
- Out-degree exponent, O: The frequency of an out-degree is proportional to the out-degree to the power of a constant O. This law suggests that there is an underlying out-degree distribution of Internet-like graphs, and the authors propose the use of this metric to rule out synthetic graphs that does not have similar out-degree exponents.
- Hop-plot exponent, H: The total number of pairs of nodes within a certain number of hops of a node is proportional to the number of hops to the power of H. It can also be used to separate between different types of graphs.
- Eigen exponent: The eigenvalues of a graph are proportional to the corresponding order to the power of a constant E. The authors found that this exponent remained sort of constant over time to suggest that it is size-invariant; but they found that it can also be used to identify different classes of graphs.
Because the power laws show consistent correlation among traces, they authors propose them to be used to assess the realism of synthetic graphs, to help analyze the average-case behavior of network protocols, and to concisely define Internet-like graphs. The paper also provides several formulas to calculate the number of edges, nodes, density of nodes of such graphs.
Thoughts
The authors have done an excellent job to draw conclusions from a vast amount of data to provide structure to the Internet graph. It was really interesting to see that there is order somewhere under the seemingly chaotic world of computer networks and their interconnections. In fact, as the authors point out, power-laws can be observed in many other types of social, scientific, and biological networks. I wonder why?
Posted in Reviews | Tagged Faloutsos, Internet, power-law, UCB CS268 F09 |
By Mosharaf on October 19, 2009
P. Bahl, R. Chandra, T. Moscibroda, R. Murty, M. Welsh, “White Space Networking with Wi-Fi like Connectivity”, ACM SIGCOMM Conference, (August 2009). [PDF]
Summary
With the FCC opening up the unused portions of the UHF spectrum, also known as the “white spaces”, researchers have set upon implementing WiFi over the newly acquired territory. Such networking is different from existing WiFi technologies along three axes: spatial variation, temporal variation, and fragmentation of the UHF spectrum. This paper presents WhiteFi, the first WiFi over white spaces that implements adaptive spectrum assignment algorithm to tackle spatial variation and fragmentation, and proposes a low overhead protocol to handle temporal variation. This paper is concerned with the “only one Access Point (AP) with multiple clients” scenario, and unlike the existing solutions, WhiteFi works on variable channel widths and uses SIFT (Signal Interpretation before Fourier Transform) for faster and better detection of data transmissions.
The Three Challenges
As mentioned earlier, UHF white spaces are different from ISM bands used in the existing WiFi in three ways:
- Spatial variation: The set of channels occupied by TV transmitters and the number of stations operating in an area vary from one place to another with significant variance. As a result, an AP must select a channel after proper consulting with all its clients based on their location.
- Spectrum fragmentation: Since UHF bands already have incumbent TV channels, they are fragmented irrespective of urban and rural areas. As a result, radios working in white spaces must use variable channel widths, which makes channel assignment and AP discovery harder than that in ISM bands.
- Temporal variation: Channel occupancy by incumbents also vary based on time. Since the FCC does not allow messing up incumbents, the AP and its clients must move away as soon as they detect a microphone (working on UHF) starts working.
Proposed Solution
The proposed solution consists of an adaptive allocation/assignment algorithm, a lightweight protocol, a specialized hardware to glue them together.
- Hardware: The authors developed KNOWS, a specialized hardware platform with a PC, a scanner, and a UHF translator, to support WhiteFi. The PC controls the others, the translator translates backs and forth from WiFi, and the scanner samples UHF spectrum to find white spaces.
- Spectrum assignment: The AP must pick a channel that can be used by all the clients. So once it finds one, it keeps checking periodically to find a better one (voluntary) or to move away from a conflicting channel (involuntary). For finding a channel, the authors propose a channel probing mechanism based on a new metric that can predict channel availability with high accuracy. The AP evaluates all possible channels and picks the one that maximizes the metric and works for all its clients. Then the AP broadcasts the new channel for its clients to switch to. The information between the AP and its clients are passed using a bitmap where each bit says whether a channel is or can be used or not. To avoid moving back and forth between channels without much gain, the authors also used hysteresis process.
- AP discovery: Since the AP can use more than one channel, finding an AP is computationally harder for its clients in WhiteFi than that in WiFi. The authors introduced a new signal analysis technique SIFT, which basically determines packet widths based on signal amplitudes with small number of false positives. Two different versions of SIFT are proposed:
- L-SIFT linearly scans all the channels, and
- J-SIFT scans in a top-down manner from higher MHz channels to lower ones in a staggered manner, and once it detects the presence of a WhiteFi transmitter, it identifies the center frequency.
- Handling disconnections: To cope with sudden appearance of an incumbent transmitter, the authors propose to keep a backup channel where everyone periodically pings about their status. To backup the backup, an arbitrary available channel is used as a secondary backup.
Evaluation
The authors performed most of their evaluation using simulation, because they could not test on real white spaces, citing FCC regulations! And there are no surprising finding either: SIFT is mostly accurate across different channels, J-SIFT does really well in discovering APs, disconnection handling works, and the proposed metric closely follows availability to make the proposed assignment algorithms perform really well in real time.
Thoughts
The problem is really fresh and exciting, as is the solution, except for the gory signal analysis part (fortunately or unfortunately that’s a big contribution). Its great to see the ‘first’ paper in a completely new area! One can predict that this paper will be really big (at least in terms of citation) in the long run if all the hype about white spaces hold up.
There are a few comments. Throughout the evaluation section, the authors keep talking about the optimal omni-potent algorithm that works best for any channel. How did they come up with that, and how it influenced their design? While evaluation the impact of spatial variation, the authors used some minimum and maximum probabilistic values. Where and how did they come up with those values? If there is any other studies of white spaces, they don’t mention it.
Unlike 10MHz and 20MHz packets, 5MHz packets have little or no variation with respect to any parameter. What is the reason? Are they parameter insensitive or the parameters are not fine tuned enough to catch their sensitivity. It would have been better to see some explanation.
Posted in Reviews | Tagged Bahl, Chandra, Moscibroda, Murty, UCB CS268 F09, Welsh, white space networking, WhiteFi, WiFi |
By Mosharaf on October 19, 2009
A. Balasubramanian, R. Mahajan, A. Venkataramani, B. N. Levine, J. Zahorjan, “Interactive WiFi Connectivity For Moving Vehicles”, ACM SIGCOMM Conference, (August 2008). [PDF]
Summary
Current WiFi handoff methods, where a client remains connected to a single basestation (BS), lead to frequent disruptions in connectivity in highly mobile vehicular networks. This paper proposes ViFi, a protocol that opportunistically exploits BS diversity to minimize disruptions and can support interactive applications (e.g., Web browsing, VoIP). ViFi opportunistically connects a mobile client device to multiple BSes, and coordinates between those BSes using a distributed and lightweight probabilistic algorithm, to obviate hard handoffs.
Observations
The authors performed experiments on two testbeds (VanLan and DieselNet) with 6 handoff protocols (practical as well as optimal) to come up with the following conclusions that led to the ViFi design:
- With a reasonable density BS deployment, a vehicle is often in range of multiple BSes. Existing handoff mechanisms do not take advantage of this property.
- Packet loss, in each vehicle-BS connection, is independent and bursty. A BS that failed to receive something is more likely to fail in close temporal proximity than another BS which also overheard the same transmission.
ViFi Design
In its core, ViFi allows overhearing BSes to carry on a transmission towards the destination even though the intended BS failed to receive or acknowledge it. The main challenge here is to coordinate between BSes with minimal overhead and latency and with little to no disruption as BS set changes. To this end, ViFi designates one of the BS as the anchor and the rest as auxiliary BSes within the range of the sender based on some metric. Through periodic Beacons from the vehicle, BSes get to know each other (who is anchor etc.) as well as the sender vehicle. The operations of ViFi is symmetric in both directions (src and dst) and given in the following:
- src transmits the packet P.
- If dst receives P, it broadcasts an ACK.
- If an auxiliary BS hears P but not the ACK within a time period, it probabilistically relays P. (Note: Relaying takes place in the inter-BS backplane)
- If dst receives relayed P and yet to broadcast an ACK, it does so now.
- src retransmits when retransmission timer goes out. (Note: Retransmission timer is adaptively set based on how fast a vehicle receive ACKs)
Probability of relaying or not relaying is computed locally in each BS based on the accumulated information from overhearing and Beacons. The invariant in this probability calculation used by the authors is that the expected number of packets relayed across all auxiliary BSes is equal to 1 (which also makes sure that a packets is relayed at most once by a BS). There can be false positives and false negatives due to the independent calculation methods, but the authors postulate that that will be very low.
ViFi also supports salvaging, i.e., whenever a vehicle moves out of the range of an anchor, the new anchor contacts the previous anchor to take care of the un-forwarded packets to the vehicle. This ensures that TCP won’t assume congestion, when there is none.
Evaluation Results
- Link layer performance of ViFi closely approximates the ideal solution in the testbeds.
- Both Web and VoIP traffic enjoys better goodput and session connectivity using ViFi. Percentage gain varies based on testbed though. Salvaging gives 10% boost, but its not very useful for VoIP.
- Medium usage/efficiency is usage is roughly the same for the increased performance.
- Coordination mechanism has low false positives than naive approaches and higher, still small, false negatives.
Critique
The whole design and concept is intriguing; but they are all based on two controlled testbeds with dense BSes and only one vehicle. What will be the overhead on the backplane or the number of signal collisions, if there are many connections going on at the same time? To give credit to the authors, previous work on opportunistic algorithms also avoided this aspect as much as possible, even in stationary scenarios.
The authors point out the possible problems with a high number of equidistant auxiliary BSes, that might increase overhead and make selection process harder (now they select all, but selecting some out of many BSes as auxiliary will intrinsically introduce more errors). Deployment of enough BSes to make ViFi perform better than others is another problem. Such dense deployment is easier in urban areas, but will be much harder elsewhere.
Some parts of the work presented and the problem itself had been present in the context of cellular networks and addressed there to some extent. The authors sporadically mention that too, but never actually go deep into discussion or comparison. A better comparison, even if qualitative, would have been nice in the relative work section.
Posted in Reviews | Tagged Balasubramanian, Levine, Mahajan, UCB CS268 F09, vehicular, Venkataramani, ViFi, WiFi, wireless, Zahorjan |
By Mosharaf on October 15, 2009
S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, “XORs in the Air: Practical Wireless Network Coding,” ACM SIGCOMM Conference, (September 2006). [PDF]
Summary
This paper present COPE, a new forwarding architecture for wireless mesh networks that significantly improves the overall throughput by exploiting the shared nature of wireless medium using network coding. All the nodes communicate using broadcast in COPE. Each node stores overheard packets from its neighbors in a buffer pool for a short amount of time and also tells its neighbors what packets it has in its own pool using a bitmap. When a node transmits any packet, it uses the knowledge about its neighbor (if it knows) or intelligently guesses to XOR multiple packets together and transmits them as a single packet. Receiving node in the next hop, decodes the packet by re-XORing it with the packets in its pool. Packets are encoded only if they can be extracted in the next hop.
The authors explain through examples and prove theorems to show Coding gain and Coding+MAC gain (gain due to resource allocation less skewed toward hub-type nodes) of using COPE over traditional options. They have three results:
- In the absence of opportunistic listening, COPE’s maximum coding gain is 2, and it is achievable;
- In the absence of opportunistic listening, COPE’s maximum Coding+MAC gain is 2, and it is achievable; and
- In the presence of opportunistic listening, COPE’s maximum coding gain is unbounded.
There are several implementation related gotchas:
- Packets are never delayed to avoid unnecessary queue development.
- COPE prefers XORing packets of same length and keeps multiple virtual queues per neighbor based one for each packet size!
- It also tries to avoid TCP packet reordering and use hop-by-hop ACKs and retransmissions.
- While guessing whether or not to XOR one more packet to the mix, COPE calculates the probability based on some metric (ETX/ETT), and if the probability goes below a threshold (0.8 in the paper), it does not XOR that packet.
- Moreover, COPE implements a pseudo-broadcast consisting of multiple unicasts to work-around default broadcasts poor reliability and lack of backoff.
COPE was evaluated on a 20 node 802.11a wireless testbed with a bit rate of 6 Mbps. Main results are:
- For toy topologies, TCP flows get lower (no MAC gain) boost than UDP flows.
- For a congested wireless medium, UDP flows gets 3-4x boost in overall throughput and approaches Coding+MAC gain. But with increasing load, UDP decreases and seems to have been stabilizing around 2x range.
- But TCP suffers from hidden-terminal induced collision related backoff and cannot gain much using COPE. Without any hidden terminal, the maximum goodput shows 38% improvement.
- Almost half the coded packets are XOR of only 2 packets and trailing off at a maximum of 5 packets.
- Finally, if COPE based access network is connected to the Internet through a gateway, throughput gain varies from 5% to 70% based on uplink to downlink ratio.
Comments
This is an overall excellent paper that combines theory with practice and backs up the claims with wide range of experimental evaluation. The paper is also very well written and easy to follow. However, there are several issues that could use more explanation. COPE requires as many virtual queues as there are packet sizes (which they say essentially to be 2 for the Internet) for each neighbor within its hearing distance, and will have to look through all of them to find optimal XOR strategy. The paper does not provide any evaluation of how big they grow or how long its takes to optimally pick an XORing strategy.
The authors say that the pseudo-broadcast mechanism will make sure that every node gets more than once chance to overhear. However, they avoid to mention and evaluate that this might also result in a higher number of collisions and link layer retransmits.
Posted in Reviews | Tagged Crowcroft, Hu, Katabi, Katti, Medard, mesh, network coding, Rahul, routing, UCB CS268 F09, wireless |
By Mosharaf on October 14, 2009
S. Biswas, R. Morris, “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” ACM SIGCOMM Conference, (August 2005). [PDF]
Summary
ExOR is an integrated routing and MAC technique that opportunistically exploits the broadcast characteristics of the wireless environment. Unlike the traditional routing protocols, where the best sequence of nodes from a source to a destination is decided before packets are routed along that path, ExOR defers the next hop decision until it knows all the nodes that received a packet and allows the closest node to the destination to be the next hop and retransmit that packet toward destination. As a result, ExOR can try multiple long but lossy links concurrently, resulting in high expected progress per transmission.
Packets are sent in batches. The source node includes in each packet a list of candidate forwarders prioritized by closeness to destination (ETX with only forward delivery probability is used in this paper) and a batch map that the sender’s best guess of the highest priority node to have received each packet. Receiving nodes buffer packets until the end of batch transmission. Then based on priority, each receiver broadcasts its received packets with updated batch maps. If a packet is somehow overheard by a node farther away than expected, it replaces the original guess with its own id as the highest priority receiver in the batch map. Essentially, each node end up with more or less the same batch map using this gossip-like protocol. Every forwarder transmits only those packets that are not ACKed by higher priority nodes. This cycle continues until 90% packets have reached the destination; the rest are transmitted using traditional routing protocol.
Evaluation of ExOR was performed on a 32 node testbed, and the authors claim that ExOR performed better than traditional routing for almost all node pairs with an average 2x end-to-end throughput gain. ExOR gain is more prominent in longer lower throughput routes (due to more probability of exploiting overhearing) than shorter higher throughput routes, but it manages to lead traditional routing throughout the spectrum. The authors believe that the best batch size is somewhere between 10 to 100 packets, but do not provide any specific value for magic formula.
Two of assumptions behind ExOR are that reception at different nodes is independent, and that there is a gradual falloff in delivery probability with distance. Through simulation, the authors show that with longer routes dependent loss more and more lags independent loss; however, maximum lag found in the simulation is 20%, which made the authors postulate that independent loss is not really a requirement but can be exploited if present.
Critique
The concept is simple and straightforward, but the paper somehow managed to make it more complex than it really is. Figure 6 as well as its description in Section 3.8 only confused everything more. And those massive plots with minute information only made things worse (LaTeX put them in an unordered fashion, which made reading the paper all the more annoying).The evaluation also did not reveal much except for showing that ExOR does increase throughput in their testbed. In addition, it also interacts badly with TCP and resorts to split connections breaking the end-to-end TCP semantics and possibly introducing overhead.
Posted in Reviews | Tagged Biswas, ETX, ExOR, Morris, multi-hop, opportunistic, routing, UCB CS268 F09, wireless |
By Mosharaf on October 8, 2009
J. Broch, D. Maltz, D. Johnson, Y-C Hu, J. Jetcheva, “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols,” ACM Mobicom Conference, (October 1998). [PDF]
Summary
This paper presents packet level simulation results of four multi-hop wireless ad hoc network routing protocols: DSDV, TORA, DSR, and AODV, in networks of 50 mobile nodes. The authors have extended the ns-2 network simulator to accurately model the MAC and the physical layer behavior of IEEE 802.11 standard, added a realistic wireless transmission channel model, and included node mobility to the simulator.
Protocols Considered
Distance-Sequenced Distance Vector (DSDV) is a hop-by-hop distance vector routing protocol, where each node maintains a routing table listing the “next hop” for each reachable distance and periodically broadcast the table. Sequence number of an entry determines its freshness – the higher the better. Better metric value is used to break a tie. In addition to periodical updates, a route update is triggered whenever a new sequence number is heard. Based on the waiting time to broadcast a triggered update there can be two variations of DSDV. This paper uses DSDV-SQ, where they instantly trigger an update.
Temporally-Ordered Routing Algorithm (TORA) discovers routes on-demand using a distributed link-reversal algorithm. Whenever a node needs to route to a particular destination, it broadcasts a QUERY packet. The recipient of the QUERY packet broadcasts an UPDATE packet. As the UPDATE packet propagates through the network, a directed path is created to the destination. TORA is implemented on top of IMEP (Internet MANET Encapsulation Protocol) for reliable, in-order delivery of control packets. Periodical BEACON and HELLO messages detect link status.
Dynamic Source Routing (DSR) is another on-demand routing protocol that uses source routing rather than hop-by-hop routing; each packet carries a complete, ordered list of nodes that it must traverse to reach the destination. The DSR protocol has two mechanisms: Route Discovery finds the list of nodes to reach a destination after the sender broadcasts a ROUTE-REQUEST packet (route caching is used to improve performance). Route Maintenance detects whether a source route has been invalidated due to topology changes.
Ad Hoc On-Demand Distance Vector (AODV) combines the basic on-demand mechanism of Route Discovery and Route Maintenance of DSR with DSDV hop-by-hop routing, sequence numbers, and periodic beacons of DSDV. Instead of using source routing, hop-by-hop states are created when a Route Discovery request is replied.
All in all, these four protocols differ in several design choices: on-demand vs constant route computation, hop-by-hop vs source routing, use of sequence numbers vs relying on ‘heights’ vs node list in source routing etc.
Evaluation
This paper considers three metrics to compare the protocols: packet delivery ratio (PDR), routing overhead, and path optimality (hop count). Major findings/confirmations are:
- With increasing mobility, PDR of DSDV-SQ drops significantly than the rest of the algorithms. For lower mobility, all the algorithms have closer PDRs.
- For DSR and AODV-LL, PDR is independent of offered traffic load. DSDV-SQ fails to converge after a certain threshold, most the losses caused by its storing only one route which turns out to be broken. TORA, on the other hand, performs well for lower loads but fails miserably once load goes up due to its higher overhead.
- DSDV-SQ maintains a constant routing overhead irrespective of mobility and load. DSR and AODV-LL show similar reaction to mobility and load, but AODV-LL has more overhead due to its lack of optimizations used in DSR and for not using source routing. TORA has high overhead even for smaller load and completely loses applicability with increasing load as IMEP faces congestion collapse.
- Lower speed of node movement does not affect the overhead for DSDV-SQ (it has to perform periodical broadcasting anyway). But in general, lower speed mellows the effect of mobility on all the protocols in terms of PDR and overhead.
Comments
This paper presents a good summary of different protocols for multi hop routing in wireless networks and presents a reasonable evaluation over a very large parameter space. Even though more sophisticated than its contemporary models, several of the important factors in modeling of wireless links are ignored in this paper. And using hop-count as a metric for path optimality is not the best choice. Overall, this was a good paper in its time but should have been replaced by now with experimental evaluation or more accurate simulation models.
Posted in Reviews | Tagged ad hoc, AODV, Broch, DSDV, DSR, Hu, Jetcheva, Johnson, Maltz, multi-hop, protocols, TORA, UCB CS268 F09, wireless |
By Mosharaf on October 8, 2009
D. De Couto, D. Aguayo, J. Bicket, R. Morris, “A High Throughput Path Metric for Multi-Hop Wireless Routing,” ACM Mobicom Conference, (September 2003). [PDF]
Summary
This paper presents ETX (expected transmission count), a new metric to find high-throughput paths on multi-hop wireless networks (802.11b), which minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to its ultimate destination. Contrary to the minimum hop-count (MHC) metric, ETX incorporates link loss ratios, asymmetry in loss ratios between the two directions, and interference among successive links. Measurements in a 29-node testbed show that ETX improves average throughput of multi-hop routes by up to a factor of two over MHC.
The authors motivate ETX design by pointing out several flaws in MHC:
- MHC-based protocols implicitly assume that links either work (if probe packets go through) or don’t work at all. However, in wireless networks, links with intermediate loss ratios can exist that are good enough to transmit control packets (probe packets) but cannot transmit data packets introducing errors. Also many links have asymmetric delivery ratios, which cannot be captured using MHC.
- By minimizing the hop-count, MHC protocols maximize distance traveled by each hop, which decreases signal strength and increases loss ratio. In addition, in a dense network many routes can exist with same MHC and arbitrarily selecting one route can significantly effect total transmission time.
- Experimental results show that MHC performs well whenever the shortest route is also the fastest route, especially when there is a one-hop link with low loss ratio. With increasing number of hops, MHC throughput decreases almost linearly.
Somewhat better approaches than MHC, product of per-link delivery ratios (PPLDR), bottleneck-loss-ratio (BLR), end-to-end delay (E2ED), also fail to account the wide range of loss ratios, asymmetry in loss ratios, and interference between successive hops. PPLDR and BLR fails to account for inter-hop interference (e.g., perfect two-hop link is better than a one-hop link with 1% loss ratio) and E2ED introduces oscillation due to its high sensitivity to network load (as queues go larger and smaller, E2ED can vary widely).
ETX calculates forward and reverse delivery ratios of a link and uses the inverse of the product of the two to estimate expected number of transmissions. The ETX of a route is calculated by summing indivual ETXes of each link. As a result, ETX accounts for asymmetry (by using forward and reverse loss ratios), interference (by summing up ETXes along the path), and link loss ratios (by definition). Since delivery ratios are directly related to throughput, ETX can better predict throughput than MHC and other approaches.
The rest of paper provides gory details of the modifications they had to make to the DSDV and DSR protocols to make them work with ETX. Apparently, no one, not even the people who created DSDV and DSR, are 100% sure about different implementation details; the authors did whatever they saw fit to make them work.
In the evaluation section, the authors match up ETX-modified DSDV and DSR against their MHC counterparts and convincingly find ETX winning every rounds!
Critique
ETX is much better than MHC, but it was sort of obvious from their motivation briefing. A better evaluation could have been against PPLDR or E2ED. Btw, the same group came up with a even better metric ETT (estimated transmission time) in their future work.
ETX performed bad for large packet sizes. The authors argued that using small probe packets introduced and over-estimation of link qualities, which was visible for larger packet sizes. Why they did not consider large prob packets (possibly of same size as the data packets) and evaluate performance in that is not clear.
Somewhere in the paper it is mentioned that ETX tends to reduce spectrum use, which was not clear.
Posted in Reviews | Tagged Aguayo, Bicket, De Couto, DSDV, DSR, ETX, Morris, multi-hop, UCB CS268 F09, wireless |