A SCALABLE QOS-BASED INTER-DOMAIN ROUTING SCHEME IN A HIGH-SPEED WIDEAREA NETWORK

In this paper we propose a scalable QoS-based inter-domain routing sch eme for distributed multimedia applications in a high speed wide area network. The problem of QoS-based routing is formulated as a multicrit eria shortest path problem, known as NP-complete [1,2] [W.C. Lee, M.G. Hluchyj, P.A. Humbler, Routing subject to quality of service constrai nts in integrated communication networks, IEEE Network (July/August 19 95) 46-55. Z. Wang, J. Crowcroft, Quality of service routing for suppo rting multimedia applications, IEEE J. Select. Areas Commun. Special I ssues on Multimedia Systems]. Our scheme consists of two phases. In Ph ase I, we present a way of mapping the network into a graph that conta ins a part of the network topology which is neglected completely or pa rtially by existing routing schemes, thus maintaining more accurate to pology information. In Phase 2, we develop a heuristic call-by-call al gorithm, based on each edge's minimum normalized slackness to the QoS requested, for selecting a feasible path efficiently in depth first se arch (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-b ased hierarchical routing schemes that address explicitly the issue of selecting a path with multiple metrics. (C) 1998 Published by Elsevie r Science B.V.