Shravan Rayanchu
Abstract
Local network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of transmissions needed to carry packets across each wireless hop. While such a strategy is certainly useful, we argue that in lossy wireless environments, a better use of local network coding is to provide higher levels of redundancy even at the cost of increasing the number of transmissions required to communicate the same information. In this paper we show that the design space for effective redundancy in local network coding is quite large, which makes optimal formulations of the problem hard to realize in practice. We present a detailed exploration of this design space and propose a suite of algorithms, called CLONE, that can lead to further throughput gains in multi-hop wireless scenarios. Through careful analysis, simulations, and detailed implementation on a real testbed, we show that some of our simplest CLONE algorithms can be efficiently implemented in today's wireless hardware to provide a factor of two improvement in throughput for example scenarios, while other, more effective, CLONE algorithms require additional advances in hardware processing speeds to be deployable in practice.
- The click modular router. http://www.read.ucla.edu/click/.Google Scholar
- Soekris engineering. http://www.soekris.com/net4826.htm.Google Scholar
- Network Flows: Theory, Algorithms, and Application. Prentice Hall, 1993. Google ScholarDigital Library
- R. A., S. J., and W. R. D. On the capacity of network coding for random networks. In Allerton Conference on Communications, 2003.Google Scholar
- D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-level measurements from an 802.11b mesh network. In SIGCOMM '04. ACM, 2004. Google ScholarDigital Library
- R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yenug. Network information flow. In IEEE Transactions on Information Theory, 2000. Google ScholarDigital Library
- J. Bicket, D. Aguayo, S. Biswas, and R. Morris. Architecture and evaluation of an unplanned 802.11b mesh network. In ACM Mobicom, 2005. Google ScholarDigital Library
- S. Biswas and R. Morris. Exor: opportunistic multi-hop routing for wireless networks. In ACM Sigcomm, 2005. Google ScholarDigital Library
- S. Chachulski, M. Jennings, S. Katti, and D. Katabi. Trading structure for randomness in wireless opportunistic routing. In ACM SIGCOMM, 2007. Google ScholarDigital Library
- P. A. Chou, Y. Wu, and K. Jain. Practical network coding. In Allerton Conference on Communications, 2003.Google Scholar
- D. D. Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In MOBICOM, 2003. Google ScholarDigital Library
- Q. Dong, J. Wu, W. Hu, and J. Crowcroft. Extended abstract: Practical network coding in wireless networks. In Mobicom, 2007. Google ScholarDigital Library
- S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. MÃ;l'dard. Resilient network coding in the presence of byzantine adversaries. In INFOCOM, 2007.Google ScholarDigital Library
- A. Kamra, V. Misra, J. Feldman, and D. Rubenstein. Growth codes: Maximizing sensor network data persistence. In ACM SIGCOMM, 2006. Google ScholarDigital Library
- S. Katti, S. Gollakota, and D. Katabi. Embracing wireless interference: Analog network coding. ACM SIGCOMM'07. Google ScholarDigital Library
- S. Katti and D. Katabi. Mixit: The network meets the wireless channel. In ACM HotNets, 2007.Google Scholar
- S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. Xors in the air: Practical wireless network coding. In ACM SIGCOMM, 2006. Google ScholarDigital Library
- R. Koetter and M. Medard. An algebraic approach to network coding. In IEEE Trans. Networking, 2003. Google ScholarDigital Library
- S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. In IEEE Trans. on Information Theory, 2003. Google ScholarDigital Library
- Z. Li and B. Li. Network coding: The case for multiple unicast sessions. In Allerton Conference on Communications, 2004.Google Scholar
- D. S. Lun, N. Ratnakar, R. Koetter, E. A. M. Mdard, and H. Lee. Achieving minimum cost multicast: A decentralized approach based on network coding. IEEE INFOCOM'05.Google Scholar
- M. Medard, M. Effros, T. Ho, and D. Karger. On coding for non-multicast networks. In Allerton Conference on Communications, 2003.Google Scholar
- L. Valiant. The complexity of enumeration and reliability problems. In SIAM Journal on Computing, 1979.Google ScholarCross Ref
- D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica'95.Google Scholar
- Y. Wu and S. Chou, P.A. Kung. Information exchange in wireless networks with network coding and physical-layer broadcast. Technical Report, MSR-TR-2004-78, Microsoft Research, 2004.Google Scholar
- S. Zhang, S. C. Liew, and P. Lam. Hot topic: Physical-layer network coding. In Mobicom, 2006. Google ScholarDigital Library
- S. Rayanchu, S. Sen, J. Wu, S. Banerjee, and S. Sengupta. Loss-Aware Network Coding for Unicast Wireless Sessions: Design, Implementation, and Performance Evaluation Technical Report UW-CS-TR-1633, University of Wisconsin-Madison, Computer Sciences Dept., 2008.Google ScholarDigital Library
Index Terms
- Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation
Recommendations
Loss-aware network coding for unicast wireless sessions: design, implementation, and performance evaluation
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systemsLocal network coding is growing in prominence as a technique to facilitate greater capacity utilization in multi-hop wireless networks. A specific objective of such local network coding techniques has been to explicitly minimize the total number of ...
Network coding-aware routing in wireless networks
A recent approach--COPE, presented by Katti et al. (Proc. ACM SIGCOMM 2006, pp. 243-254)--for improving the throughput of unicast traffic in wireless multihop networks exploits the broadcast nature of the wireless medium through opportunistic network ...
Network coded ALOHA for wireless multihop networks
WCNC'09: Proceedings of the 2009 IEEE conference on Wireless Communications & Networking ConferenceThe purpose of this paper is to show the possibility of combining slotted ALOHA with network coding in wireless multihop networks. In particular, we focus on a star topology in which outer nodes exchange data with each other through a center node. The ...
Comments