Nalanda

Citation: Katti, S., Rahul, H., Hu, W., Katabi, D., Médard, M., and Crowcroft, J. 2006. XORs in the air: practical wireless network coding. SIGCOMM Comput. Commun. Rev. 36, 4 (Aug. 2006), 243-254. DOI=http://doi.acm.org/10.1145/1151659.1159942

In a similar vein to the other reading for today, the approach presented in this paper, COPE, attempts to take advantage of, rather than work against, the characteristics of the wireless medium. The COPE approach is, however, fundamentally different from the other papers that we’ve read: instead of trying to optimize the routes that a packet takes through a network, COPE attempts to optimize utilization. It does so by coding packets being sent to the same next hop node together into a single packet, increasing the effective bit rate of a network.

COPE relies on knowledge of packets that neighbours may have received in order to perform coding; receivers must have all “native” packets used to form an encoded packet other than the one meant for them. When choosing packets to code, an estimate is made of the probability that neighbours for whom these packets are destined have already heard them. While this would work well in a relatively dense network, a network topology where most nodes are not in range of one another would probably not be served well by COPE.

Packets are coded together only when the probability that they are known to the next hops remains sufficiently high. Note that this also means that COPE will not function well in a network with high degrees of mobility, where neighbours are constantly changing. It is best applied to cases such as that presented in this paper, of fixed nodes connected to form a wireless backhaul. This also means that gains from COPE become apparent only as the diversity of packets increases, which could happen both with increased traffic, but also, I imagine, as the number of source/destination pairs increases.

Various theoretically derived ideal coding gains are presented, showing that the maximum coding gain without opportunistic listening is 2, and with opportunistic listening tends to infinity. Interestingly, the authors found that coding gain increased beyond this value in their testbed, since the queues at bottleneck routers become smaller with the use of coding, fewer packets are dropped at the router’s queue.

The results of testing on a 20-node wireless testbed are presented, with a very useful discussion of how COPE interacts with both UDP and TCP flows. UDP flows see a large throughput gains, in the range of 3-4 times the same network without COPE. Initial tests for TCP showed only marginal gains (2-3%) due to hidden terminal problems causing sufficient collision-related losses to trigger timeout and backoff in the TCP flows. When the nodes were brought closer together to a range where carrier sense could function, an increase of 38% in throughput was observed.

Where most research in this space has continued to emphasize newer approaches to routing, this paper, as the authors put it, presents a new “orthogonal axis” to extracting more throughput. I really liked this paper, both for the compelling ideas it puts forward, and also for the extensive discussion of their implementation.