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.