Edge-cut bounds on network coding rates Academic Article uri icon

abstract

  • Active networks are network architectures with processors that are capable of executing code carried by the packets passing through them. A critical network management concern is the optimization of such networks and tight bounds on their performance serve as useful design benchmarks. A new bound on communication rates is developed that applies to network coding, which is a promising active network application that has processors transmit packets that are general functions, for example a bit-wise XOR, of selected received packets. The bound generalizes an edge-cut bound on routing rates by progressively removing edges from the network graph and checking whether certain strengthened d-separation conditions are satisfied. The bound improves on the cut-set bound and its efficacy is demonstrated by showing that routing is rate-optimal for some commonly cited examples in the networking literature. 2006 Springer Science+Business Media, Inc.

published proceedings

  • JOURNAL OF NETWORK AND SYSTEMS MANAGEMENT

author list (cited authors)

  • Kramer, G., & Savari, S. A.

citation count

  • 71

complete list of authors

  • Kramer, Gerhard||Savari, Serap A

publication date

  • January 2006