The multicast capacity of deterministic relay networks with no interference

ABSTRACT

The multicast capacity is determined for networks that have deterministic channels with broadcasting at the transmitters and no interference at the receivers. The multicast capacity is shown to have a cut-set interpretation. It is further shown that one cannot always layer channel and network coding in such networks. The proof of the latter result partially generalizes to discrete memoryless broadcast channels and is used to bound the common rate for problems where one achieves a cut bound on throughput.

REFERENCES

• 1: [1] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 000.
• 2: [2] K. Marton, "A coding theorem for the discrete memoryless broadcast channel," IEEE Trans. Inf. Theory, vol. IT-25, no. 3, pp. 306-311, May 1979.
• 3: [3] M. R. Aref, "Information Flow in Relay Networks," Ph.D. dissertation, Stanford Univ., Stanford, CA, 1980.
• 4: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 5: [5] S. P. Borade, "Network information flow: Limits and achievability," in Proc. 2002 IEEE Int. Symp. Information Theory, Lausanne, Switzerland, Jun./Jul. 2002, p. 139.
• 6: [6] C. E. Shannon, "Two-way communication channels," in Proc. 4th Berkeley Symp. Mathematics and Statistical Probability, vol. 1, 1961, pp. 611-644.
• 7: [7] G. Kramer and S. A. Savari, "On networks of two-way channels," in Proc. DIMACS Workshop on Algebraic Coding Theory and Information Theory, vol. 68, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, A. Ashikhmin and A. Barg, Eds., Rutgers University, Piscataway, NJ, Dec. 2003, pp. 133-143.
• 8: Robert G. Gallager, Information Theory and Reliable Communication, John Wiley & Sons, Inc., New York, NY, 1968
• 9: [9] A. Orlitsky and J. R. Roche, "Coding for computing," IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 903-917, Mar. 2001.
• 10: Te Sun Han , Max H. M. Costa, Broadcast channels with arbitrarily correlated sources, IEEE Transactions on Information Theory, v.33 n.5, p.641-650, September 1, 1987 [doi>10.1109/TIT.1987.1057353]
• 11: [11] S. Jaggi, P. Sanders, P. Chou, M. Effros, S. Egner, K. Jain, and L. M. G. M. Tolhuizen, "Polynomial time algorithms for multicast network code construction," IEEE Trans. Inf. Theory, vol. 51, no. 6, pp. 1973-1982, Jun. 2005.
• 12: [12] T. Ho, M. Médard, J. Shi, M. Effros, and D. Karger, "On randomized network coding," in Proc. 41st Annu. Allerton Conf. Communication, Control, CompUTING, Monticello, IL, Oct. 2003, pp. 11-20.
• 13: Imre Csiszar , Janos G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Inc., Orlando, FL, 1982
• 14: [14] S. I. Gel'fand and M. S. Pinsker, "Capacity of a broadcast channel with one deterministic component," Probl. Pered. Inform., vol. 16, no. 1, pp. 24-34, Jan./Mar. 1980.
• 15: [15] T. S. Han, "The capacity region for the deterministic broadcast channel with a common message," IEEE Trans. Inf. Theory, vol. IT-27, no. 1, pp. 122-125, Jan. 1980.
• 16: [16] H. Sato, "An outer bound to the capacity region of broadcast channels," IEEE Trans. Inf. Theory, vol. IT-24, no. 3, pp. 374-377, May 1978.
• 17: [17] G. Caire and S. Shamai (Shitz), "On the achievable throughput of a multi-antenna Gaussian broadcast channel," IEEE Trans. Inf. Theory, vol. 49, no. 7, pp. 1691-1706, Jul. 2003.
• 18: [18] P. Viswanath and D. N. C. Tse, "Sum capacity of the vector Gaussian broadcast channel and uplink-downlink duality," IEEE Trans. Inf. Theory, vol. 49, no. 8, pp. 1912-1921, Aug. 2003.
• 19: [19] S. Vishwanath, N. Jindal, and A. Goldsmith, "Duality, achievable rates, and sum-rate capacity of Gaussian MIMO broadcast channels," IEEE Trans. Inf. Theory, vol. 49, no. 10, pp. 2658-2668, Oct. 2003.
• 20: [20] W. Yu and J. M. Cioffi, "Sum capacity of Gaussian vector broadcast channels," IEEE Trans. Inf. Theory, vol. 50, no. 9, pp. 1875-1892, Sep. 2004.
• 21: [21] R. Gowaikar, A. F. Dana, R. Palanki, B. Hassibi, and M. Effros, "On the capacity of wireless erasure networks," in Proc. 2004 IEEE Int. Symp. Information Theory, Chicago, IL, Jun./Jul. 2004, p. 401.
• 22: [22] D. S. Lun, M. Médard, and M. Effros, "On coding for reliable communication over packet networks," in Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, Sep./Oct. 2004, pp. 20-29.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

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

General Terms:
Algorithms, Design, Performance

Keywords:
broadcasting, capacity, multicast, network coding, relaying