Tag Archives: Hu

XORs in the Air: Practical Wireless Network Coding

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:

  1. In the absence of opportunistic listening, COPE’s maximum coding gain is 2, and it is achievable;
  2. In the absence of opportunistic listening, COPE’s maximum Coding+MAC gain is 2, and it is achievable; and
  3. 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.

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