In this paper, we undertake the first study of statistical multiplexing from the perspective of approximation algorithms. The basic issue underlying statistical multiplexing is the following: in high-speed networks, individual connections (i.e. communication sessions) are very bw-sty, with transmission rates that vary greatly over time. As such, the problem of packing multiple connections together on a link becomes more subtle than in the case when each connection is assumed to have a fixed demand. We consider one of the most commonly studied models in this domain: that of two communicating nodes connected by a set of parallel edges, where the rate of each connection between them is a random variable. We consider three related problems: (1) stochastic load balancing, (2) stochastic binpacking, and (3) stochastic knapsack. In the first problem the number of links is given and we want to minimize the expected value of the maximum load. In the other two problem the link capacity and art atlowed over@w probability p are given, and the objective is to assign connections to links, so that the probability that the load exceeds the link capacity is at most p. For the stochastic load balancing problem we give an O(l) -approximation algorithm for arbitrary random variables. For the other two problems we have algorithms restricted to on-off sources (the most common special case studied in the statistical multiplexing literature), with a A standardapproach that has emerged for dealing with probabilistic resource requirements is the notion of @ective bandwidth -this is a means of associating a fixed demand with a bunsty connection that "represents" its distribution as closely as possible. Our approximation algorithms make use of the standard definition of effective bandwidth and also a new one that we introducq the performance guarantees are based on new results showing that a combination of these measures can be used to provide bounds on the optimal solution.
Kleinberg et al REF consider traffic admission control in high-speed networks, and develop approximation algorithms to solve the corresponding stochas tic bin packing problem restricted to on-off sources.
Allocating bandwidth for bursty connections
STOC '97
Computer Science