Exploiting the Inter-Domain Hierarchy for the QoS Network Management

Abstract : The Internet is an interconnection of multiple networks called domains. Inter-domain routing is ensured by BGP which preserves each domain's independence and announces routes arbitrarily chosen by domains. BGP messages carry no information concerning quality parameters of announced routes. The authors' goal is to provide domains with information regarding the congestion state of other domains without any changes in BGP. A domain, which is aware of heavily congested domains, can choose a bypass instead of a route exhibiting possible problems with QoS satisfaction. They propose a mechanism which sends alert messages in order to notify domains about the congestion state of other domains. The major difficulty consists in avoiding flooding the Internet with signaling messages. The authors' solution limits the number of alerts by taking advantage of the hierarchical structure of the Internet set by P2C and P2P relationships. Their algorithm is distributed and heuristic because it is a solution to an NP-complete and inapproximable problem. They prove these properties by reducing the Steiner problem in directed acyclic graphs to our problem of alert diffusion. The simulations show that our mechanism significantly diminishes the number of unavailable domains and routes compared to those obtained with BGP routing and with a theoretical centralized mechanism.