XORs in the Air: Practical Wireless Network Coding

S. Katti, H. Rahuk, W. Hu, D. Katabi, M. Medard, J. Crowcroft, "XORs in the Air: Practical Wireless Network Coding," ACM SIGCOMM Conference, (September 2006).

One line summary: This paper describes a coding mechanism for improving throughput in wireless networks called COPE; COPE relies on XORing packets together and is able to improve overall network throughput in many cases.

Summary

This paper presents a coding mechanism for improving throughput in wireless networks that sits as a shim between the IP and MAC layers. This mechanism is called COPE. Two key design principles of COPE are that it embraces the broadcast nature of the wireless channel and it employs network coding. COPE employs three main techniques: opportunistic listening, opportunistic coding, and learning neighbor state. Basically, the way COPE works is that all packets are broadcast. When a node overhears a broadcast packet it stores it for a short time. Each node also shares with its neighbors the packets it has overheard. When a node needs to transmit, it encodes several packets together by XORing them if each of the packets’ intended recipients has enough information to decode the XORed packet. This is the case for a given recipient if the intended recipient has overheard n-1 of the n packets that have been XORed together, and the nth packet is the one destined for the intended recipient.

The packet coding algorithm of COPE required several design decisions: (1) COPE never delays packets, (2) COPE gives preference to XORing packets of the same length, (3) COPE maintains two virtual queues (one for big packets and one for little pakcets) per neighbor to aid in making coding decisions, (4) COPE makes sure packets do not get reordered, and (5) in COPE each node tries to ensure that each neighbor to whom an XORed packet is headed has a high probability of decoding the packets within. COPE uses pseudo-broadcast because real broadcast lacks reliability and backoff upon collision. It also uses hop-by-hop and asynchronous ACKs and retransmissions. The authors define two measures by which to quantify the throughput gains of COPE. The first is the coding gain and it is defined as the ratio of the number of transmissions required by a non-coding approach to the minimum number of transmissions required by COPE to deliver the same set of packets. The second is the coding+MAC gain and occurs due to COPE’s beneficial interaction with the MAC. For topologies with a single bottleneck, for example, this is defined as the ratio of the bottleneck’s draining rate with COPE to its draining rate without COPE.

The paper gives a nice flowchart that succinctly shows the operation of the sender and receiver operation in COPE. It also describes their evaluations. The most important findings from the evaluations are as follows: (1) when the wireless medium is congested and the transport layer does not perform congestion control (e.g. UDP) COPE delivers 3-4x improvement in throughput, (2) in this case COPE’s throughput exceeds the expected coding gain and agrees with the coding+MAC gain, (3) when the network is connected to the Internet via a gateway, the throughput improvement from COPE depends on the amount and diversity of upload traffic and ranges from 5% to 70%, and finally (4) hidden terminals in the network create a high loss rate which causes TCP to underutilize the medium and not create enough coding opportunities, so there is no improvement with COPE; when there are no hidden terminals and TCP is used as the transport protocol, the throughput of COPE agrees with the expect coding gain.

Critique

This paper struck me as one of those ideas that seem obvious after you read it. That is usually a good thing, at least in my mind. One thing I thought was interesting is the choice to use pseudo-broadcast instead of just implementing their own ACKs and backoff as has been done in other papers. One bad thing about COPE is its need to order packets at the destination. The authors state this is necessary because COPE reorders packets and this can hurt the performance of TCP but one result of this modification is that other causes of reordering are masked. This is probably not important though. It’s disappointing that COPE doesn’t really provide much improvement when used with TCP. One thing I really wondered about is why in the evaluation of COPE in a network that is connected to the Internet via one or more gateways, the throughput improvement depended on the amount of uplink traffic. I’m not sure I understand why this is the case and I thought they could have explained it a little more fully. Perhaps when there is a higher uplink to downlink ratio there are more coding opportunities. If it is true that more uplink traffic results in improved throughput then in real world situations the throughput gains are likely to be disappointing, because in at least one other paper that we read for this class, it is said that in general there is less uplink to the Internet than downlink traffic from the Internet. One other thing is that for their metrics they used aggregate measures such as total network throughput and it might have been nice to see average per-flow throughput as well.