Routing on Shortest Pair of Disjoint Paths with Bandwidth Guaranteed

Author

Leng, Hongze ; Liang, Meilian ; Song, Junqiang ; Xie, Zheng ; Zhang, Jun

Author_Institution

Comput. Sch., Nat. Univ. of Defense Technol., Changsha, China

fYear

2009

fDate

12-14 Dec. 2009

Firstpage

557

Lastpage

561

Abstract

QoS routing and multipath routing have been receiving much attention respectively in network communication. However, the research combining those two kinds of routing is rare. This paper integrated the ideas of QoS and multipath, and presented the problem of shortest pair of disjoint paths with bandwidth guaranteed. we proved it to be NP-complete, and then proposed a heuristic algorithm. The analysis indicates that our algorithm shows good performance and it can produce optimal solutions in most cases.

Keywords

communication complexity; quality of service; telecommunication network routing; NP hard complete problem; QoS routing; bandwidth; disjoint path shortest pair routing; heuristic algorithm; multipath routing; network communication; Bandwidth; Computer networks; Costs; Delay; Heuristic algorithms; Mathematics; Maximum likelihood detection; Polynomials; Quality of service; Routing; QoS; bandwidth; disjoint; guaranteed; multipath; shortest pair;

fLanguage

English

Publisher

ieee

Conference_Titel

Dependable, Autonomic and Secure Computing, 2009. DASC '09. Eighth IEEE International Conference on

Conference_Location

Chengdu

Print_ISBN

978-0-7695-3929-4

Electronic_ISBN

978-1-4244-5421-1

Type

conf

DOI

10.1109/DASC.2009.81

Filename

5380426