Satisfying Arbitrary Delay Requirements in Multihop Networks

We consider the problem of scheduling in a multi- hop packet network so as to satisfy a set of arbitrary end-to-end delay requirements. A number of scheduling protocols are known for which end-to-end delay bounds can be derived. However, it is often the case that these end-to-end delay bounds are large for flows with small rate. This is clearly inappropriate for traffic types such as VoIP for which tight delay bounds are required but session rates are typically small. In this paper we study the problem of satisfying an arbitrary set of end-to-delay requirements. For a single server in isolation, precise conditions on whether or not a set of delay requirements can be satisfied are known. In contrast, for sessions in a multihop network, we show that deciding whether or not a set of delay requirements can be met is NP-hard. However, if the delay requirements satisfy a simple set of per-server and per- session conditions necessary for schedulability, we show that our proposed protocol can meet all the requirements up to some logarithmic factor. On the negative side, we construct examples in which some delay bound must be violated by a logarithmic factor even if the necessary conditions hold. We further demonstrate through simulation the advantage of our protocol against a counterpart that does not take delay requirements into consideration. We conclude the paper by extending our results to the problem of satisfying arbitrary delay bounds in an input-queued switch.