TY - GEN

T1 - On multipath routing using widest pair of disjoint paths

AU - Shen, Bao Hong

AU - Hao, Bin

AU - Sen, Arunabha

PY - 2004/6/22

Y1 - 2004/6/22

N2 - Multipatb and disjoint path routing schemes have received considerable amount of attention in the networking research community in recent years due to many of advantages offered by such schemes. Delay, delay-jitter, bandwidth, are often used as parameters to specify quality-of-service. One of the most important parameter is the bandwidth of the route used for data transmission. A path from a source node s to a destination node t is known as the widest path if the bandwidth of this path is the largest among all paths between s to t. Algorithms for computing a widest path between a source-destination node pair is well-known. In this paper, we consider two problems where the notions of multipath, disjoint path and widest path are combined. In one version, we address the problem of finding a pair of disjoint paths between a source-destination node pair, such that the combined bandwidth of this path-pair is the maximum over all such pairs. In the other version, we want to find a pair of disjoint paths, such that the bandwidth of the first path is at least X 1 and the bandwidth of the second path is at least X 2, for some pre-specified values X 1 and X 2. We prove that both versions of the problem are NP-complete. We provide exact and approximate solutions for both versions of the problem. We show that our approximate solutions provide near-optimal solutions for almost all the instances of the problem.

AB - Multipatb and disjoint path routing schemes have received considerable amount of attention in the networking research community in recent years due to many of advantages offered by such schemes. Delay, delay-jitter, bandwidth, are often used as parameters to specify quality-of-service. One of the most important parameter is the bandwidth of the route used for data transmission. A path from a source node s to a destination node t is known as the widest path if the bandwidth of this path is the largest among all paths between s to t. Algorithms for computing a widest path between a source-destination node pair is well-known. In this paper, we consider two problems where the notions of multipath, disjoint path and widest path are combined. In one version, we address the problem of finding a pair of disjoint paths between a source-destination node pair, such that the combined bandwidth of this path-pair is the maximum over all such pairs. In the other version, we want to find a pair of disjoint paths, such that the bandwidth of the first path is at least X 1 and the bandwidth of the second path is at least X 2, for some pre-specified values X 1 and X 2. We prove that both versions of the problem are NP-complete. We provide exact and approximate solutions for both versions of the problem. We show that our approximate solutions provide near-optimal solutions for almost all the instances of the problem.

UR - http://www.scopus.com/inward/record.url?scp=2942564151&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2942564151&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:2942564151

SN - 0780383753

SN - 9780780383753

T3 - IEEE Workshop on High Performance Switching and Routing, HPSR

SP - 134

EP - 140

BT - 2004 Workshop on High Performance Switching and Routing, HPSR 2004

T2 - 2004 Workshop on High Perfomance Switching and Routing, HPSR 2004

Y2 - 19 April 2004 through 20 April 2004

ER -