Report Number: CS-TR-96-1575
Institution: Stanford University, Department of Computer Science
Title: Routing and Admission Control in General Topology Networks with Poisson Arrivals
Author: Kamath, Anil
Author: Palmon, Omri
Author: Plotkin, Serge
Date: October 1996
Abstract: Emerging high speed networks 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. High bandwidth-delay product of these networks prevents circuit rerouting, i.e. once a circuit is routed on a certain path, the bandwidth taken by this circuit remains unavailable for the duration (holding time) of this circuit. As a result, such networks will need effective routing and admission control strategies. Recently developed online routing and admission control strategies have logarithmic competitive ratios with respect to the admission ratio (the fraction of admitted circuits). Such guarantees on performance are rather weak in the most interesting case where the rejection ratio of the optimum algorithm is very small or even 0. Unfortunately, these guarantees can not be improved in the context of the considered models, making it impossible to use these models to identify algorithms that are going to perform well in practice. In this paper we develop routing and admission control strategies for a more realistic model, where the requests for virtual circuits between any two points arrive according to a Poisson process and where the circuit holding times are exponentially distributed. Our model is close to the one that was developed to analyse and tune the (currently used) strategies for managing traffic in long-distance telephone networks. We strengthen this model by assuming that the rates of the Poisson processes (the ``traffic matrix'') are unknown to the algorithm and are chosen by the adversary. Our strategy is competitive with respect to the expected rejection ratio. More precisely, it achieves expected rejection ratio of at most R+epsilon, where R is the optimum expected rejection ratio. The expectations are taken over the distribution of the request sequences, and epsilon=Sqrt(r log n), where r is the maximum fraction of an edge bandwidth that can be requested by a single circuit.
http://i.stanford.edu/pub/cstr/reports/cs/tr/96/1575/CS-TR-96-1575.pdf