A comparison of network coding and tree packing
- Yunnan Wu ,
- Philip A. Chou ,
- Kamal Jain ,
- Philip A. Chou
Published by Institute of Electrical and Electronics Engineers, Inc.
We compare network coding solutions and routing solutions, namely packing distribution trees, for the problem of information multicast. 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.
© 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.