IEEE Transactions on Information Theory · 1997 · 177 citations · 19 references
ComputingComputer ScienceComputer SystemsComputer NetworksQueuing TheorySchedulingBuffer ManagementNetwork Performance AnalysisQueueing TheoryResource-constrained SchedulingSwitching TechniquesBuffer ConstraintsFair QueueingMemory AllocationMemory Allocation PoliciesPacket SchedulingQueueing Control PoliciesQueueing Network ControlTraffic Scheduling
This paper is motivated by the need to provide per-session quality of service guarantees in fast packet-switched networks. We address the problem of characterizing and designing scheduling policies that are optimal in the sense of minimizing buffer and/or delay requirements under the assumption of commonly accepted traffic constraints. We investigate buffer requirements under three typical memory allocation mechanisms which represent tradeoffs between efficiency and complexity. For traffic with delay constraints we provide policies that are optimal in the sense of satisfying the constraints if they are satisfiable by any policy. We also investigate the tradeoff between delay and buffer optimality, and design policies that are "good" (optimal or close to) for both. Finally, we extend our results to the case of "soft" delay constraints and address the issue of designing policies that satisfy such constraints in a fair manner. Given our focus on packet switching, we mainly concern ourselves with nonpreemptive policies, but one class of nonpreemptive policies which we consider is based on tracking preemptive policies. This class is introduced and may be of interest in other applications as well.
19
Analysis and simulation of a fair queueing algorithm
Alan Demers, Srinivasan Keshav, Scott Shenker · 1989 · 1.7K citations