An algebraic approach to network coding

ABSTRACT

We take a new look at the issue of network capacity. It is shown that network coding is an essential ingredient in achieving the capacity of a network. Building on recent work by Li et al., who examined the network capacity of multicast networks, we extend the network coding framework to arbitrary networks and robust networking. For networks which are restricted to using linear network codes, we find necessary and sufficient conditions for the feasibility of any given set of connections over a given network. We also consider the problem of network recovery for nonergodic link failures. For the multicast setup we prove that there exist coding strategies that provide maximally robust networks and that do not require adaptation of the network interior to the failure pattern in question. The results are derived for both delay-free networks and networks with delays.

REFERENCES

• 1: {1} T. M. Cover, "Comments on broadcast channels," IEEE Trans. Inform. Theory, vol. 44, pp. 2524-2530, Oct. 1998.
• 2: {2} T. M. Cover, "Broadcast channels," IEEE Trans. Inform. Theory, vol. IT-18, pp. 2-14, Jan. 1972.
• 3: {3} T. M. Cover, "An achievable rate region for the broadcast channel," IEEE Trans. Inform. Theory, vol. IT-21, pp. 300-404, July 1975.
• 4: {4} R. Ahlswede, "Multi-way communication channels," in Proc. 1971 IEEE Int. Symp. Information Theory, pp. 23-52.
• 5: {5} H. Liao, "Multiple-access channels," Ph.D. dissertation, Univ. Hawaii, 1972.
• 6: {6} E. Van der Meulen, "Three-terminal communication channels," Adv. Appl. Probabil., vol. 3, pp. 120-154, 1971.
• 7: {7} T. Cover and A. El Gamal, "Capacity theorems for the relay channel," IEEE Trans. Inform. Theory, vol. IT-25, pp. 572-584, Sept. 1979.
• 8: {8} B. Schein and R. Gallager, "The Gaussian parallel relay network," in Proc. 2000 IEEE Int. Symp. Information Theory, p. 22.
• 9: {9} S. Y. R. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Trans. Inform. Theory, vol. 49, p. 371, Feb. 2003.
• 10: {10} R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inform. Theory, vol. 46, pp. 1204-1216, July 2000.
• 11: {11} S.-Y. R. Li and R. W. Yeung, "Network multicast flow via linear coding," in Proc. Int. Symp. Operations Research and its Applications, 1998, pp. 197-211.
• 12: {12} R. W. Yeung, A First Course in Information Theory. Norwood, MA: Kluwer, 2002.
• 13: {13} R. W. Yeung and Z. Zhang, "Distributed source coding for satellite communications," IEEE Trans. Inform. Theory, vol. 45, pp. 1111-1120, May 1999.
• 14: {14} E. Ayanoglu, I. Chih-Lin, R. D. Gitlin, and J. D. Mazo, "Diversity coding: Using error control for self-healing in communication networks," in Proc. IEEE INFOCOM, vol. 1, 1990, pp. 95-104.
• 15: {15} S.-Y. R. Li and R. W. Yeung, "Network information flow--multiple sources," in Proc. 2001 IEEE Int. Symp. Information Theory, p. 102.
• 16: {16} D. P. Bertsekas, Network Optimization: Continuous and Discrete Models. Belmont, MA: Athena Scientific, 1998.
• 17: {17} P. Elias, A. Feinstein, and C. E. Shannon, "A note on the maximum flow through a network," IEEE Trans. Info. Theory, vol. IT-2, pp. 117-119, Dec. 1956.
• 18: {18} W. Fulton, Algebraic Curves. New York: Benjamin, 1969.
• 19: {19} D. Cox, J. Little, and D. O'Shea, Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York: Springer, 1992.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Protocol architecture (OSI model)

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

General Terms:
Design, Performance

Keywords:
algebraic coding, network information theory, network robustness