Construct QoS End-to-end Virtual Path With Lagrangean Relaxation Method

Abstract

In this paper, we have improved a QoS routing problem. We give an approach to minimize the congested link utilization while to satisfy individual connection’s packet delay. We use a Lagrangean Relaxation based approach augmented with an efficient primal heuristic algorithm, called Lagrangean Relaxation Heuristic (LRH). With the aid of generated Lagrangean multipliers and lower bound indexes, the primal heuristic algorithm of LRH achieves a near-optimal upper-bound solution. A performance study delineated that the performance trade-off between accuracy and convergence speed can be manipulated via adjusting the Unimproved Count (UC) parameter in the algorithm. We have drawn comparisons of accuracy and computation time between LRH and the Linear Programming Relaxation (LPR)-based method, under three networks named NSFNET, PACBELL, and GTE and three random networks. Experimental results demonstrated that the LRH is superior to the other approach, namely the LPR method, in both accuracy and computational time complexity, particularly for larger size networks