Title :
Heuristic Algorithm for K-disjoint QoS Routing Problem
Author :
Yu, Zhanke ; Ni, Mingfang ; Wang, Zeyan ; Huang, Huajun
Author_Institution :
Inst. of Commun. Eng., PLA Univ. of Sci. & Technol., Nanjing, China
Abstract :
K-disjoint QoS Routing emphasizes to find k disjoint paths from source to destination satisfying the QoS requirements. It is well-known that this problem is NP-Complete. In this paper, we formulate the k-disjoint QoS routing problem as binary integer linear program (BILP) and propose a new heuristic algorithm based on integer linear programming and penalty function. Preliminary numerical results show that the proposed algorithm is viable.
Keywords :
computational complexity; integer programming; linear programming; quality of service; telecommunication network routing; NP-complete problem; binary integer linear program; communication networks; heuristic algorithm; k-disjoint QoS routing problem; penalty function; Additives; Algorithm design and analysis; Delay; Heuristic algorithms; Integer linear programming; Quality of service; Routing; disjoint QoS routing; integer linear programming; multi-constrained path; penalty function;
Conference_Titel :
Computational Sciences and Optimization (CSO), 2011 Fourth International Joint Conference on
Conference_Location :
Yunnan
Print_ISBN :
978-1-4244-9712-6
Electronic_ISBN :
978-0-7695-4335-2
DOI :
10.1109/CSO.2011.145
