Efficient admission control for EDF schedulers

We propose a class of non-work-conserving service disciplines, called the rate-controlled service disciplines. When coupled with suitable admission control algorithms, rate-controlled service disciplines can provide end-to-end deterministic and statistical performance guarantees on a per-connection basis in an arbitrary-topology packet-switching network. The key feature of a rate-controlled service discipline is the separation of the server into two components: a rate controller and a scheduler. This separation makes it possible to obtain end-to-end performance characteristics by applying single node analysis at each switch. It also has several other distinct advantages: it decouples the allocation of bandwidths and delay bounds, uniformly distributes the allocation of buffer space inside the network to prevent packet loss, and allows arbitrary combinations of rate-control policies and packet scheduling policies. Rate-controlled service disciplines provide a general framework within which most of the existing non-work-conserving disciplines can be naturally expressed. One discipline in this class, called Rate-Controlled Static Priority (RCSP), is particularly suitable for providing performance guarantees in high-speed networks. It achieves simplicity of implementation as well as flexibility in the allocation of bandwidths and delay bounds to different connections.

Compressed digital video is one of the most important traffic types in future integrated services networks. However, a network service that supports delay-sensitive video imposes many problems since compressed video sources are variable bit rate (VBR) with a high degree of burstiness. In this paper, we consider a network service that can provide deterministic guarantees on the minimum throughput and the maximum delay of VBR video traffic. A common belief is that due to the burstiness of VBR traffic, such a service will not be efficient and will necessarily result in low network utilization. We investigate the fundamental limits and tradeoffs in providing deterministic performance guarantees to video and use a set of 10 to 90 minute long MPEG-compressed video traces for evaluation. Contrary to conventional wisdom, we are able to show that, in many cases, a deterministic service can be provided to video traffic while maintaining a reasonable level of network utilization. We first consider an ideal network environment that employs the most accurate deterministic, time-invariant video traffic characterizations, Earliest-Deadline-First packet schedulers, and exact admission control conditions. The utilization achievable in this situation provides the fundamental limits of a deterministic service. We then investigate the utilization limits in a network environment that takes into account practical constraints, such as the need for fast policing mechanisms, simple packet scheduling algorithms, and efficient admission control tests.

There are numerous applications which require packets to be delivered within pre-specified delay bounds in point-to-point packet-switched networks. To meet this requirement, we define a real-time channel as a unidirectional connection between two nodes in such a network that guarantees every packet to be delivered before a user-defined, end-to-end deadline. The goal of this paper is to lay a mathematical basis for the problem of establishing real-time channels by (i) deriving a necessary and sufficient condition for the schedulability of a set of channels over a link, and (ii) developing an efficient method for calculating the minimum delay bound over a link for each channel. Given the traffic characteristics of a channel, our results can be used to check whether or not every packet will be delivered within a pre-specified delay bound. The results are also applicable to a wide variety of real-time task scheduling problems. >

This is a summary of data from an extensive analysis of on-off speech patterns in 16 experimental telephone conversations. The on-off patterns are determined by a fixed threshold speech detector having certain rules for rejecting noise and for filling in short gaps (for example, from stop consonants). Distributions are obtained for ten events, including talk-spurts, pauses, double talking (simultaneous speech from both parties), mutual silence, etc. Particular emphasis is placed on events surrounding interruptions. The entire analysis is performed for three speech detector thresholds, since most of the data are strongly influenced by choice of threshold. Observations are made about the influence of threshold on the data, properties of speech invariant with choice of threshold, and differences between male and female speech patterns.

The problem of multiprogram scheduling on a single processor is studied from the viewpoint of the characteristics peculiar to the program functions that need guaranteed service. It is shown that an optimum fixed priority scheduler possesses an upper bound to processor utilization which may be as low as 70 percent for large task sets. It is also shown that full processor utilization can be achieved by dynamically assigning priorities on the basis of their current deadlines. A combination of these two scheduling techniques is also discussed.

This paper is motivated by the need to support multiple service classes in fast packet-switched networks. The authors 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. They investigate the buffer requirements under three typical memory allocation mechanisms, that represent trade-offs between efficiency and complexity. For classes with delay constraints they 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. They also address the issue of designing policies that satisfy delay constraints in a fair manner. They 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. >

A scheme is developed for providing predictable interprocess communication in real-time systems with (partially connected) point-to-point interconnection networks, which provides guarantees on the maximum delivery time for messages. This scheme is based on the concept of a real-time channel, a unidirectional connection between source and destination. A real-time channel has parameters which describe the performance requirements of the source-destination communication, e.g., from a sensor station to a control site. Methods to compute guarantees for the delivery time of messages belonging to real-time channels are examined. Problems associated with allocating buffers for these messages are addressed, and a scheme which preserves delivery time guarantees is developed. >