A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

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).

One line summary: This paper uses a network simulator that the authors improved by adding relatively realistic physical and spatial models to compare four wireless ad hoc network protocols: DSDV, TORA, DSR, and AODV, that cover a wide range of different design choices.

Summary

This paper compares four wireless ad hoc network routing protocols using detailed simulations. The four protocols compared were (1) Destination-Sequenced Distance Vector using sequence number triggered updates (DSDV-SQ), (2) Temporally Ordered Routing Algorithm (TORA), (3) Dynamic Source Routing (DSR), and (4) Ad Hoc On-Demand Distance Vector using link layer feedback to detect link breakage (AODV-LL). DSDV-SQ is a hop-by-hop distance vector routing protocol that uses periodic broadcast updates and guarantees loop freedom. TORA is a distributed routing protocol that uses a link-reversal algorithm to provide on demand route discovery and runs on top of IMEP. DSR uses on-demand source routing and consists of Route Discovery and Route Maintenance phases. Lastly, AODV-LL is like a combination of DSR and DSDV because it has on-demand Route Discovery and Route Maintenance along with hop-by-hop routing and sequence numbers. These protocols were simulated using ns-2 at varying levels of node mobility and number of senders. The simulator was enhanced to allow for realistic physical layer and propagation modeling as well as node mobility. It used a random waypoint model to simulate mobility and constant bit rate (CBR) sources. The metrics by which the protocols were judged were (1) packet delivery ratio, (2) routing overhead, and (3) path optimality.

The results are presented for each metric. These results are for hosts that move at a speed of 20 m/s when not paused. In terms of the percentage of packets delivered, DSR and AODV-LL deliver between 95% and 100% of packets regardless of offered load and node mobility. DSDV-SQ drops to 70% packet delivery with constant node mobility, which the authors attribute to packets dropped on account of a stale routing table entry. TORA does well until the number of sources sending packets reaches 30 then experiences congestive collapse due to a positive feedback loop. In terms of routing overhead, DSR and AODV-LL have similar curves although AODV-LL has higher overhead when node mobility is near constant. The authors later note that if measured in bytes instead of packets, the overhead of DSR becomes much greater than AODV-LL. The overhead of TORA depends in part on node mobility and is much higher than any of the other protocols. DSDV-SQ has nearly constant overhead independent of node mobility or offered load. In terms of path optimality, both DSDV-SQ and DSR use near optimal routes regardless of node mobility, whereas TORA and AODV-LL use less optimal routes when node mobility is high. Other interesting observations the authors make are that the percentage of packets successfully delivered for broadcast packets is lower than for unicast packets. They also note that early in their experiments they found a serious integration problem with ARP; they found a workaround but note that this problem would have to be addressed in any real implementation running on top of ARP. The authors don’t really conclusively rank the protocols in the end but it is clear from the experiments that DSR is probably the best protocol, followed by AODV-LL and DSDV, with the relative ranking of these two being less clear due to tradeoffs. TORA is obviously the worst protocol in almost every respect.

Critique

Although I tend to think that real-world experiments are always preferable to simulations, I like that the authors improved the network simulator to include a spatial model to simulate host mobility and a relatively realistic physical layer and radio network interface model. I also appreciated the thoroughness of their simulations with respect to their clearly stated metrics. Their section describing their experimental results was considerably easier to follow than most papers and the way they laid out their graphs made it pretty easy to compare the results from the different protocols. I also like that they provided additional, more in-depth explanations for certain observations where they were warranted, for example, their explanation of the congestive collapse of TORA. Their section containing additional observations was nice too. For some reason I am having trouble questioning their assumptions and making criticisms of this paper (nothing immediately jumps out at me), but because they used a simulator and also implemented all the protocols themselves there are clearly going to be a lot of assumptions that underlie their results. I thought they did a pretty good job of clearly stating what all these assumptions were though, so at least they are there for readers to take into account. I liked this paper and I think it’s probably good to keep it in the syllabus.

VL2: A Scalable and Flexible Data Center Network

A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz, P. Patel, S. Sengupta, "VL2: A Scalable and Flexible Data Center Network," ACM SIGCOMM 2009, (August 2009).

One line summary: This paper presents VL2, a data center network architecture that provides layer 2 semantics, high capacity, and performance isolation between services using flat addressing, Valiant Load Balancing, and a directory service for mappings, and runs over a Clos topology.

Summary

This paper presents a data center network architecture called VL2. The goals of VL2 are to achieve uniform high capacity, performance isolation between services, layer 2 semantics, as well as agility (the ability to assign any server to any service). VL2 is built from low cost switches arranged into a Clos topology and uses Valiant Load Balancing (VLB) to spread traffic across available paths and adapt to volatility in traffic and failure patterns. The authors of the paper first conduct a data center traffic analysis by implementing a data center that supports data mining. From this their major findings were that (1) the majority of flows are small, (2) the number of concurrent flows through a machine is around ten more than half the time, (3) the variability in traffic patterns is not easily summarized and there are a large number of representative traffic matrices, (4) traffic patterns change nearly constantly and unpredictably, (5) most failures are small in size, and (6) the main causes of downtimes are network misconfigurations, firmware bugs, and faulty components, and there is no obvious way to eliminate failures from the top of the data center topology hierarchy.

Briefly, VL2 operates as follows. VL2 is built on a Clos network topology. It uses two different kinds of addresses: location specific IP addresses (LAs) and application specific IP addresses (AAs). All switches and interfaces have LAs. Each server has an AA that remains the same no matter where the application is located and is assigned when the server is provisioned to a service. All servers within a service believe they are in the same subnet. The AA of a server is associated with the LA of the ToR switch to which the server is connected. Switches run a link-state routing protocol using these LAs. In performing routing, VL2 uses VLB to distribute traffic across intermediate switches and ECMP to distribute across equal cost paths. There is a VL2 agent at each server that encapsulates packets emanating from the servers within a packet that has the LA address of the destination ToR in the header. A directory service stores AA-LA-MAC address mappings. The directory service consists of a number of read-optimized directory services that cache AA-LA mappings and a smaller number of write-optimized replicated state machine servers that reliably store AA-LA mappings. The directory service performs lookups, updates, and reactive cache updates.

The authors perform an evaluation of VL2, which serves to demonstrate that VL2 provides uniform high capacity, VLB fairness, performance isolation, convergence after link failures, and has a directory service that is scalable and resilient, with high availability and throughput. Of these experiments, I thought the most interesting was the one where they performed an all-to-all data shuffle stress test to show VL2 achieves high utilization and fairness between flows.

Critique

In terms of criticisms, here are several notes I made about this paper:

I liked that before designing VL2 they did an analysis of data center traffic. The results of this were somewhat surprising to me so I found them interesting. However, for this analysis, the authors instrumented a data mining workload, but it’s probably not the case that a data mining workload is representative of most traffic in data centers in general.

I didn’t understand why they exclude UDP traffic from consideration in their evaluations, in which they only use TCP flows, not UDP flows. I don’t know if this is realistic. They make some hand wavy claim that techniques such as STCP to make UDP “TCP friendly” are well known and can be used, but I am not convinced it is really that easy. Also in their evaluations, they state that they rely on TCP to ensure that each flow is rate limited to its fair share of the bottleneck, but many of the previous papers we read suggest that TCP is not very good at fairness. Another thing is that in their evaluation using data shuffle, they claim that a conventional design would take 11x longer but they don’t explain where they got their figures. Also, they claim several times throughout the paper that agility is a big goal for VL2 but they don’t do an experiment to show what happens when a server is migrated, as was done in the PortLand paper. I don’t think that by agility they necessarily mean ease of VM migration but perhaps this still would have been interesting to examine.

Some miscellaneous points are that in one part of the paper, they claim that that VL2 enables fine-grained path control by adjusting the randomization used in VLB but they don’t elaborate further on this. Also the performance of VL2 appears to depend on traffic obeying the hose model. I don’t know what the hose model is, but is it safe to assume all data center traffic will obey the hose model?

A general point not just about this paper in particular but about all of these papers on data center networks is that it seems that every paper only uses evaluations that highlight the good features of the solution suggested in that paper, so it is hard to compare solutions. It would be nice if there were at least some standard experiments or similar experiments that could facilitate comparison, analogous to the sets of benchmarks used for processors in architecture.