Sachin Katti
Dina Katabi
ABSTRACT
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently mixing packets increases network throughput. Our design is rooted in the theory of network coding. Prior work on network coding is mainly theoretical and focuses on multicast traffic. This paper aims to bridge theory with practice; it addresses the common case of unicast traffic, dynamic and potentially bursty flows, and practical issues facing the integration of network coding in the current network stack. We evaluate our design on a 20-node wireless network, and discuss the results of the first testbed deployment of wireless network coding. The results show that COPE largely increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.
- D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris. Link-level measurements from an 802.11b mesh network. In ACM SIGCOMM, 2004. Google Scholar
Digital Library
- R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network Information Flow. In IEEE Transactions on Information Theory, 2000. Google ScholarDigital Library
- H. Balakrishnan, V. N. Padmanabhan, S. Seshan, and R. H. Katz. A comparison of mechanisms for improving TCP performance over wireless links.Google Scholar
- P. Bhagwat, B. Raman, and D. Sanghi. Turning 802.11 inside-out. In HotNets, 2003.Google Scholar
- 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. Opportunistic routing in multi-hop wireless networks. ACM SIGCOMM, 2005. Google ScholarDigital Library
- S. Chachulski, M. Jennings, S. Katti, and D. Katabi. More: Exploiting spatial diversity with network coding. In MIT CSAIL Technical Report, 2006.Google Scholar
- C. cheng Chen, E. Seo, H. Kim, and H. Luo. Self-learning collision avoidance for wireless networks. In Proceedings of IEEE INFOCOM, 2006.Google ScholarCross Ref
- M. E. Crovella, M. S. Taqqu, and A. Bestavros. Heavy-tailed probability distributions in the World Wide Web. In R. J. Adler, R. E. Feldman, and M. S. Taqqu, editors, A Practical Guide To Heavy Tails, chapter 1, pages 3--26. Chapman and Hall, New York, 1998. Google ScholarDigital Library
- D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A high-throughput path metric for multi-hop wireless routing. In ACM MobiCom '03, San Diego, California, September 2003. Google ScholarDigital Library
- S. Deb, M. Effros, T. Ho, D. R. Karger, R. Koetter, D. S. Lun, M. Médard, and N. Ratnakar. Network coding for wireless applications: A brief tutorial. In IWWAN, 2005.Google Scholar
- R. Draves, J. Padhye, and B. Zill. Comparison of Routing Metrics for Multi-Hop Wireless Networks. In Proceedings of ACM SIGCOMM, 2004. Google ScholarDigital Library
- Definition and assessment of relay based cellular deployment concepts for future radio scenarios considering 1st protocol characteristics. Chapter 5. https://www.ist-winner.org/DeliverableDocuments/D3.4.pdf.Google Scholar
- Z. Fu, P. Zerfos, H. Luo, S. Lu, L. Zhang, and M. Gerla. The impact of multihop wireless channel on tcp throughput and loss. In INFOCOM 2003.Google ScholarCross Ref
- M. Heusse, F. Rousseau, R. Guillier, and A. Duda. Idle sense: an optimal access method for high throughput and fairness in rate diverse wireless lans. In ACM SIGCOMM, 2005. Google ScholarDigital Library
- T. Ho and R. Koetter. Online incremental network coding for multiple unicasts. In DIMACS Working Group on Network Coding, 2005.Google Scholar
- T. Ho, R. Koetter, M. Médard, D. Karger, and M. Effros. The Benefits of Coding over Routing in a Randomized Setting. In ISIT, 2003.Google ScholarCross Ref
- T. Ho, B. Leong, Médard, R. Koetter, Y. Chang, and M. Effros. The Utility of Network Coding in Dynamic Environments. In IWWAN, 2004.Google Scholar
- p. a. IEEE 802.11 WG. Wireless lan medium access control (mac) and physical layer (phy) specifications. Standard Specification,IEEE, 1999.Google Scholar
- S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2003. Google ScholarDigital Library
- A. Kamra, J. Feldman, V. Misra, and D. Rubenstein. Growth codes: Maximizing sensor network data persistence. In ACM SIGCOMM, 2006. Google ScholarDigital Library
- B. Karp. Geographic Routing for Wireless Networks. PhD thesis, Harvard University, 2000. Google ScholarDigital Library
- S. Katti, D. Katabi, W. Hu, H. S. Rahul, and M. Médard. The importance of being opportunistic: Practical network coding for wireless environments, 2005.Google Scholar
- R. Koetter and M. Médard. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003. Google ScholarDigital Library
- E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek. The click modular router. ACM Transactions on Computer Systems, August 2000. Google ScholarDigital Library
- S. R. Li, R. W. Yeung, and N. Cai. Linear network coding. In IEEE Transactions on Information Theory, 2003. Google ScholarDigital Library
- D. S. Lun, M. Médard, R. Koetter, and M. Effros. Further results on coding for reliable communication over packet networks. In IEEE International Symposium on Information Theory (ISIT 05), 2005.Google ScholarCross Ref
- D. S. Lun, N. Ratnakar, R. Koetter, M. Médard, E. Ahmed, and H. Lee. Achieving Minimum-Cost Multicast: A Decentralized Approach Based on Network Coding. In IEEE INFOCOM, 2005.Google ScholarCross Ref
- Internet packet size distributions: Some observations. http://netweb.usc.edu/rsinha/pkt-sizes/.Google Scholar
- V. Paxson and S. Floyd. Wide-area traffic: the failure of poisson modeling. In IEEE/ACM Transactions on Networking, 3(3):226--244, 1995. Google ScholarDigital Library
- A. Ramamoorthy, J. Shi, and R. Wesel. On the capacity of network coding for wireless networks. In 41st Annual Allerton Conference on Communication Control and Computing, Oct. 2003.Google Scholar
- Nokia rooftop wireless routing. White Paper.Google Scholar
- P. Sinha, T. Nandagopal, N. Venkitaraman, R. Sivakumar, and V. Bharghavan. WTCP: A reliable transport protocol for wireless wide-area networks. Wireless Networks, 8(2-3):301--316, 2002. Google ScholarDigital Library
- ttcp. http://ftp.arl.mil/ftp/pub/ttcp/.Google Scholar
- udpgen. http://pdos.csail.mit.edu/click/ex/udpgen.html.Google Scholar
- Wireless Community Network List. http://www.toaster.net/wireless/community.html.Google Scholar
- Y. Wu, P. A. Chou, and S. Y. Kung. Information Exchange in Wireless Networks with Network Coding and Physical-layer Broadcast. MSR-TR-2004-78.Google Scholar
- Z. Li and B. Li. Network Coding in Undirected Networks. In CISS 04, 2004.Google Scholar
- Z. Li and B. Li. Network coding: The case for multiple unicast sessions. In Allerton Conference on Communications, 2004.Google Scholar
Index Terms
- XORs in the air: practical wireless network coding
Recommendations
XORs in the air: practical wireless network coding
Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communicationsThis paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently ...
XORs in the air: practical wireless network coding
This paper proposes COPE, a new architecture for wireless mesh networks. In addition to forwarding packets, routers mix (i.e., code) packets from different sources to increase the information content of each transmission. We show that intelligently ...
TCP CERL: congestion control enhancement over wireless networks
In this paper, we propose and verify a modified version of TCP Reno that we call TCP Congestion Control Enhancement for Random Loss (CERL). We compare the performance of TCP CERL, using simulations conducted in ns-2, to the following other TCP variants: ...
Comments