XORs in The Air: Practical Wireless Network Coding

Summary

The key idea of this paper is to take advantage of the broadcast nature of wireless and coding to reduce the number of packets that must be sent to transmit data.

The proposed design, COPE, uses three main techniques:

1. Opportunistic learning. COPE overhears packets destined for other nodes and stores them for some time
2. Opportunistic coding. COPE tries to send data encoded in such a way that multiple receivers can extract the packets they need using the data they already have.
3. Learning neighbor state. COPE guesses what packets neighbors may have using the ETX metric.

COPE works by basically "adding" together packets such that multiple recipients can "subtract" the data they already have and obtain a new piece of data. In practice this is accomplished using XOR. This technique is particularly useful when multiple nodes are exchanging data.

The authors find a 3-4x performance improvement when using COPE for UDP flows.

Thoughts

This is a clever use of the broadcast nature of wireless to improve performance. I am actually quite surprised it works as well as it does.

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

Summary

This paper presents a new metric, expected transmission count (ETX), for choosing high-throughput paths in a multi-hop wireless network. This metric takes into account link loss rates, asymmetry in loss ratios and interference among the successive links in a path. The authors evaluate this metric in a real test environment and compare it to minimum hop count.

The authors first analyze the shortcomings of the minimum hop-count metric. They find that minimum hop count performs well "whenever the shortest route is also the fastest route." However, minimum hop-count does not consider loss rates which the authors find to vary widely in their test environment. Also, minimum hop-count does not have a way to choose among multiple paths of the same length.

ETX is designed to address these issues. It works by predicting the number of transmissions required to deliver data. In other words, it computes 1 / (df X dr) where df is the probability that the data packet makes it across the link and dr is the probability the ACK is successfully returned. df and dr are computed empirically by occasionally sending probe packets and counting the delivery rate.

The authors implement ETX in the DSDV routing algorithm and compare it to the original DSDV using minimum hop-count. They find that ETX provides a throughput improvement in all cases but it is less significant when large packets are used because the small probe packets do not accurately model the transmission probability for large packets.

Thoughts

ETX is clearly a better metric than minimum hop when dealing with lossy links. It could be improved by estimating actual throughput, as in RoofNet, not just transmission count. This would account for different transmission rates. Finally, it seems that the link loss probabilities could be computed/updated from the data actually being sent not just the probe packets. Overall, this paper presents a simple and clearly useful idea.

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

Summary

This paper compares four multi-hop routing protocols, DSDV, TORA, DSR and AODV, using a network simulator. The simulation is done in a modified ns-2 network simulator with an 802.11 MAC implementation and a realistic radio signal attenuation model.

The authors briefly describe each of the protocols being considered:

1. DSDV: Each node maintains a table with the next hop for all destinations. Routing updates are broadcast.
2. TORA: Routes discovered on demand. Quickly establishing routes is preferred over choosing the shortest path.
3. DSR: The source decides the full route of each packet. Routes are discovered through flooding "Route Request" packets.
4. AODV: Combines route request and maintenance from DSR with hop-by-hop routing from DSDV.

In the evaluation the authors simulated 50 nodes over an area of 1.5k x 300m. The nodes moved at different rates and in different patters. The measured metrics were packet delivery ratio, routing overhead and path optimality.

Packet delivery rates were good (>95%) for DSR and AODV at all rates of mobility. However, DSDV had a poor delivery ratios when nodes moved quickly and TORA could not handle a large number of sources.

The routing overhead also changed significantly with the movement of nodes. In both DSR and AODV the routing overhead was much higher at high mobility. DSDV overhead remained fairly constant and TORA had the constantly very high overhead.

Thoughts

This seems like a thorough and useful analysis of routing protocols. However, the protocols being compared are fairly old. I am curious if any of these are still used today or if they have been superseded. Also, it is not clear how well this simulation would translate to real-world performance.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

This paper describes the design of a wireless mesh network. The key goal of the design is ease of deployment. So nodes are in unplanned locations and they use omni-directional antennas to avoid having to configure antenna placement. This necessitates a multi-hop routing and path optimization to provide adequate throughput.

The network is auto-configuring and has only some nodes that act as external gateways to the Internet. It uses an internal addressing system based on the MAC address of the Ethernet cards to route within the mesh. At the gateways, NAT is used to translate internal addresses to external ones. This means that connections are tied to a specific external gateway and cannot shift if network conditions change. However, new connections always use the "optimal" gateway.

To route within the wireless mesh each node uses Dijkstra's algorithm to choose the best path. The cost of each link is estimated using an "estimated transmission time" metric. This takes into consideration the throughput bit-rate of the link and the probability of delivery at that bit-rate. For example, "a single-hop route with 40% loss can deliver more data than a two-hop route with perfect links." By considering these trade-offs the node is able to maximize its throughput.

The authors deploy a system of 33 nodes and 4 gateways on rooftops in Cambridge Massachusetts by asking volunteers to install the nodes. They obtain an average throughput of 627 kbits/s with links having a median loss rate of 20%. The throughput is mostly dependent on the number of hops with just 89 kbit/s at 5 hops.

Modeling Wireless Links for Transport Protocols

Summary

This paper details the key features of models of wireless links. The goal is to help address the issue of how to modify TCP and link-layer protocols to improve performance over wireless links.

This paper points out the key problems in current wireless models: unrealistic assumptions, small parameter space, overly realistic and lack reproducibility. Next, they list characteristics of wireless links and how to model them:

1. Error Losses: represent packet loss after link-layer retransmission attempts. Model by dropping packets with some probability.
2. Delay Variation: represents delay due to link-layer recovery, etc. Model by randomly suspending transmission.
3. Packet Reordering: caused by retransmission attempts. Model by randomly swapping packets or delaying single packets.
4. Resource Allocation: some wireless links temporarily allocate bandwidth to streams. Model by introducing delay when a packet arrives to a queue that has been empty for longer than the channel holding time.
5. Bandwidth Variation: may occur on CDMA and UMTS links. Model by occasionally reducing bandwidth of the link.
6. Bandwidth Asymmetry: wireless links typically have asymmetric bandwidths.
   

Finally the paper makes some recommendations. They suggest that bit errors should be handled at the link layer using FEC and retransmissions. However, explicit corruption notification can be used to inform TCP when transmission fails after link-layer recovery attempts. TCP should be more resilient to reordering which would give link-layer protocols more flexibility in recovery. Finally, where possible, link layer protocols should reduce delay variation but delay tolerant TCP may be useful as well.

Thoughts

This paper seemed to state fairly obvious characteristics of wireless links and modeling techniques. The key contribution seems to be in pulling all of these characteristics together and stating where previous work has failed to do so.

A Comparison of Mechanisms for Improving TCP Performance over Wireless Links

Summary

This paper explores different mechanisms to deal with loss in wireless networks. Specifically, it compares the performance of three classes of solutions:

1. End-to-end protocols
2. Link-layer protocols
3. Split-connection protocols

End-to-end protocols include standard TCP Reno and modifications. The basic problem is that standard TCP uses packet loss as a signal of congestion, however, in wireless networks packet losses can occur due to noise or interference, treating these losses as congestion degrades performance. The authors find that basic TCP Reno achieves a throughput of 50% of the maximum with a 2.3% packet loss rate on the wireless link. Other variations of TCP Reno include partial acknowledgments (new Reno) which performs better because it can fill large holes, resending one packet for each additional ACK (after 3 duplicates). A different approach is to use explicit loss notification, this allows the sender to maintain the congestion window size while retransmitting lost packets. Both of these modifications perform similarly.

The second class of solutions is link-layer protocols. These solutions perform re-transmissions at the link layer and attempt to hide the lossy link from TCP. The problem with this approach is that re-transmitting at the link-layer can lead to out of order packets received at the destination. This will cause duplicate ACKs which will activate TCP fast retransmit unnecessarily. Several solutions are explored, all involve "TCP awareness" or suppressing duplicate ACKs for packets that have already been retransmitted. The authors find that this solution is best, out performing the end-to-end solutions.

The final class of solutions is split-connection protocols. These isolate TCP from the wireless link by using a different connection to make the wireless hop. If the protocol used for the wireless hop is optimized to handle losses then the overall throughput is quite good. However, the authors argue that this approach breaks the end-to-end principle and is not necessary for good performance.

Thoughts

I am curious to know what is actually done in 802.11b/g/n networks. The link-layer recovery seems like a fairly clear solution but admittedly requires duplicating recovery functionality.

MACAW: A Media Access Protocol for Wireless LAN's

Summary

This paper analyzes the existing MACA wireless protocol and proposes changes that improve fairness and performance. The key problem they address is how to handle congestion fairly and efficiently. First the authors make several observations about congestion:

1. Contention is at the receiver not the sender
2. Congestion is location dependent
3. MACs should propagate congestion information explicitly
4. MACs should propagate synchronization information about contention periods

 The first two observations motivate using a RTS/CTS protocol instead of a carrier-sense protocol. With just carrier sensing, senders can potentially interfere with other senders that are out of range ("hidden terminal" scenario). Similarly, carrier sensing may prevent transmission even when the receivers are out of range ("exposed terminal" scenario). The solution is to use RTS/CTS, where each sender first requests to send and all stations hearing the RTS delay transmission for the length of a reply. If the receiver sends a CTS, then the sender can send and all stations hearing the CTS must wait. The key is that delaying transmission is now tied to who can hear (and thus interfere with) the messages.

This paper proposes several optimizations to the RTS/CTS protocol. Namely, using additive decrease and multiplicative increase of the backoff counter which is used to determine how quickly to re-try transmission. The paper also proposes a fairness optimization: keeping per-stream backoff counters and ordering data using "shortest wait time." They also propose using link-layer ACKs to allow faster retransmissions and DS messages to avoid collisions at the senders, who must now also receive ACKs.

Thoughts

There are a lot of similarities between the techniques used in this paper, at the MAC level, and previous papers we read that dealt with TCP/IP.  For example, the backoff counter operates much like the inverse of the congestion window in TCP/IP, dictating how much to wait before sending rather than the sending rate. Similarly, keeping per-stream queues and using shortest wait-time ordering has been used in routers (Analysis and Simulation of a Fair Queueing Algorithm). Finally, sending ACKs at the link layer is similar to ACKs at the transport layer. All of these similarities make me wonder if it is good that the same type of solutions apply at different layers of if there should be a single mechanism that solve these problems at all layers.

Finally, I am curious if any of this is used in today's wireless networks. I know my home router has RTS/CTS settings but they are turned off by default. Is this not the case for larger enterprise networks?