A comparison of network coding and tree packing

Author

Wu, Yunnan ; Chou, Philip A. ; Jain, Kamal

Author_Institution

Dept. of Electr. Eng., Princeton Univ., NJ, USA

fYear

2004

fDate

27 June-2 July 2004

Firstpage

143

Abstract

Network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast is compared in this paper. To enable the comparison, we develop greedy tree packing algorithms that repeatedly pack the maximum-rate distribution tree and a greedy tree packing algorithm based on Lovasz´ proof to Edmonds´ theorem. We then investigate the potential advantages of network coding over routing. In terms of throughput, tree packing performs comparably to network coding on the network graphs of six Internet service providers. However, network coding offers additional benefits, including fewer network resources consumed, ease of management, and robustness.

Keywords

encoding; graph theory; multicast communication; telecommunication network routing; trees (mathematics); Edmond theorem; Lovasz proof; greedy tree packing algorithm; information multicast; maximum-rate distribution; network coding; network graph; network resource; routing solution; Communication networks; Electronic mail; Multicast algorithms; Network coding; Resource management; Robustness; Routing; Throughput; Tree graphs; Web and internet services;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on

Print_ISBN

0-7803-8280-3

Type

conf

DOI

10.1109/ISIT.2004.1365182

Filename

1365182