XORs in The Air: Practical Wireless Network Coding
url show details
You need to log in to add tags and post comments.
| papers | collections | search | login | register | forgot password? |
|
| papers | collections | search | login | register | forgot password? |
|
XORs in the Air applies a very clever idea in coding theory to “increase” the amount of information delivered in a single packet. The key idea (COPE) is that a sending node will merge a set of outgoing packets together using XORs and deliver them to multiple recipients in a single wireless broadcast. The “trick” now is that (hopefully) the receiving nodes have enough information to decode the original packet (by XOR’ing with the packets it has). This is possible when receiving nodes operate in “promiscuous” mode and maintain a buffer of recently observed packets. The receiving node also tries to inform the sender of its known set of packets, such that the sender can decide the optimal set of source packets to XOR together. Ideally, encoding of more packets is better.
The key benefit of this approach is to improve the overall bandwidth, especially in the presence of “bottleneck” links, where a significant amount of cross-traffic (the relay node is one example the authors demonstrate) lead to dropped packets. By merging the cross-traffic through XORs, the authors predict theoretical upper bounds in bandwidth improvement for various topologies (in general, the gain is 2 in terms of coding). From a congestion improvement point of the view, the authors show (through artificial topology) that the gain due to congestion reduction can be unbounded.
The authors then show that building and testing the real topology examples (that were analyzed) generally matched expectations. Their most detailed testbed involved 20 experimental nodes organized as a wireless mesh network. The authors show in these experiments that: 1) high collision-related losses will not benefit from COPE since queues remain empty and have very little coding opportunity and 2) COPE is most effective under conditions with all the nodes being within carrier sense range and having high bandwidth demands (resulting in high coding opportunities). The authors also show that mismatches in uplink/downlink reduce coding opportunities.
My comments:
This paper is solid and implements a very novel idea. The analytical upper bounds derived from the topologies were easy to understand and gave good intuition as to where the gains are coming from. There a few issues:
1. I was hoping the authors could further elaborate on their choice of the G = 0.8 constant used to determine when it is appropriate to “guess” a destination’s set of known neighboring packets. The authors make the observation in 7.4.2 that guessing turns out to be very important under high demand.
2. It would have been nice to see a graph that shows sensitivity to the T parameter, which indicates how long to keep packets around, as this determines how much memory is needed to store recorded packets.
3. Realism of their testbench. The authors relied on artificially generated traffic to study their techniques. The ultimate benchmark, of course, is to have end-users operate in the environment (such as in the Roofnet paper). It’s not clear in a real environment whether the “300%” improvement in UDP bandwidth with COPE will actually hold up.
This is a very good paper. Network Coding is a technique that has been used in some Wireless Sensor Networks and I know many people that are working on this area and I think they are getting good results.
This is a good theoretical paper but the authors were a little too much optimistic somethings, because there are some details that limit the gain obtained by network coding (as they found out TCP congestion avoidance can almost eliminate any possible gain). On the other hand, the results with UDP are very impressive.
Regarding the value for G, they could have tested other values to see what would happen, but higher values would make guessing more difficult and lower values could make retransmissions more frequent.
This is a good example of putting an interesting theory into practice. Also, another example of where TCP's assumptions end up making a wireless network protocol harder to get right.
It might be interesting, from both an acronym and implementation standpoint, to combine XOR with ExOR -- nodes would have to both receive and be able to decode a packet to add it to their batch queue.
Another potentially interesting idea would be coding packets in such a way that they would only need to be decoded several hops away. This could save computation time at intermediate nodes, however it would be tricky to implement right, since non-local communication would be required.
I thought this was one of the most exciting papers so far, with a nice idea and a good set of characterization / experiments. One thing I didn't quite understand is, they say with hidden terminals COPE doesn't help. Would this be an issue in using COPE in a real network? I guess theoretically if it doesn't harm the performance of the network, then it doesn't matter, though if you can't guarantee a gain, people are not likely to use it?
It was a very interesting idea to code multiple packets into one by exploiting broadcasting in wireless networks. However, I am suspicious about performance in the case that this should be deployed in highly mobile ad-hoc networks. The "20-node testbed" here in the paper doesn't look like a mobile environment.
This is a very interesting technique. However, like the other paper, this one seems to gloss over the fact that it would only really be beneficial in mesh networks, not in the type of wireless networks commonly found today in actual practice (where a mobile device talks to a wired access point connected to the Internet). In this common situation, there would be very little potential to gain extra throughput, because there is little redundant information.
This paper also somewhat reminded me of the XOR circularly-linked list data structure, where each node stores the XOR of the pointers to the previous and next nodes. Debugging such a data structure is not a lot of fun, and I imagine that trying to trouble-shoot an issue with XOR-encoding network devices would also not be very much fun.
A comment on Anshul's question (comment #9) regarding retransmission of packets that did not make it to their destination: Given that the native packets (belonging to the XORed packet) had similar sizes, it really doesn't make a difference if we choose to send the XORed or the original native packet. The are both approximately the same size. The only minor drawback I can imagine is that the receiving node would have to keep its packet pool intact for a longer time in order to be able to decode the retransmitted XORed packet.
The paper presents a novel idea of improving bandwidth from results in information theory. I'm impressed that they could implement the whole thing into the real world and get positive results on both TCP and UDP flows. COPE could work very well in a congested network, however, TCP will suffer from high loss rates at the same time, so the application of the idea maybe somehow restricted.
I really liked this paper. It had a cool idea, had results on real deployments(versus simulations) and did a very thorough job of identifying and explaining the different causes of improvement/failure.
One question that I did have was if you could do something smarter than XORs. Presumably, there are better network coding ideas out there? Has there been any follow up work that studies this?
I like read this paper. It gives a very innovative networking system that saves the bandwith of the wireless networking.
I am especially interested to see the integration of this paper with the other paper assigned.
The idea of XOR packet for transmission is really clever. When I started reading the paper, I was quite skeptical about the performance of the protocol especially when they set a threshold probability at very high value (0.8) because with many packet to combine it seems not likely to achieve such a high probability. I also want to see the performance of this algorithm in ad-hoc network that all nodes are moving because in that situation, the probability that all nexthop nodes would be able to decode its packet seems to be very low.
There was a hudge debate about how applicable the network coding is in the network community. Now it seems a little bit clear that, NC is more practical in wireless network than in wired network. As far as I know this paper is the first to implement NC in wireless nodes. So I really enjoy this paper.
In my mind, the clever part of the idea in this paper is its opportunistic coding. Different from NC in wired network, it just listen to the network and wait for the coding chance. In this way, the system don't need the synchronization mechanism (which is really expensive in wireless network) as required by decoding. Or I view the system as a degraded coding system, but at least it works.
Question: can we combine the opportunistic coding with the opportunistic multi-hop routing?