A new distributed QoS routing algorithm using mean field approximation method

Abstract Today various real‐time services, such as audio and video conferencing and telemedicine are being deployed over the Internet. This requires the network to provide guarantees of the service provided to the receiver. The needs of applications are specified in terms of Quality of Service (QoS) metrics such as the desired bandwidth, response time, loss rate, expected reliability, etc. Support for QoS must be provided at each of the layers of the protocol stack for overall efficiency in network utilization. Routing algorithms supporting QoS differentiation differ from traditional routing algorithms in that, in QoS routing, the path from the source to the destination must satisfy multiple constraints simultaneously, while in conventional routing, routing decisions are made only on a single metric, such as cost or delay. However, it is well known that the problem of path selection subject to two or more independent additive metrics is NP‐complete which means that there is no efficient (polynomial) exact solution for the general multi‐constrained path (MCP) selection problems. In this paper, we present an outline of distributed QoS routing problems and propose a mean field annealing (MFA) heuristic algorithm to solve the MCP problem. © 2008 Wiley Periodicals, Inc. Electron Comm Jpn, 91(1): 1– 10, 2008; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.10019