07/01/1995 09:00 AM
Computer Engineering
In this paper, we develop a general model, called Latency-Rate servers ($\\cal LR$-servers), for the analysis of traffic scheduling algorithms in broadband packet networks. The behavior of an $\\cal LR$ scheduler is determined by two parameters --- the latency and the allocated rate. We show that 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 $\\cal LR$-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 ${\\cal LR}$-servers in terms of the latencies of the individual schedulers in the network, when the session traffic is shaped by a leaky bucket. Thus, the theory of $\\cal LR$-servers enables computation of tight upper-bounds on end- to-end delay and buffer requirements in a network of servers in which the servers on a path may not all use the same scheduling algorithm. We also define a self-contained approach to evaluate the fairness of $\\cal LR$-servers and use it to compare the fairness of many well- known scheduling algorithms.
