Title :
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
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;
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
DOI :
10.1109/DASC.2009.81
