Transcript Slide 1
Wireless Network Coding Martin Xu Outline • Introduction • New Solutions – COPE – ANC • Conclusions Introduction • Wireless: mobility • Problem: severe throughput limitation • Solutions – COPE – ANC –… • Let’s take a look at traditional wireless… Traditional Wireless Router Traditional Wireless Router 4 transmission required Traditional Wireless Router 4 time slots required COPE • Katti, S., Rahul, H., Hu, W., Katabi, D., Médard, M., and Crowcroft, J. 2006. XORs in the air: practical wireless network coding. In Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (Pisa, Italy, September 11 - 15, 2006). SIGCOMM '06. ACM Press, New York, NY, 243-254. • Forward multiple packets in a single transmission • Let’s take a look at how COPE deals with the aforementioned example COPE Router XOR = COPE Router COPE Router XOR = XOR Higher throughput (3 transmissions required) = COPE • Transparent coding layer between IP and MAC • Forward multiple packets in a single transmission • Never delay packets • HOW? – Opportunistic Listening – Opportunistic Coding – Learning neighbor state COPE - Listening • “Broadcast” in a small neighbor • Each node stores overheard packets for a limited time • Pseudo broadcast – Broadcast results in poor reliability and lack of backoff – Pseudo broadcast unicast packets that are meant for broadcast COPE - Coding • To transmit n packets, p1, ..., pn, to n nexthops, r1, ..., rn, a node can XOR the n packets together only if each next-hop ri has all n − 1 packets pj for j = i. COPE - data structure • Reception report – Reports are piggybacked on packets – If no packets to send, periodically send reports • Output queue (FIFO) • Two per-neighbor virtual queue – packet-size distribution in the Internet is bimodal with peaks at 40 and 1500 bytes • Packet info COPE - Performance • With no hidden terminals, TCP’s throughput can increase by 38% • flows, COPE increases UDP throughput by 3-4x ANC • Katti, S., Gollakota, S., and Katabi, D. 2007. Embracing wireless interference: analog network coding. In Proceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (Kyoto, Japan, August 27 - 31, 2007). SIGCOMM '07. ACM Press, New York, NY, 397-408. • Strategically exploit interference instead of avoiding it – Interfered signal is not exactly the sum – Channel distorts signals – Two signals are never synchronized ANC - Algorithm • Decode small part of uninterfered signal (MSK) • Decode interfered signal – Decomposition using amplitudes of the original ones and the interfered – Four possible angles – Choose the 90 degree one • Decode the rest of the uninterfered signal ANC - Performance • For the example used at the beginning, median throughput gain of ANC over routing 70%, COPE 30% • For X-topology, median throughput gain over routing is 65%, over COPE 28% • For chain topology, median throughput gain over routing is 37% Conclusion • Both implementation that yields large throughput gains • COPE – Simple and practical • ANC – Embrace Broadcast and Interference