Rate diverse network coding: breaking the broadcast bottleneck

ABSTRACT

An inherent limitation of the existing digital wireless network coding is that the relay node has to settle for a single broadcast rate for the coded packet transmission. Since the selected rate should be supported on the worst quality links to the intended receivers, the throughput gain by network coding is essentially bound to the capacity of the worst link. Worse yet, the bottleneck capacity diminishes as the diversity of links increases, which generally happens when the nodes participating in network coding operation grow in number. In this paper, we solve this "broadcast bottleneck" by using a novel symbol-level network coding scheme called Rate Diverse Network Coding (RDNC). With RDNC, the relay node can deal with receivers under disparate channel conditions with a single coded data stream, eliminating the single-rate broadcast bottleneck. Through extensive simulation, we find that RDNC significantly boosts the coding gain and the throughput, more when the given topology provides richer opportunities for coding. Specifically, RDNC is as good as COPE in the worst case, but can achieve up to 2.5 times the coding gain if the network topology permits.

References

1. }}IEEE 802.11 WG, IEEE 802.11g-2003: Further Higher Data Rate Extension in the 2.4 GHz Band, IEEE 802.11g-2003, 2003.
2. }}R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, "Network Information Flow," IEEE Transactions on Information Theory, pp. 1204--1216, July 2000.
3. }}S. Katti, H. Rahul, W. Hu, D. Katabi, and M. Medard, and J. Crowcroft, "XORs in the Air: Practical Wireless Network Coding," in proceedings of ACM SIGCOMM, 2006.
4. }}S. Katti, S. Gollakota, and D. Katabi, "Embracing wireless interference: Analog network coding", in proceedings of ACM SIGCOMM, 2007
5. }}S. Yun, H. Kim "Towards Zero-Cost Retransmission through Physical-Layer Network Coding in Wireless Networks," ACM SIGCOMM (poster abstract), 2008
6. }}Yunnan Wu, "Broadcasting when receivers know some priori," in proceedings of International Symposium of Information Theory, IEEE, 2007.
7. }}Yunnan Wu, "Network Coding for Wireless Networks," Technical Report, MSR-TR-2007-90.
8. }}J. Zhang, Q. Zhang "Cooperative Network Coding-Aware Routing for Multi-Rate Wireless Networks," in proceedings of IEEE INFOCOM, 2009.
9. }}R. Alimi, Li Li, R. Ramjee, H. Viswanathan, Y. Yang, "iPack: in-Network Packet Mixing for High Throughput Wireless Mesh Networks," IEEE INFOCOM 2008.
10. }}O. Awoniyi and F. A. Tobagi, "Packet Error Rate in OFDM-based Wireless LANs Operating in Frequency Selective Channels," in proceedings of IEEE INFOCOM, 2006.
11. }}J. Heiskala and J. Terry, OFDM Wireless LANs: A Theoretical and Practical Guide, SAMS.
12. }}D. Tse and P. Viswanath, Fundamentals of Wireless Communication, Cambridge University Press, 2005.
13. }}R. Draves, J. Padhey, B. Zill "Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks," in proceedings of ACM MOBICOM, 2004.

Index Terms

• Networks

  • Network protocols

    • Network protocol design