| To support diverse applications, high-speed networks need to be able to simultaneously support multiple service classes. In the worst case, separate resources must be reserved for each class. More generally, through careful scheduling, re sources can be shared. In this dissertation, through study of the classic problem of scheduling a constant-capacity link to guarantee competing flows Deterministic Quality of Service (DQoS), we provide new perspectives on link sharing and new approaches to deterministic scheduling.; Conceptually and structurally, our development has two parts. In the first part, we address general issues concerning deterministic scheduling---its complexity, its controllability and its efficiency. In particular, we highlight diversity gain as the key to achieving higher link efficiency. To make our discussion concrete, we introduce Minimum Rate (MR) and Prioritized Token-Bucket (PTB) scheduling. In comparison, MR scheduling cannot exploit potential diversity gains while PTB scheduling can, so, efficiency-wise, the latter is superior to the former. Thanks to their simplicity, both MR and PTB schedulers are very easy to implement.; Building upon the intuition acquired in the first part of the dissertation, in the second part, we develop a more systematic, theoretical approach to identifying "good" scheduling policies. In marked contrast to past studies, which have primarily been scheduling-driven in the sense that they fixed the scheduling policy and then sought to identify the DQoS requirements it could satisfy, we pursue a DQoS-driven approach that fixes the flows' DQoS requirements and then identifies all scheduling policies that can satisfy them. To this end, we introduce a new, dynamic framework for state-based scheduling. In each instant, the framework allows us to determine the set of all scheduling decisions that the scheduler can make without endangering any flow's DQoS guarantee and thus it encompasses all possible scheduling policies. We illustrate our approach by investigating Delay-State (DS) and Matrix-State (MS) scheduling. DS scheduling extends, and deepens understanding of, the well-known Earliest Deadline First (EDF) scheduling policy, while MS scheduling is more comprehensive in that it enables modelling of network calculus-based DQoS constraints. |
