Report Number: CS-TR-95-1548
Institution: Stanford University, Department of Computer Science
Title: Routing and Admission Control in General Topology Networks
Author: Gawlick, Rainer
Author: Kamath, Anil
Author: Plotkin, Serge
Author: Ramakrishnan, K. G.
Date: May 1995
Abstract: Emerging high speed Broadband Integrated Services Digital Networks (B-ISDN) will carry traffic for services such as video-on-demand and video teleconferencing -- that require resource reservation along the path on which the traffic is sent. As a result, such networks will need effective {\em admission control} algorithms. The simplest approach is to use greedy admission control; in other words, accept every resource request that can be physically accommodated. However, in the context of symmetric loss networks (networks with a complete graph topology), non-greedy admission control has been shown to be more effective than greedy admission control. This paper suggests a new {\em non-greedy} routing and admission control algorithm for {\em general topology} networks. In contrast to previous algorithms, our algorithm does not require advance knowledge of the traffic patterns. Our algorithm combines key ideas from a recently developed theoretical algorithm with a stochastic analysis developed in the context of reservation-based algorithms. We evaluate the performance of our algorithm using extensive simulations on an existing commercial network topology and on variants of that topology. The simulations show that our algorithm outperforms greedy admission control over a broad range of network environments. The simulations also illuminate some important characteristics of our algorithm. For example, we characterize the importance of the implicit routing effects of the admission control part of our algorithm.
http://i.stanford.edu/pub/cstr/reports/cs/tr/95/1548/CS-TR-95-1548.pdf