[IEEE Trans. on Information Theory, March 2006, pp. 777-788]
Network Routing Capacity
Jillian Cannons, Randall Dougherty, Chris Freiling, and Kenneth Zeger
Abstract
We define the routing capacity of a network to be the supremum of all possible
fractional message throughputs achievable by routing.
We prove that the routing capacity of every network is achievable and rational,
we present an algorithm for its computation,
and we prove that every rational number in (0,1] is the routing capacity of some solvable network.
We also determine the routing capacity for various example networks.
Finally, we discuss the extension of routing capacity to fractional coding solutions
and show that the coding capacity of a network is independent of the alphabet used.