Optimal multiplexing on a single link: delay and buffer requirements

This paper is motivated by the need to support multiple service classes 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 the buffer requirements under three typical memory allocation mechanisms, that represent trade-offs between efficiency and complexity. For classes with delay constraints we provide policies that are optimal in the sense of satisfying the constraints if they are satisfiable by any policy, and they also have low buffer requirements. We also address the issue of designing policies that satisfy delay constraints in a fair manner. We mainly concern ourselves with non-preemptive policies. One of the proposed policies is based on a class of non-preemptive policies that tracks preemptive policies. This class is introduced in this paper and may be of interest in other applications as well.