More Web Proxy on the site http://driver.im/

research-article

XORs in the past and future

Authors:

Muriel Médard,

Hariharan Rahul,

Jon CrowcroftAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 49, Issue 5

Pages 77 - 81

https://doi.org/10.1145/3371934.3371959

Published: 08 November 2019 Publication History

Abstract

While placing the paper "XORs in the Air" in the context of the theoretical and practical understanding of network coding, we present a view of the progress of the field of network coding, In particular, we examine the interplay of theory and practice in the field.

References

[1]

http://www.steinwurf.com/products/kodo.html.

[2]

S. Acedański, S. Deb, M. Médard, and R. Koetter. 2005. How good is random linear coding based distributed network storage?. In Proc. 1st Workshop on Network Coding, Theory, and Applications (Netcod'05).

[3]

R. Ahlswede, Ning Cai, S.-Y.R. Li, and R.W. Yeung. 2000. Network information flow. Information Theory, IEEE Transactions on 46, 4 (2000), 1204--1216.

Digital Library

[4]

R. Ahlswede, Cai Ning, S-Y.R Li, and R.W. Yeung. 2000. Network information flow. 46, 4 (July 2000), 1204--1216.

[5]

P. J. Braun, D. Malak, M. Medard, and P. Ekler. 2019. Multi-Source Coded Downloads. In ICC 2019 - 2019 IEEE International Conference on Communications (ICC). 1--7.

[6]

J. Cloud, L. M. Zeger, and M. Medard. 2012. MAC Centered Cooperation --- Synergistic Design of Network Coding, Multi-Packet Reception, and Improved Fairness to Increase Network Throughput. IEEE Journal on Selected Areas in Communications 30, 2 (February 2012), 341--349.

[7]

Y. Cui, M. Médard, E. Yeh, D. Leith, and K. R. Duffy. 2018. Optimization-Based Linear Network Coding for General Connections of Continuous Flows. IEEE/ACM Transactions on Networking 26, 5 (Oct 2018), 2033--2047.

Digital Library

[8]

Y. Cui, M. Médard, E. Yeh, D. Leith, F. Lai, and K. R. Duffy. 2017. A Linear Network Code Construction for General Integer Connections Based on the Constraint Satisfaction Problem. IEEE/ACM Transactions on Networking 25, 6 (Dec 2017), 3441--3454.

Digital Library

[9]

E. Erez, M. Kim, Y. Xu, E. M. Yeh, and M. Médard. 2014. Deterministic Network Model Revisited: An Algebraic Network Coding Approach. IEEE Transactions on Information Theory 60, 8 (Aug 2014), 4867--4879.

[10]

F. Gabriel, S. Wunderlich, S. Pandi, F. H. P. Fitzek, and M. Reisslein. 2018. Caterpillar RLNC With Feedback (CRLNC-FB): Reducing Delay in Selective Repeat ARQ Through Coding. IEEE Access 6 (2018), 44787--44802.

[11]

J. Heide, S. Shi, K. Fouli, M. Médard, and V. Chook. [n. d.]. Random Linear Network Coding (RLNC): Background and Practical Considerations, https://datatracker.ietf.org/doc/draft-heide-nwcrg-rlnc-background/.

[12]

J. Heide, S. Shi, K. Fouli, M. Médard, and V. Chook. [n. d.]. Random Linear Network Coding (RLNC)-Based Symbol Representation, https://tools.ietf.org/html/draft-heide-nwcrg-rlnc-02.

[13]

C. Hellge and M. Medard. 2016. Multi-code Distributed Storage. In 2016 IEEE 9th International Conference on Cloud Computing (CLOUD). 839--842.

[14]

T. Ho, M. Médard, R. Koetter, D.R. Karger, M. Effros, Jun Shi, and B. Leong. 2006. A Random Linear Network Coding Approach to Multicast. IEEE Transactions on Information Theory 52, 10 (Oct. 2006), 4413 --4430.

Digital Library

[15]

M. Karzand, D. J. Leith, J. Cloud, and M. Médard. 2017. Design of FEC for Low Delay in 5G. IEEE Journal on Selected Areas in Communications 35, 8 (Aug 2017), 1783--1793.

[16]

Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Médard, and Jon Crowcroft. 2006. XORs in the Air: Practical Wireless Network Coding. In Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM '06). ACM, New York, NY, USA, 243--254.

Digital Library

[17]

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. 2008. XORs in the Air: Practical Wireless Network Coding. IEEE/ACM Transactions on Networking 16, 3 (June 2008), 497--510.

Digital Library

[18]

R. Koetter and M. Medard. 2001. An algebraic approach to network coding. In Proceedings. 2001 IEEE International Symposium on Information Theory (IEEE Cat. No.01CH37252). 104--.

[19]

R. Koetter and M. Medard. 2002. Beyond routing: an algebraic approach to network coding. In Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1. 122--130 vol. 1.

[20]

R. Koetter and M. Médard. 2003. An algebraic approach to network coding. IEEE/ACM Transactions on Networking 11, 5 (Oct. 2003), 782 -- 795.

Digital Library

[21]

Desmond Lun, Niranjan Ratnakar, Muriel Médard, Ralf Koetter, David R. Karger, Tracey H, Ebad Amhed, and Fang Zhao. 2006. Minimum-cost multicast over coded packet networks. 52, 6 (June 2006), 2608--2623.

[22]

D. S. Lun, M. Médard, T. Ho, and R. Koetter. 2004. Network coding with a cost criterion. In International Symposium on Information Theory and its Applications (ISITA).

[23]

D. S Lun, P. Pakzad, C. Fragouli, M. Médard, and R. Koetter. 2006. An Analysis of Finite-memory Random Linear Coding on Packet Streams. In 2006 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks. IEEE, 1-- 6.

[24]

D. Malak, M. Médard, and E. M. Yeh. 2018. ARQ with Cumulative Feedback to Compensate for Burst Errors. In 2018 IEEE Global Communications Conference (GLOBECOM). 1--6.

[25]

D. Malak, M. Médard, and E. M. Yeh. 2019. Tiny Codes for Guaranteeable Delay. IEEE Journal on Selected Areas in Communications 37, 4 (April 2019), 809--825.

[26]

D. Malak, A. Schneuwly, M. Médard, and E. Yeh. 2019. Delay-Aware Coding in Multi-Hop Line Networks. In 2019 IEEE 5th World Forum on Internet of Things (WF-IoT). 650--655.

[27]

M. Medard, F. H. P. Fitzek, M. Montpetit, and C. Rosenberg. 2014. Network coding mythbusting: why it is not about butterflies anymore. IEEE Communications Magazine 52, 7 (July 2014), 177--183.

[28]

J. Neu and M. Medard. 2019. Babel Storage: Uncoordinated Content Delivery from Multiple Coded Storage Systems. IEEE Globecom (2019).

[29]

S. Pandi, S. Wunderlich, and F. H. P. Fitzek. 2018. Reliable low latency wireless mesh networks --- From Myth to reality. In 2018 15th IEEE Annual Consumer Communications Networking Conference (CCNC). 1--2.

[30]

Nikolaos Papanikos and Evangelos Papapetrou. 2014. Deterministic Broadcasting and Random Linear Network Coding in Mobile Ad Hoc Networks. CoRR abs/1411.4465 (2014). arXiv:1411.4465 http://arxiv.org/abs/1411.4465

[31]

V. Roca. [n. d.]. The Sliding Window Random Linear Code (RLC) Forward Erasure Correction (FEC) Scheme for FECFRAME, https://tools.ietf.org/html/draft-roca-tsvwg-rlc-fec-scheme-01.

[32]

C. W. Sørensen, D. E. Lucani, and M. Médard. 2017. On network coded filesystem shim: Over-the-top multipath multi-source made easy. In 2017 IEEE International Conference on Communications (ICC). 1--7.

[33]

J.K. Sundararajan, D. Shah, M. Médard, S. Jakubczak, M. Mitzenmacher, and J. Barros. 2011. Network Coding Meets TCP: Theory and Implementation. Proc. IEEE 99, 3 (March 2011), 490--512.

[34]

J.K. Sundararajan, D. Shah, M. Médard, M. Mitzenmacher, and J. Barros. 2009. Network Coding Meets TCP. In INFOCOM 2009, IEEE. 280--288.

[35]

J. K Sundararajan, P. Sadeghi, and M. Médard. 2009. A feedback-based adaptive broadcast coding scheme for reducing in-order delivery delay. In Workshop on Network Coding, Theory, and Applications, 2009. NetCod '09. IEEE, 1--6.

[36]

M. Talas, R. Rausch, and N. Barhoum. 2018. New York City Pilot Acquisition and Installation Experiences. (2018).

[37]

F. Tesema and V. Pauli. 2018. Layer 2 FEC in 5G Broadcast / Multicast Networks, http://nomor.de/wp-content/uploads/2018/09/Nomor_WhitePaper_2018_FT_VP_RAN_2nd_layer_FEC_v3.pdf. (2018).

[38]

F. Tesema and V. Pauli. 2019. Coordinated Link Adaptation and Higher Layer Error Correction for 5G Broadcast / Multicast, http://nomor.de/wp-content/uploads/2019/07/white_paper_coord_la_and_ec.pdf. (2019).

[39]

S. Wunderlich, F. Gabriel, S. Pandi, and F. H. P. Fitzek. 2017. We don't need no generation - a practical approach to sliding window RLNC. In 2017 Wireless Days. 218--223.

[40]

S. Wunderlich, F. Gabriel, S. Pandi, F. H. P. Fitzek, and M. Reisslein. 2017. Caterpillar RLNC (CRLNC): A Practical Finite Sliding Window RLNC Approach. IEEE Access 5 (2017), 20183--20197.

[41]

Weifei Zeng, C.T.K. Ng, and M. Médard. 2012. Joint coding and scheduling optimization in wireless systems with varying delay sensitivities. In Sensor, Mesh and Ad Hoc Communications and Networks (SECON), 2012 9th Annual IEEE Communications Society Conference on. 416--424.

[42]

F. Zhao and M. Médard. 2010. On analyzing and improving COPE performance. In 2010 Information Theory and Applications Workshop (ITA). 1--6.

[43]

F. Zhao, M. Médard, M. Hundebøll, J. Ledet-Pedersen, S. A. Rein, and F. H. P. Fitzek. 2012. Comparison of analytical and measured performance results on network coding in IEEE 802.11 ad-hoc networks. In 2012 International Symposium on Network Coding (NetCod). 43--48.

Cited By

Michel FCohen AMalak DDe Coninck QMédard MBonaventure O(2023)FlEC: Enhancing QUIC With Application-Tailored Reliability MechanismsIEEE/ACM Transactions on Networking10.1109/TNET.2022.319561131:2(606-619)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TNET.2022.3195611
Kaisina IAbilov AChunaev AAiman Al Akkad MKhvorenkov V(2020)Analysis Methods for Improving Quality of Service Metrics in Flying Ad Hoc Networks2020 Moscow Workshop on Electronic and Networking Technologies (MWENT)10.1109/MWENT47943.2020.9067430(1-6)Online publication date: Mar-2020
https://doi.org/10.1109/MWENT47943.2020.9067430
Gao RLi YWang JQuek T(2020)Dynamic Sparse Coded Multi-Hop Transmissions Using Reinforcement LearningIEEE Communications Letters10.1109/LCOMM.2020.300534924:10(2206-2210)Online publication date: Oct-2020
https://doi.org/10.1109/LCOMM.2020.3005349

Index Terms

XORs in the past and future
1. Mathematics of computing
  1. Information theory
    1. Coding theory
2. Networks
  1. Network properties
    1. Network reliability
      1. Error detection and error correction

Recommendations

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 ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 49, Issue 5

October 2019

114 pages

ISSN:0146-4833

DOI:10.1145/3371934

Editor:
Olivier Bonaventure
UCLouvain, Louvain-la-Neuve, Belgium

Issue’s Table of Contents

Copyright © 2019 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 November 2019

Published in SIGCOMM-CCR Volume 49, Issue 5

Check for updates

Author Tag

network coding

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
263
Total Downloads

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

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Michel FCohen AMalak DDe Coninck QMédard MBonaventure O(2023)FlEC: Enhancing QUIC With Application-Tailored Reliability MechanismsIEEE/ACM Transactions on Networking10.1109/TNET.2022.319561131:2(606-619)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TNET.2022.3195611
Kaisina IAbilov AChunaev AAiman Al Akkad MKhvorenkov V(2020)Analysis Methods for Improving Quality of Service Metrics in Flying Ad Hoc Networks2020 Moscow Workshop on Electronic and Networking Technologies (MWENT)10.1109/MWENT47943.2020.9067430(1-6)Online publication date: Mar-2020
https://doi.org/10.1109/MWENT47943.2020.9067430
Gao RLi YWang JQuek T(2020)Dynamic Sparse Coded Multi-Hop Transmissions Using Reinforcement LearningIEEE Communications Letters10.1109/LCOMM.2020.300534924:10(2206-2210)Online publication date: Oct-2020
https://doi.org/10.1109/LCOMM.2020.3005349

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents