Performance Comparison of Multi-hop Wireless Ad-hoc Network Routing Protocols

Wireless mobile users can communicate by forming an ad-hoc network where each mobile node is both a host and a router, forwarding packets to other nodes that may not be within range for direct wireless transmission. This type of network requires the nodes involved to dynamically establish routing amongst themselves.  There have been protocols proposed to deal with multi-hop routing in these ad-hoc networks; this paper aims to directly compare/evaluate these attempts (DSDV, TORA, DSR, and AODV) to demonstrate their actual performance.

The authors describe their TCP simulator that:

• Uses a signal radio wave attenuation model that accounts for both short and long distances
• Uses Distributed Coordination Function (DCF) to accurately model contention on the wireless medium, tries to reduce probability of collision caused by hidden terminals
• (and more)

The authors also made improvements to the protocols they evaluated:

• Packets were sent with jitter to prevent synchronization
• Routing packets were sent at head of transmit queue, while ARP and data packets were inserted at en
• Link breakage detection feedback was used to indicate when a packet couldn’t be forwarded to next hop (not used in DSDV because made performance worse)

In DSDV, each route has a sequence number and one route is better than another if it has a greater sequence number, with a lower metric as a tie-breaker. Nodes advertise increasing even sequence numbers for themselves, so that a node can advertise an odd number for a destination that it notices has gone down–signifying an infinite metric to be used in the routing choice. In TORA, route optimality is less important than minimizing overhead for establishing routes and doing it quickly. A node computes a route to a destination by broadcasting a “query” packet that propagates throughout the network until finding the destination or a node with a route to it. The recipient broadcasts an “update” packet that lists its height to the destination; each node that hears this broadcast adjusts its height to be greater than the broadcasted height. TORA assumes that neighboring nodes have a consistent picture of the network: a link down is known by both nodes involved. DSR uses source routing: each packet carries with it the ordered list of nodes to visit, meaning that intermediate nodes do not need up-to-date routing information and thereby eliminating the need for periodic route advertisements. The route is determined via broadcast in the “route discovery”, and broken routes are taken care of in the “route maintenance” phase. AODV is a combination of DSR and DSDV, using the on-demand route discovery and maintenance and hop-by-hop routing with sequence numbers. A route request for a destination is broadcast to neighbors as well as the last sequence number for that destination.

The evaluation aimed to measure each of these protocols’ reaction to changing topology while still routing packets. In particular, the metrics used were: (1) packet delivery ratio, (2) routing overhead, and (3) path optimality. A smattering of results: DSR dominates with the least overhead, DSR and AODV-LL perform best in the packet delivery ratio (over 95%), DSR and DSDV-SQ are the best at using the optimal routes.

This paper was very thorough in describing the protocols used, the implementation details made, the simulation details, and the evaluation results. I’ll go ahead and say there was probably too much detail to really walk away with a sound sense of the conclusions, and I think this summary even shows how I got a little bogged down in the details. Still, the description of the simulator was a nice review of some of the topics we’ve been discussion: hidden terminals, CTS/RTS, node buffer queue management policies like drop-tail.

A High-Throughput Path Metric for Multi-Hop Wireless Routing

For routing in multi-hop wireless routing, the minimum hop-count metric chooses amongst paths of the same minimum length, which ignores potential differences in throughput amongst those paths. Minimum hop-count assumes a link either works well or doesn’t work at all: totally not true in the wireless world. The authors instead use the expected transmission count metric (ETX) that minimizes the number of packet transmissions by considering link loss, link loss asymmetry, and interference. This work is for use in the Roofnet multi-hop network we read about last week.

Analyzed performance of of minimum hop-count in wireless test bed of twenty-nine nodes on five floors of an office building. The size of the each data packet with its ACK computes to a maximum throughput of 451 unicast packets per second over a loss-free link. There was potential interference in the form of other 802.11b access points on various channels. The best path between a pair of nodes was found by selecting from ten potential paths, determined with an off-line routing algorithm, the one with the highest throughput. The evaluation shows that DSDV using the minimum-hop metric chooses paths with less throughput than the best path. This happens because links with high loss ratios are choosen, causing more retransmissions that consume bandwidth. Another observation is that the multi-hop metric chooses randomly from same-length paths, which is unlikely to achieve the best choice as the number of paths increase. Looking at link loss ratios, the authors note a lot of link asymmetry, a wide range of ratios amongst paths, and a lot of intermediate ratios that would lose data.

The ETX was designed to account for the above problems with link loss, as well as interference between hops in a path. The ETX for a route is the sum of ETX for each link in that route, calculated using the delivery ratios in each direction of the link. The forward delivery ratio is the probability that a data packet successfully arrives at its recipient; the backward delivery ratio is the probability for the corresponding ACK. 

ETX was implemented in DSDV with four changes:

• The weighting time before advertising a route should start when the first route of each sequence number is heard.
• Link-level feedback is not used to detect broken links.
• Triggered updates do not cause a full dump.
• A route isn’t used until it can be advertised, in order to avoid choosing bad links.

ETX does not consider congestion in its routing choices, a design choice discussed in papers we read last week about the separation between the transport layer and the link layer in wireless. A fair choice, but I wonder how much varying amounts of congestion affects their metric’s choice of the best path. ETX also doesn’t account for mobility. I like how they began with an in-depth comparison to the alternate method of minimum hop-count to highlight the differences using ETX.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes an unplanned deployment of a wireless mesh network, Roofnet: unplanned placement of thirty-seven nodes, omni-directional antennae, multi-hop routing, and optimization for throughput over route repair. With this setup, the authors look at the effect of node density on connectivity and throughput, link characteristics chosen by the protocol, etc. This method is in contrast to the traditional way to construct a community network is through carefully choose node locations with directional antennas, as well as a “hot-spot” construction of individual nodes. The authors’ design choice makes for easier deployment, but runs risk of too much performance reduction. 

Roofnet nodes are located in buildings throughout Cambridge, MA, hosted by individual users. Since these users need to be able to simply connect the node to their computer via Ethernet, the node is self-configuring by assigning addresses, finding gateways, and determining the best multi-hop routes. The node keeps track of which gateway has the best route for each open TCP connections; a new best route can be used for new connections. Roofnet has a routing protocol called Srcr that aims to find the best throughput route between nodes, using various techniques like forwarding link metric information in the packet itself. Routes are choosen with an estimated transmission time (ETT) metric: total time it would take to send a packet on a route considering each link’s highest throughput rate and the likelihood of achieving it.

There were some interesting points in the evaluation. Despite having omni-directional antennas making lots of links, Srcr uses a small number of the short links. Their multi-hop feature suffered from inter-hop collisions and thus didn’t perform as well as they predicted. I liked the discussion of Roofnet successfully using the mesh architecture by routing to “useful” nodes with many neighbors. Roofnet, however, is very vulnerable to loss of valuable links: when removing the best two nodes, throughput decreases by 43%.

Modeling Wireless Links for Transport Protocols

This paper describes how to appropriately design wireless link simulations in order to evaluate the performance of transport protocols and the interplay between wireless links and the transport layer. The authors look at unicast transport with models of the three classes of wireless links: wireless LANs, wide-area cellular links, and satellite links. Like last time’s readings, they note that packet loss in wireless does not necessarily indicate a congestion problem, a mismatched situation in TCP. Furthermore, TCP penalizes cellular and satellite links for their high latency that results in high RTT. There has been a lot of work on whether the same protocol stack should be used for fixed and wireless links. If so, interoperability is an advantage; but wireless links should still attempt to minimize effects on the transport protocol. Modeling should be as simple as possible, not doing such extravagances as link-level retransmissions, but rather stick to end-to-end protocols.

The authors further describe the differing characteristics of the three classes of wireless links. Cellular has lower bandwidth and high latency, and are protected by forward-error-correction and link-layer retransmissions. Wireless LANs have a higher bandwidth and low latency. Satellite has high bandwidth and latency. The wireless topology and traffic are also important aspects of the modeling process. For example, conclusions from one-way bulk TCP transfers may be misleading. When modeling, it’s important to capture the important link characteristics: error loss and corruption, delay variation, packet reordering, on-demand resource allocation, and bandwidth variation.

There’s been problems with the ways models have been designed. Unrealistic models like using older versions of TCP or making tight assumptions about inter-packet delays to distinguish corruption from congestion. A model could be realistic, but still poorly designed if it only explores a small amount of the parameter space, like assuming the wireless link is the only bottleneck. A related problem is focusing too much on the nuances real-world flaws, or designing an irreproducible model. The authors describe how to better model the aforementioned characteristics and remarking on their effects on the transport protocol.

I love that this paper addresses the question I always have about the reality or practicality of evaluation results we’ve seen in papers so far. It reminds me of a databases paper that did a thorough comparison of concurrency control methods in myriad situations, motivated by a lot of research papers that reported seemingly contradictory results. Both these papers highlight the importance of important simulations to correctly capture tradeoffs in different situations.

A Comparison of Mechanisms for Improving TCP Performance Over Wireless Links

This paper compares three schemes for improving performance of TCP in wireless and other lossy networks: end-to-end protocols, link-layer protocols, and split-connection protocols. Reliable transport protocols assume that packet loss and delay are caused by congestion, which is not necessarily true in this space. Still, when assuming congestion, congestion control techniques kick in that result in reduced throughput and performance. To remedy this, approaches include: hiding non-congestion related losses from the TCP sender to solve the problem locally, or make the TCP sender aware that the loss was not due to congestion. The latter could be accomplished via selective acknowledgments (SACKs) and explicit loss notification (ELN). SACKs could take the form of RFC, where acks contain information about three non-contiguous blocks of data, or SMART, where acks contain information the sequence of packets so far. 

The authors compare a myriad combination of features in the three schemes they compare. The link-layer SMART TCP aware protocol performs the best overall. A spattering of other evaluation results I found interesting: link-layer protocol without TCP-AWARE cause duplicate acks that ultimately invoke congestion control, adding ELN and SACKs to end-to-end protocols yielded good performance, and the performance of split-connection is worse than a TCP aware link-layer protocol–further demonstrating that splitting the end-to-end connection at the base station doesn’t improve performance.

This paper was great for exploring the details of different approaches to preventing the unnecessary activation of congestion control in wireless links. They clearly presented the discussion of a lot of different models. In their extensive experimentation, the authors note that it was not their intent to model a real wireless channel, but rather to exercise the dynamics of each protocol. I’m wondering if this is the preferred method of simulation, or does the academic community prefer a mix of that and real-life situations. Or, perhaps, these models subsume or predict those that would occur in the real world.

MACAW: A Media Access Protocol for Wireless LANs

Due to the growth in mobile computing devices utilizing the network, need new network technologies to provide connectivity. Since wireless LANs are most heavily utilized for these devices, also need to think about how to control access to this shared media. The authors aim to develop a media access protocol for this space and explore performance and design issues in wireless media access protocols; they test in a simulation. They propose the MACAW algorithm, which includes changes to Multiple Access, Collision Avoidance (MACA). They observe several things about contention and congestion: (1) relevant contention lies at the receiver, (2) congestion is location dependent, (3) learning about congestion levels is necessary to allocate fair media access, and (4) the media access propagate information about contention.

The authors describe their radio network at PARC and its characteristics. A “collision” occurs when a receiver cannot differentiate between two signals from two transmitting stations. “Capture” occurs when the receiver can only receive the signal from the closer of two transmitters in range. “Interference” occurs when the receiver cannot receive a signal from a transmitter due to the interference from an out-of-range transmitter. They note that they use the simple model of ignoring capture and interference in their algorithms, but not their simulations. For single channel control, it’s better to use multiple access over the token approach because the former is more robust and mobility would cause too much handing-off in the latter. CSMA is not appropriate for their multiple access algorithm because it detects collisions in the vicinity of the transmitter and not the receiver. MACA is better because it uses signaling packets between stations: request-to-send (RTS) and clear-to-send (CLS); stations overhearing an RTS will defer transmission. The authors enhance MACA in MACAW with a smarter backoff algorithm to ensure fairness using additional information stored in the packet header. They also consider multiple stream models, choosing to allocate bandwidth to streams rather than stations. Other changes include: adding an ACK to the RTS-CTS-DATA exchange since recovery at link-layer is faster, adding a Data-sending (DS) packet to clarify the lost CTS problem, and a Request-for-request-to-send (RRTS) packet to protect against a station being unable to respond to an RTS because of its own deferral.

This paper was good at demonstrating (with examples!) some of the difficulties in synchronizing wireless communication between nodes and promoting fairness. The paper was well motivated and articulated. I appreciated the authors noting their difficulty in making the RTS-CTS scheme work in multicast, although I admit I was disappointed that it was left as an open question. The autohrs also mentioned that their analysis assumes symmetry between stations, e.g. to assume that RTS-CTS will successfully avoid collisions at the receiver. Is this an okay assumption?  How much noise is typically present in the real world?