End-to-end delay service in high-speed packet networks using earliest deadline first scheduling
Vijay Sivaraman, Mário Gerla · 2000
Broadband integrated services packet networks rely on traffic scheduling disciplines within the packet switches in the network to provide a wide range of Quality of Service (QoS) assurances. The role of the scheduling discipline at each outgoing link of the switch is to select, from the available packets belonging to flows sharing the output link, the packet to be transmitted next on the link. This dissertation contributes to the design, analysis and implementation of such a scheduling discipline, namely Earliest Deadline First (EDF), and compares its performance to the Generalized Processor Sharing (GPS) scheduling discipline in providing per-flow end-to-end delay guarantees. The first part of this work considers the provision of end-to-end deterministic delay guarantees to regulated traffic flows when EDF scheduling is used in conjunction with per-hop traffic shaping. We show that deducing the optimal shaping parameters is infeasible except in trivial cases, and propose a heuristic choice that has desirable properties and performs very well for realistic traffic scenarios. In the second and main part of this work, we focus on the provision of statistical delay guarantees. We develop analytical frameworks that allow the aggregate loss (namely, delay violation) probabilities at EDF schedulers to be quantified under markovian as well as dual-leaky-bucket regulated traffic assumptions. We show that our analysis matches simulation values very closely, and allows the network to operate at much higher utilizations than the deterministic setting. To realize the requisite per-flow guarantees from the aggregate losses, we propose a low-complexity packet discard mechanism that drops packets fairly when delay violations are imminent at the EDF scheduler. We then compare the delay performance of the EDF and GPS scheduling schemes in the statistical setting, and show that EDF offers consistently larger network schedulable regions than GPS. Further, we argue that the use of GPS for statistical delay support is inherently problematic, since optimizing the performance of GPS requires dynamic resynchronization of the flow weights—an operation too expensive for practical implementation. In the final part of our work, we propose a highly scalable architecture of the EDF shaper. Our architecture has complexity independent of the number of flows being shaped, and guarantees small and bounded degradations in delay performance, making it very amenable for hardware implementation at high speeds.