Summary
I really liked this paper, mostly just because it's a very clever idea. An algorithm, COPE, again taking advantage of the broadcast nature of wireless radios but this time by packing more data into a single transmission, is developed in this paper. This is done by maintaining a packet buffer at each node, and by knowing (or guessing) what packets nearby nodes have in their buffers. The can be known with certainty through 'reception reports', or by guessing based on expected transmissions given the routing metric. Once I know what my neighbors have I can look at the next packet I need to transmit. If I can find n packets such that my neighbors all have n - 1 of those packets (not necessarily the same n-1 packets though) then I can XOR those packets together to send multiple packets in the space of one 'native' packet. Any neighbors with n-1 packets can XOR again to get the native packet they don't have back out. This increases the throughput of the network without changing anything else.
Each node maintains a queue of packets to send out. This could be re-ordered to provide more XOR-ing opportunities, but this isn't done since it would create an out-of-order problem for TCP. COPE maintains two virtual queues per neighbor, one of small packets and one of large packets. When it needs to send a packet it tries to find other similarly sized packets to XOR-ing with it (since XOR-ing small packets with large ones doesn't provide as much bandwidth savings). If appropriate packets are found, they XOR-ed in and sent.
Since the standard 802.11 MAC broadcast doesn't do ACKs the authors also introduce pseudo-broadcast which uses 802.11 unicast but adds an XOR header with all intended nodes so that any overhearing node can figure out if it was also an intended recipient. The packet is sent until the primary recipient ACKs the packet.
The authors give proofs of the bandwidth gain that can be achieved for certain network topologies. Most importantly they show that in the presence of opportunistic listening the gain is unbounded. This explains the 3x-4x increase in performance they see when running UDP tests on Roofnet. Interestingly they don't see much of a performance boost when running TCP tests. They believe this is because TCP backs off too much when collisions occur, and that collisions are common due to hidden terminals. They validate this by showing that TCP performs well with COPE when there are no hidden terminals.
Comments
I thought this was a well argued paper. It gives a good overview of a clever design, proves some interesting theoretical properties of the design, and then runs actual experiments on an implementation.
A few gripes:
I didn't like the graphs they chose to use, rather difficult to read and not particularly illuminating. Bar charts of throughput feel like they would have been much more useful.
The hidden terminal problem feels a lot like Incast to me. Would reducing the RTOmin be an effective way to deal with this problem? RTTs are probably higher in the wireless environment, but there might be some gain to be had. It's all well and good to say, we help TCP if there are no hidden terminals, but this will always be a problem in the real world.
I really liked this paper, mostly just because it's a very clever idea. An algorithm, COPE, again taking advantage of the broadcast nature of wireless radios but this time by packing more data into a single transmission, is developed in this paper. This is done by maintaining a packet buffer at each node, and by knowing (or guessing) what packets nearby nodes have in their buffers. The can be known with certainty through 'reception reports', or by guessing based on expected transmissions given the routing metric. Once I know what my neighbors have I can look at the next packet I need to transmit. If I can find n packets such that my neighbors all have n - 1 of those packets (not necessarily the same n-1 packets though) then I can XOR those packets together to send multiple packets in the space of one 'native' packet. Any neighbors with n-1 packets can XOR again to get the native packet they don't have back out. This increases the throughput of the network without changing anything else.
Each node maintains a queue of packets to send out. This could be re-ordered to provide more XOR-ing opportunities, but this isn't done since it would create an out-of-order problem for TCP. COPE maintains two virtual queues per neighbor, one of small packets and one of large packets. When it needs to send a packet it tries to find other similarly sized packets to XOR-ing with it (since XOR-ing small packets with large ones doesn't provide as much bandwidth savings). If appropriate packets are found, they XOR-ed in and sent.
Since the standard 802.11 MAC broadcast doesn't do ACKs the authors also introduce pseudo-broadcast which uses 802.11 unicast but adds an XOR header with all intended nodes so that any overhearing node can figure out if it was also an intended recipient. The packet is sent until the primary recipient ACKs the packet.
The authors give proofs of the bandwidth gain that can be achieved for certain network topologies. Most importantly they show that in the presence of opportunistic listening the gain is unbounded. This explains the 3x-4x increase in performance they see when running UDP tests on Roofnet. Interestingly they don't see much of a performance boost when running TCP tests. They believe this is because TCP backs off too much when collisions occur, and that collisions are common due to hidden terminals. They validate this by showing that TCP performs well with COPE when there are no hidden terminals.
Comments
I thought this was a well argued paper. It gives a good overview of a clever design, proves some interesting theoretical properties of the design, and then runs actual experiments on an implementation.
A few gripes:
I didn't like the graphs they chose to use, rather difficult to read and not particularly illuminating. Bar charts of throughput feel like they would have been much more useful.
The hidden terminal problem feels a lot like Incast to me. Would reducing the RTOmin be an effective way to deal with this problem? RTTs are probably higher in the wireless environment, but there might be some gain to be had. It's all well and good to say, we help TCP if there are no hidden terminals, but this will always be a problem in the real world.
I agree with your comments about the limitation of the approach, particularly in terms of the interaction of XOR and TCP. I think the packet cache mechanism, and the need to hold on to packets to get the coding gain, could lead to greater variability in the packet delivery times. RTO mods might help, but I would be more concerned with the implications for RTT.
ReplyDelete