ADVERTISEMENT

A Brief History of Network Coding

The entries below include some highlights; see "More to Explore" for related references. A fuller bibliography is at www.ifp.uiuc.edu/¿koetter/NWC/ --M.E., R.K. and M.M.

2000: Concept introduced. In a landmark paper, Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li and Raymond W. Yeung showed the potential power of network coding in multicast networks, where all receivers get identical information. They proved that good (informative) codes exist, although they did not describe a method for designing them.

2003: Important steps taken toward practical implementation. Li, Yeung and Cai showed network coding for multicast networks can rely on mathematical functions involving only addition and multiplication, which reduces the complexity of designing codes. And two of us (Koetter and Médard) introduced a powerful algebraic framework for analyzing coding approaches and simplifying code design.

2005-2006: Valuable design algorithms published. Sidharth Jaggi, then at Caltech, with Peter Sanders of the University of Karlsruhe in Germany, one of us (Effros) and collaborators and, separately, Tracey Ho of Caltech, with the three of us and others, published low-complexity algorithms for designing the functions used by each node in a multicast network. The first paper gave a systematic approach for designing functions; the second showed that choosing functions randomly and independently for each node should work just as well. (Early versions of both contributions were presented at a conference in 2003.)

2006: Applications for wireless networks explored. At a conference in 2006, Christina Fragouli of the École Polytechnique Fédérale de Lausanne in Switzerland and collaborators demonstrated the potential benefits of network coding for wireless applications and characterized scenarios in which the approach would be particularly helpful.

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Dinosaurs

Get Total Access to our Digital Anthology

1,200 Articles

Order Now - Just $39! >

X

Email this Article

X