A Distributed Algorithm for Multiple-Metric Link State QoS Routing Problem

摘要

Multimedia applications often require guaranteed quality of service (QoS) and resource reservation, which has raised a number of challenging technical issues for routing. Nevertheless, the QoS routing algorithm must be simple because a costly procedure does not scale with the size of the network. In this paper, an efficient QoS routing method based on Lagrange relaxation is presented, which provides a polynomial heuristic solution to the Delay and Bandwidth Constrained Least Hop path problem (DBCLH) and Delay, Bandwidth and Loss probability Constrained Least Hop path problem (DBLCLH). An algorithm analysis and numerical evaluation are presented. It is shown that our polynomial algorithm is close to the optimal solution computed by an exponential algorithm.