Network Coding
Contents |
[Ahlswede-Cai-Li-Yeung-2000 (doi) .]
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung,
“Network Information Flow”,
IEEE Transactions on Information Theory,
vol.46 iss.4, Jul. 2000, pp. 1204–1216
ResiliNets Keywords: Redundant routing, network coding
Keywords: Diversity coding, multicast, network coding, switching, multiterminal source coding
Abstract: “We introduce a new class of problems called network information flow which is inspired by computer network applications. Consider a point-to-point communication network on which a number of information sources are to be mulitcast to certain sets of destinations. We assume that the information sources are mutually independent. The problem is to characterize the admissible coding rate region. This model subsumes all previously studied models along the same line. In this paper, we study the problem with one information source, and we have obtained a simple characterization of the admissible coding rate region. Our result can be regarded as the Max-flow Min-cut Theorem for network information flow. Contrary to one’s intuition, our work reveals that it is in general not optimal to regard the information to be multicast as a ‘fluid’ which can simply be routed or replicated. Rather, by employing coding at the nodes, which we refer to as network coding, bandwidth can in general be saved. This finding may have significant impact on future design of switching systems.”
Notes: The first paper on network coding; very analytical treatment.
[Fragouli-LeBoudec-Widmer-2006 (doi) .]
Christina Fragouli, Jean-Yves Le Boudec, and Jörg Widmer,
“Network Coding: an Instant Primer”,
ACM SIGCOMM Computer Communication Review,
vol.36 iss.1, Jan. 2006, pp. 63–68
ResiliNets Keywords: Redundant routing, network coding
Keywords: Network coding
Abstract: “Network coding is a new research area that may have interesting applications in practical networking systems. With network coding, intermediate nodes may send out packets that are linear combinations of previously received information. There are two main benefits of this approach: potential throughput improvements and a high degree of robustness. Robustness translates into loss resilience and facilitates the design of simple distributed algorithms that perform well, even if decisions are based only on partial information. This paper is an instant primer on network coding: we explain what network coding does and how it does it. We also discuss the implications of theoretical results on network coding for realistic settings and show how network coding can be used in practice.”
Notes: Less mathematical than the original network coding paper.
[LeBoudec-Widmer-2005 (doi) .]
Jörg Widmer and Jean-Yves Le Boudec,
“Network Coding for Efficient Communication in Extreme Networks”,
Proceedings 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN 2005),
Philadelphia, August 2005, ACM Press, New York, pp. 284–291
ResiliNets Keywords: Redundant routing, network coding
Keywords: Network coding
Abstract: “ Some forms of ad-hoc networks need to operate in extremely performance-challenged environments where end-to-end connectivity is rare. Such environments can be found for example in very sparse mobile networks where nodes "meet" only occasionally and are able to exchange information, or in wireless sensor networks where nodes sleep most of the time to conserve energy. Forwarding mechanisms in such networks usually resort to some form of intelligent flooding, as for example in probabilistic routing.We propose a communication algorithm that significantly reduces the overhead of probabilistic routing algorithms, making it a suitable building block for a delay-tolerant network architecture. Our forwarding scheme is based on network coding. Nodes do not simply forward packets they overhear but may send out information that is coded over the contents of several packets they received. We show by simulation that this algorithm achieves the reliability and robustness of flooding at a small fraction of the overhead. ”
Notes:
Network Coding Web Page
Notes: Web page with brief overview of network coding, bibliography, and tutorial notes.
