Providing quality of service (QoS) guarantees for wireless communications requires special consideration for the relatively large and time-varying bit error rates of wireless links, due to impairments that are difficult to predict. We describe a new wireless link access scheme called remote-queueing multiple access (RQMA), which allows seamless integration of scheduling disciplines proposed for wired networks that achieve end-to-end QoS guarantees. RQMA supports the flexible and efficient allocation of bandwidth for real-time sessions. Mobile stations send information about their backlogged packets to a base station which executes a scheduling discipline that provides delay bounds. Some minimum portion of the link bandwidth is reserved for the retransmission of packets that are not correctly received but whose deadlines are still not violated. For a fast fading channel with an average error rate of 10/sup -2/, RQMA is capable of delivering real-time traffic with a small average packet loss rate on the order of 10/sup -5/. Similar performance can be achieved for a slow fading channel if the average error rate is no more than 10/sup -3/.

To provide service guarantees in packet-switching networks, several deadline-ordered service disciplines have been proposed, including delay-EDD (earliest due deadline), jitter-EDD, leave-in-time, RFS, and virtual-clock. In a deadline-ordered service discipline, packets are assigned transmission deadlines and are transmitted according to the deadline-ordered scheduling policy: transmit packets in increasing order of deadlines. Although these service disciplines provide desirable quality of service (QoS) guarantees, they have been regarded as infeasible for high-speed networks due to the high overhead imposed by the sorting of packets in the server queue. This paper shows that these service disciplines become efficient if they replace the deadline-ordered scheduling policy with a new scheduling policy that is defined. This new scheduling policy uses hardware support to achieve an O(1) time complexity. We prove that a server that employs this new scheduling policy provides a delay bound to real-time packets that is slightly larger than what the server can provide with deadline-ordered scheduling.

Rate-function scheduling (RFS) is a new deadline-based packet-scheduling service discipline that supports quality-of-service guarantees for applications with real-time communication requirements. RFS is distinguished from other service disciplines in that it achieves all of the following goals: analytically-derived performance bounds, performance isolation among sessions, flexible and efficient allocation of bandwidth, implementation simplicity, work-conserving operation, and bandwidth-fair operation (defined in the paper). Through the specification of rate functions, sessions can control their bandwidth usage and their upper bounds on delay. For a class of rate functions, which we show is sufficient for providing sessions with delay bounds, RFS is as simple to implement and to calculate service bounds such as Zhang's VirtualClock service discipline. We also show that the non-preemptive earliest deadline first policy is a simple degeneration of RFS.

In a deadline-ordered service discipline, packets are assigned transmission deadlines and eligibility times and are transmitted in increasing order of deadlines. Different deadline-ordered service disciplines are distinguished by how they calculate deadlines and eligibility times. One of the more difficult analytical problems one faces when designing a new deadline-ordered service discipline is to prove that one can bound the end of transmission times of packets relative to their assigned deadlines, which we call schedulability. We show that, no matter how one calculates deadlines, there is a simple schedulability condition for deadline-ordered service disciplines. This schedulability condition is necessary and sufficient for preemptive deadline-ordered service disciplines, and for a server that allows the presence of nonreal-time packets (i.e., packets with no deadlines), it is also necessary and sufficient for nonpreemptive deadline-ordered service disciplines. We also address the schedulability problem for service disciplines in general, and show the optimality of deadline-ordered service disciplines. To demonstrate how our results simplify schedulability determination, we use them to prove the known schedulability conditions of VirtualClock, Packet-by-Packet Generalized Processor Sharing (PGPS), Stop-and-Go, and Delay-Earliest-Due-Date (Delay-EDD), and to provide a new result, the necessary schedulability condition of VirtualClock.

Leave-in-Time is a new rate-based service discipline for packet-switching nodes in a connection-oriented data network. Leave-in-Time provides sessions with upper bounds on end-to-end delay, delay jitter, buffer space requirements, and an upper bound on the probability distribution of end-to-end delays. A Leave-in-Time session's guarantees are completely determined by the dynamic traffic behavior of that session, without influence from other sessions. This results in the desirable property that these guarantees are expressed as functions derivable simply from a single fixed-rate server (with rate equal to the session's reserved rate) serving only that session. Leave-in-Time has a non-work-conserving mode of operation for sessions desiring low end-to-end delay jitter. Finally, Leave-in-Time supports the notion of delay shifting, whereby the delay bounds of some sessions may be decreased at the expense of increasing those of other sessions. We present a set of admission control algorithms which support the ability to do delay shifting in a systematic way.

Proves that a connection composed of virtual-clock servers provides an upper bound on delay for leaky bucket constrained sessions, i.e., sessions conforming to a token bucket filter. This upper bound on delay is calculated, and it is the same upper bound on delay given by PGPS. The authors also prove that leaky bucket constrained sessions are the only type of sessions for which an upper bound on delay can be provided by servers with an upper bound on link capacity.>