OPTIMAL MULTIPLEXING ON A SINGLE LINK - DELAY AND BUFFER REQUIREMENTS

This paper is motivated by the need to provide per-session quality of service guarantees in fast packet-switched networks, We address the pr oblem of characterizing and designing scheduling policies that are opt imal in the sense of minimizing buffer and/or delay requirements under the assumption of commonly accepted traffic constraints, We investiga te buffer requirements under three typical memory allocation mechanism s which represent tradeoffs between efficiency and complexity, For tra ffic with delay constraints we provide policies that are optimal in th e sense of satisfying the constraints if they. are satisfiable by any policy, We also investigate the tradeoff between delay and buffer opti mality, and design policies that are ''good'' (optimal or close to) fo r both, Finally, we extend our results to the case of ''soft'' delay c onstraints and address the issue of designing polities that satisfy su ch 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 pree mptive policies, This class is introduced in this paper and may be of interest in other applications as well.