A comparison of network coding and tree packing

Yunnan Wu, Philip A. Chou, and Kamal Jain


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 maximumrate

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.


Publication typeInproceedings
PublisherInstitute of Electrical and Electronics Engineers, Inc.
> Publications > A comparison of network coding and tree packing