A scalable QoS-based inter-domain routing scheme in a high speed wide area network

Abstract

In this paper we propose a scalable QoS-based inter-domain routing scheme for distributed multimedia applications in a high speed wide area network. The problem of QoS-based routing is formulated as a multicriteria shortest path problem, known as NP-complete [1,2] [W.C. Lee, M.G. Hluchyj, P.A. Humbler, Routing subject to quality of service constraints in integrated communication networks, IEEE Network (July/August 1995) 46-55. Z. Wang, J. Crowcroft, Quality of service routing for supporting multimedia applications, IEEE J. Select. Areas Commun. Special Issues on Multimedia Systems]. Our scheme consists of two phases. In Phase I, we present a way of mapping the network into a graph that contains a part of the network topology which is neglected completely or partially by existing routing schemes, thus maintaining more accurate topology information. In Phase 2, we develop a heuristic call-by-call algorithm, based on each edge's minimum normalized slackness to the QoS requested, for selecting a feasible path efficiently in depth first search (DFS)-like manner on the graph and tailoring to each application's QoS requirements. Note that our routing scheme is one of a few QoS-based hierarchical routing schemes that address explicitly the issue of selecting a path with multiple metrics. (C) 1998 Published by Elsevier Science B.V.