Network coding: does the model need tuning?

ABSTRACT

We consider the general network information flow problem, which was introduced by Ahlswede et. al[1]. We show a periodicity effect: for every integer m ≥ 2, there exists an instance of the network information ow problem that admits a solution if and only if the alphabet size is a perfect m^th power. Building on this result, we construct an instance with O(m) messages and O(m) nodes that admits a solution if and only if the alphabet size is an enormous 2^exp(Ω(m1/3)). In other words, if we regard each message as a length-k bit string, then k must be exponential in the size of the network. For this same instance, we show that if edge capacities are slightly increased, then there is a solution with a modest alphabet size of O(2^m). In light of these results, we suggest that a more appropriate model would assume that the network operates at slightly under capacity.

REFERENCES

• 1: Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, and Raymond W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204--1216, July 2000.
• 2: Yu. D. Burago and V. A. Zalgaller. Geometric inequalities. In Grundlehren der mathematischen Wiseen-chaften. Spinger-Verlag, 1988. Number 285.
• 3: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 4: R. Dougherty, C. Freiling, and K. Zeger. Linearity and solvability in multicast networks, December 2003.
• 5: R. Dougherty, C. Freiling, and K. Zeger. Insufficiency of linear coding in network information flow, Febuary 2004.
• 6: G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers, 5th Edition. Clarendon Press, Oxford, England, 1979.
• 7: Sidharth Jaggi, Peter Sanders, Philip A. Chou, Michelle Effros, Sebastian Egner, Kamal Jain, and Ludo Tolhuizen. Polynomial time algorithms for multicast network code construction, July 2003. Submitted to IEEE Transactions on Information Theory.
• 8: Ralf Koetter and Muriel Medard. Beyond routing: An algebraic approach to network coding. In INFOCOM, 2002.
• 9: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 10: April Rasala Lehman , Eric Lehman, Complexity classification of network information flow problems, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 11: Shuo-Yen Robert Li, Raymond Yeung, and Nig Cai. Linear network coding. IEEE Transactions on Information Theory, 49:371 -- 381, 2003.
• 12: L. H. Loomis and H. Whitney. An inequality related to the isoperimetric inequality. Bulletin of the American Mathematial Society, 1949.
• 13: D. Ron M. Feder and A. Tavory. Bounds on linear codes for network multicast. Electronic Colloquim on Computational Complexity (ECCC), 10(033), 2003.
• 14: Muriel Medard, Michelle Effros, Tracy Ho, and David Karger. On coding for non-multicast networks. In 41st Annual Allerton Conference on Communication Control and Computing, 2003.
• 15: Soren Riis. Linear versus non-linear boolean functions in network flow. In Conference on Information Sciences and Systems (CISS), March 2003.
• 16: Alexandre Tiskin. A generalization of the Cauchy and Loomis-Whitney inequalities. http://www.dcs.warwick.ac.uk/ tiskin/pub/.
• 17: Vorlesungen ūber Inhalt. Oberflāche and isoperimetrie. In Grundlehren der mathematischen Wissenchaften. Springer-Verlag, 1957. Number 93.