Reverse Optimization Algorithm for QoS Routing Problem
Zhang Pin①②; Li Le-min①; Wang Sheng①
Key Lab of Optical Fiber and Communication Networks, UEST of China, Chengdu 610054, China;College of Communications, Hangzhou Dianzi University, Hangzhou 310017, China
Abstract:Finding the path satisfying two additive QoS constraints is the key question of QoS research. The linear search algorithm is one of important approximation algorithms. This paper proposes a new linear search algorithm combined with the reverse optimization scheme. If the path found by the linear search procedure does not satisfy the QoS constraints, the proper nodes of the path are chosen to make the reverse optimization. The time complexity of proposed algorithm is 0(K(m+nlog2(n))). The simulation shows that the new approach extends the search fields and improves the succeeding ratio of finding the feasible paths.