A study of the routing capacity regions of networks

Author

Kakhbod, Ali ; Savari, Serap A. ; Yazdi, S. M Sadegh Tabatabaei

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., Univ. of Michigan, Ann Arbor, MI

fYear

2008

fDate

26-29 Oct. 2008

Firstpage

2226

Lastpage

2230

Abstract

The routing capacity region of networks with multiple unicast sessions can be characterized using Farkas´ lemma as an infinite set of linear inequalities. In this paper this result is sharpened by exploiting properties of the solution satisfied by each rate-tuple on the boundary of the capacity region, and a finite description of the routing capacity region which depends on network parameters is offered. For the special case of undirected ring networks additional results on the complexity of the description are provided.

Keywords

linear programming; multicast communication; telecommunication network routing; infinite set of linear inequalities; linear programming; multiple unicast sessions; network parameter; network routing; rate-tuple; routing capacity region; undirected ring networks; Communication standards; Error correction; Linear programming; Network coding; Routing; Sufficient conditions; Telecommunication network reliability; Throughput; Transmitters; Unicast; linear programming; multicast sessions; network capacity; routing;

fLanguage

English

Publisher

ieee

Conference_Titel

Signals, Systems and Computers, 2008 42nd Asilomar Conference on

Conference_Location

Pacific Grove, CA

ISSN

1058-6393

Print_ISBN

978-1-4244-2940-0

Electronic_ISBN

1058-6393

Type

conf

DOI

10.1109/ACSSC.2008.5074831

Filename

5074831