article

XORs in the air: practical wireless network coding

Authors:

Hariharan Rahul,

Muriel Médard,

Jon CrowcroftAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 16, Issue 3

Pages 497 - 510

https://doi.org/10.1109/TNET.2008.923722

Published: 01 June 2008 Publication History

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 using COPE at the forwarding layer, without modifying routing and higher layers, increases network throughput. The gains vary from a few percent to several folds depending on the traffic pattern, congestion level, and transport protocol.

References

[1]

D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris, "Link-level measurements from an 802.11b mesh network," in Proc. ACM SIG-COMM , Portland, OR, Aug. 2004, pp. 121-132.

[2]

Y. Wu, P. A. Chou, and S. Y. Kung, "Information exchange in wireless networks with network coding and physical-layer broadcast," Microsoft Corp., Redmond, WA, Tech. Rep. MSR-TR-2004-78.

[3]

T. Ho and R. Koetter, "Online incremental network coding for multiple unicasts," in DIMACS Working Group on Network Coding, Rutgers Univ., Piscataway, NJ, Jan. 2005.

[4]

R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.

[5]

S. R. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371-381, Feb. 2003.

[6]

R. Koetter and M. Médard, "An algebraic approach to network coding," IEEE/ACM Trans. Networking, vol. 11, no. 5, pp. 782-795, Oct. 2003.

[7]

T. Ho, M. Médard, J. Shi, M. Effros, and D. Karger, "On randomized network coding," presented at the 41st Annu. Allerton Conf. Communication, Control, and Computing, Monicello, IL, Oct. 2003.

[8]

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," presented at the 2005 Int. Workshop on Wireless Ad-hoc Networks (IWWAN), London, U.K., May 2005.

[9]

Y. Wu, P. Chou, Q. Zhang, K. Jain, W. Zhu, and S. Kung, "Network planning in wireless ad hoc networks: a cross-layer approach," IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 136-150, Jan. 2005.

[10]

Y. Wu, P. A. Chou, and S.-Y. Kung, "Minimum-energy multicast in mobile ad hoc networks using network coding," IEEE Trans. Commun., vol. 53, no. 11, pp. 1906-1918, Nov. 2005.

[11]

J. Widmer, C. Fragouli, and J. LeBoudec, "Energy-efficient broadcasting in wireless ad-hoc networks," presented at the NetCod 2005, Riva del Garda, Italy, Apr. 2005.

[12]

Y. Sagduyu and A. Ephremides, "Joint scheduling and wireless network coding," presented at the NetCod 2005, Riva del Garda, Italy, Apr. 2005.

[13]

Y. Chen, S. Kishore, and J. Li, "Wireless diversity through network coding," in Proc. WCNC, 2006, vol. 3, pp. 1681-1686.

[14]

X. Bao and J. Li, "On the outage properties of adaptive network coded cooperation (ANCC) in large wireless networks," presented at the ICASSP, Toulouse, France, May 2006.

[15]

A. A. Hamra, C. Barakat, and T. Turletti, "Network coding for wireless mesh networks: A case study," presented at the WoWMoM Conf., Buffalo, NY, Jun. 2006, 9 pp.

[16]

S. Chachulski, M. Jennings, S. Katti, and D. Katabi, "Trading structure for randomness in wireless opportunistic routing," in Proc. ACM SIG-COMM. , Kyoto, Japan, Aug. 2007, pp. 169-180.

[17]

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 Proc. IEEE INFOCOM, Miami, FL, Mar. 2005, pp. 1607-1617.

[18]

R. Dougherty, C. Freiling, and K. Zeger, "Insufficiency of linear coding in network information flow," IEEE Trans. Inf. Theory, vol. 51, no. 8, pp. 2745-2759, Aug. 2005.

[19]

Z. Li and B. Li, "Network coding: The case for multiple unicast sessions," presented at the 42nd Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, 2004.

[20]

X. Bao and J. Li, "Matching code-on-graph with network-on-graph: Adaptive network coding for wireless relay networks," presented at the 43rd Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, 2005.

[21]

Y. Sagduyu and A. Ephremides, "Network coding in wireless queueing networks: Tandem network case," in Proc. ISIT, Jul. 2006, pp. 192-196.

[22]

Y. Sagduyu and A. Ephremides, "Crosslayer design for distributed mac and network coding in wireless ad hoc networks," in Proc. ISIT, Sep. 2005, pp. 1863-1867.

[23]

S. Katti, H. S. Rahul, W. Hu, D. Katabi, M. Médard, and J. Crowcroft, "XORs in the air: Practical wireless network coding," in Proc. ACM SIGCOMM, Pisa, Italy, Aug. 2006, pp. 243-254.

[24]

Y. Wu, J. Padhye, R. Chandra, V. Padmanabhan, and P. A. Chou, "The local mixing problem," presented at the Information Theory and Applications Workshop, San Diego, CA, Feb. 2006.

[25]

S. Sengupta, S. Rayanchu, and S. Banerjee, "An analysis of wireless network coding for unicast sessions: The case for codingaware routing," in Proc. IEEE INFOCOM, May 2007, pp. 1028-1036.

[26]

J. Liu, D. Goeckel, and D. Towsley, "Bounds on the gain of network coding and broadcasting in wireless networks," in Proc. IEEE IN-FOCOM , May 2007, pp. 724-732.

[27]

P. Popovski and H. Yomo, "Bi-directional amplification of throughput in a wireless multi-hop network," in Proc. IEEE 63rd Vehicular Technology Conf. (VTC 2006-Spring), 2006, pp. 588-593.

[28]

T. Aulin and M. Xiao, "A physical layer aspect of network coding with statistically independent noisy channels," in Proc. IEEE Int. Conf. Communications (ICC), Jun. 2006, vol. 9, pp. 3996-4001.

[29]

S. Zhang, S. C. Liew, and P. P. Lam, "Physical-layer network coding," presented at the ACM MobiCom, Los Angeles, CA, Sep. 2006.

[30]

S. Katti, S. Gollakota, and D. Katabi, "Embracing wireless interference: Analog network coding," in Proc. ACM SIGCOMM, Kyoto, Japan, Aug. 2007, pp. 397-408.

[31]

D. De Couto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless routing," presented at the ACM Mo-biCom, San Diego, CA, Sep. 2003.

[32]

J. Bicket, D. Aguayo, S. Biswas, and R. Morris, "Architecture and evaluation of an unplanned 802.11b mesh network," presented at the ACM MobiCom, Cologne, Germany, Aug. 2005.

[33]

R. Draves, J. Padhye, and B. Zill, "Comparison of routing metrics for multi-hop wireless networks," in Proc. ACM SIGCOMM, Portland, OR, Aug. 2004, pp. 133-144.

[34]

P. Sinha, T. Nandagopal, N. Venkitaraman, R. Sivakumar, and V. Bharghavan, "WTCP: A reliable transport protocol for wireless wide-area networks," Wireless Networks, vol. 8, no. 2-3, pp. 301-316, 2002.

[35]

S. Biswas and R. Morris, "Opportunistic routing in multi-hop wireless networks," in Proc. ACM SIGCOMM, Philadelphia, PA, Aug. 2005, pp. 133-144.

[36]

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 Proc. ACM SIGCOMM, Philadelphia, PA, Aug. 2005, pp. 121-132.

[37]

Z. Li and B. Li, "Network coding in undirected networks," presented at the 38th Annu. Conf. Information Sciences and Systems (CISS 2004), Princeton, NJ, Mar. 2004.

[38]

R. Sinha, C. Papadopoulos, and J. Heidemann, "Internet packet size distributions: some observations," USC/Information Sciences Inst. {Online}. Available: http://netweb.usc.edu/~rsinha/pkt-sizes/

[39]

H. Balakrishnan, V. N. Padmanabhan, S. Seshan, and R. H. Katz, "A comparison of mechanisms for improving TCP performance over wireless links," IEEE/ACM Trans. Networking, vol. 5, no. 6, pp. 756-769, Dec. 1997.

[40]

Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Standard Specification, IEEE p. a. IEEE 802.11 WG, 1999.

[41]

E. Kohler, R. Morris, B. Chen, J. Jannotti, and M. F. Kaashoek, "The click modular router," ACM Trans. Comput. Syst., vol. 18, no. 3, Aug. 2000.

[42]

Udpgen. MIT. {Online}. Available: http://pdos.csail.mit.edu/click/ex/ udpgen.html

[43]

TTCP. Army Research Lab. {Online}. Available: http://ftp.arl.mil/ftp/ pub/ttcp/

[44]

V. Paxson and S. Floyd, "Wide-area traffic: The failure of Poisson modeling," IEEE/ACM Trans. Networking, vol. 3, no. 3, pp. 226-244, Jun. 1995.

[45]

M. E. Crovella, M. S. Taqqu, and A. Bestavros, "Heavy-tailed probability distributions in the world wide web," in A Practical Guide To Heavy Tails, R. J. Adler, R. E. Feldman, and M. S. Taqqu, Eds. New York: Chapman and Hall, 1998, ch. 1, pp. 3-26.

[46]

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 Proc. IEEE INFOCOM, 2003, vol. 3, pp. 1744-1753.

[47]

C. C. cheng, E. Seo, H. Kim, and H. Luo, "Self-learning collision avoidance for wireless networks," in Proc. IEEE INFOCOM, 2006, pp. 1-12.

[48]

P. Bhagwat, B. Raman, and D. Sanghi, "Turning 802.11 inside-out," presented at the HotNets-II, Cambridge, MA, 2003.

[49]

Nokia Rooftop Wireless Routing. Nokia, White Paper.

[50]

A. Adinoyi et al., "Definition and assessment of relay based cellular deployment concepts for future radio scenarios considering 1st protocol characteristics," chapter 5. IST-2003-507581 WINNER. {Online}. Available: https://www.ist-winner.org/DeliverableDocu-ments/D3.4.pdf

[51]

A. Kamra, V. Misra, J. Feldman, and D. Rubenstein, "Growth codes: Maximizing sensor network data persistence," in Proc. ACM SIG-COMM , Pisa, Italy, Aug. 2006, pp. 255-266.

Cited By

Mei Z(2025)A Novel Method to Solve the Maximum Weight Clique Problem for Instantly Decodable Network CodingIEEE Transactions on Mobile Computing10.1109/TMC.2024.348972424:3(2181-2192)Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3489724
Zhao YQu YXiang YUddin MPeng DGao L(2024)A Comprehensive Survey on Edge Data Integrity Verification: Fundamentals and Future TrendsACM Computing Surveys10.1145/368027757:1(1-34)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3680277
Chukhno NChukhno OMoltchanov DPizzi SGaydamaka ASamuylov AMolinaro AKoucheryavy YIera AAraniti G(2024)Models, Methods, and Solutions for Multicasting in 5G/6G mmWave and Sub-THz SystemsIEEE Communications Surveys & Tutorials10.1109/COMST.2023.331935426:1(119-159)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/COMST.2023.3319354
Show More Cited By

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 communications

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 ...
XORs in the air: practical wireless network coding
SIGCOMM '06: Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications

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 ...
INCP: Practical Wireless Network Coding for Multiple Unicast Sessions

In this paper, we propose INCP, inter-flow network coding protocol, for wireless mesh networks. INCP is designed with the concept of Layered Approach. It acts as a distinct layer above the MAC and has close cooperation with IP layer. INCP exploits the ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 16, Issue 3

June 2008

249 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2008

Published in TON Volume 16, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

211
Total Citations
View Citations
3,475
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mei Z(2025)A Novel Method to Solve the Maximum Weight Clique Problem for Instantly Decodable Network CodingIEEE Transactions on Mobile Computing10.1109/TMC.2024.348972424:3(2181-2192)Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1109/TMC.2024.3489724
Zhao YQu YXiang YUddin MPeng DGao L(2024)A Comprehensive Survey on Edge Data Integrity Verification: Fundamentals and Future TrendsACM Computing Surveys10.1145/368027757:1(1-34)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3680277
Chukhno NChukhno OMoltchanov DPizzi SGaydamaka ASamuylov AMolinaro AKoucheryavy YIera AAraniti G(2024)Models, Methods, and Solutions for Multicasting in 5G/6G mmWave and Sub-THz SystemsIEEE Communications Surveys & Tutorials10.1109/COMST.2023.331935426:1(119-159)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/COMST.2023.3319354
Xie XHua CHong JXu W(2023)Optimal Power Control and CSI Acquisition for Over-the-Air Computation in OFDM SystemIEEE Transactions on Wireless Communications10.1109/TWC.2023.333332623:6(6533-6545)Online publication date: 23-Nov-2023
https://dl.acm.org/doi/10.1109/TWC.2023.3333326
Graham MGanesh APiechocki R(2023)Low Latency Allcast Over Broadcast Erasure ChannelsIEEE Transactions on Information Theory10.1109/TIT.2022.321977369:3(1604-1617)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TIT.2022.3219773
Şahin AYang R(2023)A Survey on Over-the-Air ComputationIEEE Communications Surveys & Tutorials10.1109/COMST.2023.326464925:3(1877-1908)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1109/COMST.2023.3264649
Abdullah SAsghar MFleury MMushtaq Z(2023)Network-Coding-Enabled and QoS-Aware Message Delivery for Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-023-10613-y132:1(329-359)Online publication date: 20-Jul-2023
https://dl.acm.org/doi/10.1007/s11277-023-10613-y
Huang WLi XLiang Y(2022)Probabilistic cooperative coded forwarding for broadcast transmissions in industrial mobile edge communicationsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-022-02132-42022:1Online publication date: 13-Jun-2022
https://dl.acm.org/doi/10.1186/s13638-022-02132-4
Tata CKadoch M(2022)Network Coding-Based D2D Transmission for Public Safety Networks over LTE HetNets and 5G NetworksWireless Communications & Mobile Computing10.1155/2022/88897182022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/8889718
Li X(2022)An English Translation Quality Evaluation Model Integrating Knowledge Transfer and Wireless NetworkMobile Information Systems10.1155/2022/20864862022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/2086486
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents