Latency-rate servers: a general model for analysis of traffic scheduling algorithms

Abstract

We develop a general model, called latency-rate servers (/spl Lscr//spl Rscr/ servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an /spl Lscr//spl Rscr/ server is determined by two parameters-the latency and the allocated rate. Several well-known scheduling algorithms, such as weighted fair queueing, virtualclock, self-clocked fair queueing, weighted round robin, and deficit round robin, belong to the class of /spl Lscr//spl Rscr/ servers. We derive tight upper bounds on the end-to-end delay, internal burstiness, and buffer requirements of individual sessions in an arbitrary network of /spl Lscr//spl Rscr/ servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a token bucket. The theory of /spl Lscr//spl Rscr/ servers enables computation of tight upper bounds on end-to-end delay and buffer requirements in a heterogeneous network, where individual servers may support different scheduling architectures and under different traffic models.