.
`
`I
`
`
`
`1052
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 9, NO. 7. SEPTEMBER 1991
`
`Real-Time Scheduling with Quality of Service
`Constraints
`
`Jay M. Hyman, Student Member, IEEE, Aurel A. Lazar, Senior Member, IEEE, and
`Giovanni Pacifici, Member, IEEE
`
`Abstract-Can the introduction of traffic classes improve upon
`the performance of ATM networks? We investigate this issue
`within the framework provided by a class of networks that
`guarantees quality of service. To provide a meaningful com-
`parison we define the concept of schedulable region, a region
`in the space of loads for which the quality of service is guar-
`anteed. We show the dependence of the schedulable region on
`the scheduling algorithm employed, quality of service param-
`eters, and traffic statistics. An efficient real-time scheduling al-
`gorithm is introduced that substantially increases the schedul-
`able region without incurring prohibitive complexity costs. The
`schedulable region associated with this algorithm is compared
`with the ones generated by the static priority scheduling algo-
`rithm and a variant of the minimum laxity threshold algorithm.
`The size and shape of the schedulable region is explored by
`means of simulations.
`
`I. INTRODUCTION
`N [l], a class of integrated networks was proposed for
`
`I implementation with the capability of eficiently provid-
`
`ing quality of service (QOS). The switching architecture
`of these networks is novel in that the concept of quality
`of service explicitly appears in the design specification at
`both the edge and core of the network. One of the fun-
`damental requirements of these systems is that the core of
`the network makes a distinction between traffic classes.
`This was found necessary in order to efficiently provide
`quality of service. The immediate question these net-
`works raise is whether traffic classes should also be intro-
`duced in ATM networks. This paper attempts to provide
`information for a better understanding and elucidation of
`this question. Our present study is limited to a switching
`node taken in isolation.
`To date, there are two networks that were designed
`based on the ideas presented in [l]. One is MAGNET I1
`[2], a fully instrumented and operational network testbed
`for metropolitan area applications. The other is TeraNet
`[3], a gigabit network currently under development. These
`networks are called asynchronous time sharing (ATS)-
`based because of the way the main network resources
`
`Manuscript received August 199(krevi:-ed
`I This paper was sup-
`ported by the National Science Foundation under Grant ECD-88-11 I 1 I .
`This paper was presented in part at the Seventh International Teletraffic
`Congress, Morristown, NJ, Oct. 9-11, 1990.
`The authors are with the Center for Telecommunications Research, Co-
`lumbia University, New York, NY 10027-6699.
`IEEE Log Number 9102694.
`
`‘‘‘I
`
`(switching and communication bandwidth, buffer space,
`and processing capacity) are allocated. The design of
`ATS-based networks heavily relies on the hardware im-
`plementation of buffer management and scheduling algo-
`rithms in which the QOS guarantee is explicitly incorpo-
`rated. This represents its distinctive feature.
`In order to give a quantitative framework for evaluating
`the performance of ATS-based networks that provide QOS
`guarantees, the concept of the schedulable region is in-
`troduced. It is the region in the space of possible loads
`for which a scheduling algorithm guarantees quality of
`service. The set of QOS constraints for the schedulable
`region is interpreted as a generalization of the classical
`‘‘average time delay smaller than infinity” constraint that
`defines stability in the classical sense for queueing sys-
`tems. The size and shape of the schedulable region de-
`pends, as shown in this paper, on the scheduling algo-
`rithm used, the QOS parameters under consideration, and
`the statistics of the traffic load. Throughout this paper,
`comparisons of different algorithms and evaluations of
`these various effects are expressed in terms of the size of
`the schedulable region. Presently, the exploration of the
`schedulable region is possible for the type of traffic
`sources considered in this paper only by means of simu-
`lations. Analytically tractable traffic sources for a FIFO
`queueing system are analyzed within the framework of
`Palm probabilities in [4].
`We present the MAGNET I1 real-time scheduling al-
`gorithm (MARS), and compare its performance with that
`of other known algorithms that have already been consid-
`ered in the literature, static priority scheduling (SPS) and
`a variant of minimum laxity threshold (MLT). Related
`work on scheduling was previously published in [5]-[9],
`[ 141, [ 151. The MARS algorithm uses a simple knowl-
`edge structure, and was adopted for implementation on
`our real-time network testbed MAGNET I1 as well as
`TeraNet. The complexity of its implementation versus the
`corresponding performance is also investigated.
`As already mentioned, this work is intended to provide
`data for the ongoing discussion about the need for intro-
`ducing traffic classes in ATM networks. The introduction
`of traffic classes leads to higher complexity. Is this com-
`plexity warranted? The answer does not appear to be an
`easy one. From a strict performance point of view, we
`show that the schedulable region is increased and this in-
`
`0733-8716/91/0900-1052$01 00 0 1991 IEEE
`
`7 --1
`
`~
`
`__
`
`~
`
`

`

`Input Llnk n
`Input Llnk n b T
`
`Output Llnk
`
`~
`
`11.3
`
`111.3 C.3
`
`1053
`
`---
`--
`-
`
`---
`
`InputLlnk
`
`1.1
`1.2
`1.3
`
`~
`
`~
`
`I
`
`Favport RAY
`
`11.1 ; 111.1
`
`11.2
`11.3
`
`c.1
`c.2
`111.2
`111.3 C.3
`t
`
`output Link
`
`c
`
`Fig. 1. The architecture of the TeraNet network interface unit
`
`mission time. In Fig. 1, the critical resources (buffer space
`and communication links) are controlled by a link sched-
`uler and buffer manager. Scheduling and buffer manage-
`ment policies have hardware support. A general discus-
`sion of the basic architecture of an ATS-based switching
`node is given in [ 11.
`
`B. The Quality of Service Constraints
`The architecture shown in Fig. 1 supports four classes
`of traffic.. Three of the traffic classes (Class I, 11, and 111)
`transport user traffic and are defined by a set of perfor-
`mance constraints. The fourth class, Class C, transports
`traffic of the network management system, and is not sub-
`ject to specific QOS constraints.
`Class I traffic is characterized by 0% contention packet
`loss and an end-to-end time delay distribution with a nar-
`row support. The maximum end-to-end time delay be-
`tween the source and destination stations is denoted by
`S'. Class I1 traffic is characterized by 6 % contention
`packet loss and an upper bound, 7, on the average number
`of consecutively lost packets. It is also characterized by
`an end-to-end time delay distribution with a larger support
`than Class I. The maximum end-to-end time delay is S".
`Here, E and 7 are arbitrarily small numbers and SI I S".
`For Class I and I1 traffic, there is no retransmission policy
`for lost packets. Class I11 traffic is characterized by 0%
`end-to-end packet loss that is achieved with an end-to-end
`retransmission policy for error correction. If requested, it
`is also characterized by a minimum average user through-
`put r and a maximum average user time delay T.
`
`C. The Link Scheduling Model
`The contention problem at one of the output links of
`Fig. 1 is modeled as a resource allocation problem in a
`queueing system consisting of four FIFO buffers (one for
`each traffic class) sharing a single server as shown in Fig.
`2. The server models a slotted channel with a fixed ca-
`pacity of C bits/second and a fixed cell size of D
`bits/cell. The service rate is denoted by p = C / D
`cells/second.
`For this buffer model, there are various scheduling
`
`HYMAN et al.: REAL-TIME SCHEDULING WITH QOS CONSTRAINTS
`
`crease leads to a substantial gain in the overall efficiency
`of utilization of network resources. More investigations
`along the lines described here will be needed, with data
`ultimately obtained from the operational networks that we
`have implemented.
`This paper is organized as follows. In Section 11, we
`briefly describe the main characteristics of the class of
`ATS-based broadband networks by using the block dia-
`gram implementation of the TeraNet switching node. The
`quality of service constraints, the link scheduling model,
`and the real-time traffic source models for benchmarking
`are also introduced. In Section 111, the concept of the
`schedulable region is introduced, the SPS and MLT al-
`gorithms are described, and the MARS algorithm is intro-
`duced and presented in detail. In Section IV, the algo-
`rithms discussed in the previous section are evaluated via
`simulations. First, the complexity versus performance
`tradeoff for the MARS algorithm is discussed. Then, the
`dependence of the schedulable region on the scheduling
`algorithm, QOS parameters, and traffic statistics is eval-
`uated. Finally, the distribution of the QOS parameters as-
`sociated with each call is explored. Section V concludes
`the paper with a discussion of issues for further study.
`
`11. THE GENERIC SCHEDULING PROBLEM
`The generic scheduling problem presented in this sec-
`tion was motivated by the implementation of a class of
`asynchronous time sharing networks. The switching ar-
`chitecture of these networks is briefly described in Section
`11-A. Four traffic classes are introduced via quality of ser-
`vice constraints in Section 11-B. Note that, in order to keep
`the complexity of the network manageable, the QOS for
`these classes is defined for the network as a whole, rather
`than for each individual call. The introduction of traffic
`classes calls for the introduction of scheduling algo-
`rithms. Models for scheduling of the link bandwidth are
`described in Section 11-C. Source models of traffic flows
`for different traffic classes are discussed in Section 11-D.
`
`A. The Architecture of the Switching Node
`The basic architeture of the ATS-based switching node
`was first implemented on MAGNET I1 [2]. It was also
`adopted for a new prototype multihop lightwave network
`called TeraNet [3]. In order to exemplify the application
`of the scheduling algorithms investigated in this paper,
`the architecture of the network interface units (switching
`nodes) of the latter network is briefly discussed here (see
`Fig. 1).
`Each network interface unit consists of three input links,
`three output links, and a bus-based nonblocking switch
`fabric. Congestion may arise only at the output links. The
`architecture supports multiple traffic classes. Traffic arriv-
`ing at an access point is transferred and stored, according
`to its class, into one (or more) of the multiple buffers.
`Each group of multiple buffers is connected to an output
`port. Note that this architecture allows for simultaneous
`arrivals at each of the output buffers during a packet trans-
`
`

`

`.
`
`I
`
`
`
`1054
`
`ClassC
`
`ClassII
`
`l
`
`l
`
`I I I I I I I
`
`l
`
`l
`
`l
`
`l ~
`
`- l
`- w
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 9, NO. I. SEPTEMBER 1991
`
`in practice: we could not find a more easily understand-
`able way to interpret and present the results.
`A single video call is modeled as a periodic random
`process that is characterized by a fixed frame duration of
`F = 62.5 ms, a constant bit rate of c1 = 10 Mb/s, and
`average active period IEICactive]. At time t = jF, the frame
`begins and the source emits cells at a rate c'/D. During
`this time, the source is active. The active period, Cactive,
`is a random variable uniformly distributed between Cmin
`= 10 ms and Emax = 40 ms. At the end of the active
`period, the source stops emitting cells for the duration of
`the frame, e.g., F - Cactive. The cycle then repeats. The
`source average rate is given by:
`IEX(t, video) = !!l!?&d * c' = 4 Mb/s.
`F
`Multiplexing of K' video calls is assumed to be accom-
`plished by uniformly distributing the frame start at inter-
`vals of F/K' ms.
`A single voice call is modeled as an on-off source with
`constant arrivals. It is characterized by an exponentially
`distributed active period, in which cells are generated with
`constant rate c"/D with cI1 = 64 Kb/s, and an exponen-
`tially distributed silence period, in which no cells are gen-
`erated.
`Con and Coff are two statistically independent random
`variables with a negative exponential distribution describ-
`ing the on-off behavior of the source. IEICon] = 352 ms
`and IE[COff] = 650 ms denote the average values of Con
`and Coff, respectively [ 111. The average rate for one such
`source is given by:
`
`(2.1)
`
`IEX(r, voice) =
`E[Conl + IE[CoffI
`
`* cI1 = 22.5 Kb/s.
`
`Finally, the data traffic is modeled as a Poisson source
`with average rate
`IEX(t, data) = 1 Mb/s.
`
`(2.3)
`
`111. SCHEDULING ALGORITHMS AND THE SCHEDULABLE
`REGION
`In this section, the main scheduling algorithms are in-
`troduced. The presentation in Section 111-A starts with the
`introduction of the schedulable region concept that pro-
`vides the framework for comparing the different sched-
`uling algorithms. In Section 111-B, two algorithms are in-
`troduced. One is based on static priority scheduling and
`the other on a variant of the minimum laxity threshold
`algorithm. In Section 111-C, the MAGNET I1 real-time
`scheduling algorithm is presented and discussed in detail.
`
`A. The Schedulable Region
`Intuitively, the schedulable region of a queueing sys-
`tem is the set of points in the space of possible loads for
`
`Fig. 2. The ATS link scheduling model.
`
`mechanisms that can be employed. For some schedulers,
`such as SPS and MLT, control decisions are made at each
`packet departure time, and the parameters (Mc, M', M",
`M"') are not relevant. For others, such as MARS, which
`utilize the asynchronous time sharing (ATS) scheme de-
`scribed below, control decisions occur at the end of each
`cycle, when these parameters are set for the course of the
`next cycle. In all cases, service is nonpreemptive; a cell
`transmission in progress cannot be aborted.
`In the ATS scheme, the allocation of the server to each
`of the buffer (packet) classes is achieved by dividing time
`into periods called cycles consisting of up to Hcells. Each
`cycle is further divided into four subcycles. During each
`subcycle (C, I, 11, 111), the link is allocated to the corre-
`sponding traffic class (C, I, 11, 111). For example, during
`subcycle I, Class I packets enter the server (link). The
`link scheduler uses four variables ( M c , MI, M", M"') to
`determine the boundary positions between subcycles.
`These variables represent the length (in cells) of subcycle
`C, I, 11, and 111, respectively, and can be dynamically
`adjusted by the scheduler according to the traffic load and
`mix. For a broader view of the switching and communi-
`cation bandwidth allocation concepts included in the ATS
`framework, see [l].
`
`D. Real-Time Trafic Source Models
`For the purposes of this paper, we consider each of the
`traffic classes, defined via quality of service constraints in
`Section 11-B, to carry information of a very specific type.
`Class I is assumed to consist of K' video calls, and Class
`I1 of K" voice calls. Class I11 consists of K"' data sources.
`The use of traffic source models raises two issues: how
`close are they to traffic sources encountered in practice,
`and what is the traffic mix employed.
`The traffic models described below have been validated
`based on an extensive set of real-time measurements and
`qualitative evaluations of real-time video as well as traffic
`source models for video, voice, and data on MAGNET I1
`[lo]. Note, however, that the traffic sources used in the
`results presented in this paper display homogeneity. That
`is, a single source model is used within the same traffic
`class. Therefore, e.g., the same peak load values or in-
`terarrival time correlations are used. There is a simple
`reason for this deviation from what would most likely arise
`
`

`

`HYMAN et al.: REAL-TIME SCHEDULING WITH QOS CONSTRAINTS
`
`1055
`
`which the quality of service is guaranteed. As such, this
`concept is a generalization of the concept of stability re-
`gion. Recall that the general concept of stability calls for
`finding the region in the space of loads for which the aver-
`age time delay is finite. In our case, the set of constraints
`that determine the schedulable region is defined by the
`QOS constraints. Examples of constraints were given in
`Section 11-B and include hard time delay constraints,
`probability of blocking and average gap constraints, aver-
`age throughput, and average time delay constraints. Note
`that the schedulable region might be finite even for the
`case of a queueing system with finite buffer size. This is
`because the QOS constraints might restrict the loading on
`the system before the finite buffer size does.
`Figs. 10, 13, and 14 are examples of schedulable re-
`gions for a three-dimensional queueing system with Class
`I, 11, and I11 buffers. The axes in these figures show the
`load for each traffic class. The region in the three-dimen-
`sional space below the shaded surface represents the
`schedulable region. The size of the schedulable region de-
`pends on the scheduling algorithm used, the values of the
`QOS parameters, and the statistics of the traffic load. The
`dependency will be investigated in this paper. How to in-
`crease the schedulable region through the use of sched-
`uling algorithms will be discussed in detail.
`The theoretical characterization of the schedulable re-
`gion appears, in general, to be fairly complex. A theoret-
`ical study of the schedulable region for the M M / G / l
`queueing system can be found in [4]. Markov-modulated
`arrivals, hard-time delays, blocking, and average packet
`gap constraints were considered. In this paper, the shape
`and size of the schedulable region is explored with very
`few restrictions on the arrival process, QOS parameters,
`and class of scheduling algorithms. As a result, at this
`point in the theoretical development, only simulations can
`give an insight into the form and size of the schedulable
`region under these assumptions. The size of the schedul-
`able region is a prime factor in determining the admission
`control policy for ATS-based networks [ 121.
`For the sake of simplicity, we will limit our present
`study of the schedulable region to a queueing system with
`three user classes (Class I, 11, and 111). Therefore, we will
`assume that the system in Fig. 2 is not loaded with Class
`C traffic. This represents an approximation to the case
`where the Class C traffic load is negligible when com-
`pared with the aggregated user traffic load. An extension
`of our results to the general case of four classes is straight-
`forward. Finally, we will assume that each of the buffers
`has infinite capacity. The finite buffer case, currently un-
`der consideration, will be published elsewhere.
`
`B. SPS and MLT Algorithms
`
`When static priority scheduling (SPS) is employed,
`Class I cells are always transmitted ahead of Class 11, and
`Class I1 cells are always transmitted ahead of those of
`Class 111. This scheduling scheme is simple to implement,
`
`and is thus often considered for scheduling of real-time
`traffic. Note that SPS scheduling is class-dependent. In-
`tuitively, this policy will not be efficient when S' is large
`compared to S". This is because the priority policy could
`cause QOS violations for the other traffic classes even
`while Class I delays are far from their allowed limits. In
`these cases, overall performance can be improved by de-
`laying Class I packets within their QOS bounds.
`The minimum laxity threshold (MLT) policy used in
`this paper will now be defined. Note that both the defi-
`nition of laxity and the algorithm itself differ slightly from
`those used to define a previously published policy with
`the same name [6]. Let @ denote the number of cells in
`the Class k queue, and let t k ( i ) be the deadline of the ith
`Class k cell, for i = 0,
`, Q k - 1. It is assumed that
`*
`the cells in the buffer are sorted according to their dead-
`lines. In our case, this is always true since the buffer be-
`haves as a FIFO and the Class I maximum delay (SI) is
`the same for every cell. Also, with no loss of generality
`(since service times are deterministic), we adopt the con-
`vention that deadlines are to the beginning of service.
`The laxity L'(i) of the ith Class I cell in the buffer at
`time t is defined by:
`~ ' ( i ) = tI(i> - t - 1.
`P
`Thus, for a given cell which knows that i other cells must
`precede it into service, the laxity represents the amount
`of time for which the server may remain idle, or serve
`cells of other classes, and still be able to serve this cell
`by its deadline. Note that this concern is not explicitly
`addressed by algorithms based only on the laxity of the
`packet at the head of the queue, as in [6].
`The laxity for a Class I1 cell reflects the fact that it must
`be preceded into service by a number of Class I cells, in
`addition to all Class I1 cells ahead of it. Let N'(t) denote
`the number of Class I cells which have deadlines before
`time t . The laxity for cell i in the Class I1 queue is then
`given by:
`L"(i) = t"(i) - r - - (i + N1(tl'(i))).
`1
`P
`Prior to each cell transmission time, the laxities are
`evaluated for each of the cells in the queues for traffic
`classes I and 11, and the minimum laxities L' and L" are
`computed for the queues themselves, by:
`
`(3.1)
`
`(3.2)
`
`L~ = min Lk(i).
`O s r < Q k
`
`(3.3)
`
`A threshold operation is then used to choose which class
`to serve. If L' < l / p , then the Class I queue must be
`served. If not, and L" < l / p , then the Class I1 queue
`must be served. If neither of these conditions are true,
`then a Class I11 cell may be transmitted (if one exists).
`This scheduling policy is closely related to the OPT
`policy proposed in [9]. That policy, which is based on full
`knowledge of all future arrivals, is presented there as an
`
`

`

`.
`
`..
`
`1056
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 9. NO. 7. SEPTEMBER 1991
`
`unrealizable optimal algorithm against which to bench-
`mark other schedulers. Under the simplifying assumption
`made here that the cells of a given class always arrive in
`the order of their deadlines, and the assumption in [9] that
`all future arrivals are known (which, in this context, would
`be reflected by the exact knowledge of N1(t) and the eval-
`uation of laxities for packets not yet in the queues), the
`two policies should achieve identical schedules. How-
`ever, while the OPT algorithm requires that the Class I
`schedule be completely filled in for all time before any
`Class I1 cells can be scheduled and is thus unrealizable,
`the MLT algorithm presented here allows for an imple-
`mentation based on predicting N'(t) when necessary. Spe-
`cifically, if t"(i) > t + SI (which is only possible if SI
`< S"), then N'(t"(i)) is given by the number of packets
`in the Class I queue plus the predicted number of Class I
`amvals in the interval (t, t"(i) - SI]. The scheduler im-
`plemented for our studies evaluates laxities only for cells
`already in the buffers (3.3) and, when appropriate, uses
`an estimate of N1(t) based on a first-order filter. This
`scheduler is thus expected to be very efficient, but esti-
`mation errors could decrease the link efficiency.
`
`C. MARS: A Real-Time Scheduling Algorithm
`In this section a real-time scheduling algorithm for
`ATS-based networks, called MARS, is presented. Refer-
`ring to the ATS link scheduling model of Fig. 2, the server
`activity over the course of a cycle is divided into subcy-
`cles, whose lengths are defined by the parameters MI, M",
`and MI1'. The scheduler is responsible for properly setting
`these parameters.
`Informally, the scheduler operates as follows. A max-
`imum cycle length of H cells is first chosen. The knowl-
`edge structure available to the scheduler at the beginning
`of each cycle consists of two schedules (lists) of dimen-
`sions h' and h" that contain the number of Class I and
`Class I1 cells which arrived in each of the previous h' and
`h" cycles. The scheduling algorithm updates these lists at
`the end of each cycle by taking into account the number
`of new cells that arrived durin2 the'previous cycle. The
`scheduling algorithm is based on the intuition that in order
`to achieve high throughput, each cycle should serve only
`the Class I and I1 cells whose transmission cannot be fur-
`ther delayed. Thus, in each cycle, the scheduler first sets
`MI, and then M"; in each case choosing the minimum
`number of cells that must be transmitted to satisfy the QOS
`requirements. Any cells remaining in the cycle may then
`be assigned to M"'. Throughout this process, the sched-
`uler must adhere to the maximum cycle length constraint
`MI + MI1 + M"' I H .
`(3.4)
`If, after M' has been set, not enough cells remain in the
`cycle to satisfy the Class I requirements, the exceeding
`Class I1 cells are clipped.
`The actual cycle length, often shorter than H, will
`change dynamically depending on the traffic load and pro-
`file. By keeping track of the number of packets arriving
`
`in each cycle, the scheduler will know ahead of time how
`many packets will be put up for service in the next cycle.
`To accomplish this, the scheduler updates the h'- and h"-
`dimensional schedules at the end of each cycle. These
`schedules correspond to a logical partitioning of the Class
`I and Class I1 buffers into bins.
`In the following, we will assume that h" 1 h'; the ex-
`tension to the cases h" = h1 and h" < h' is straightfor-
`ward. Fig. 3 shows the Class I and Class I1 buffer logical
`partitions at the beginning of the ith cycle. The variable
`M k [ i , j ] represents the number of Class k cells that at the
`beginning of cycle i , i E N , are predicted to be scheduled
`in the ( i + j)th cycle, j < hk, k = I, 11. Thus, thejth bin
`contains the number of Class k cells that, according to the
`current buffer status, will be transmitted during the (i +
`j)th cycle. k [ i , j ] is obtained through the min operator
`by comparing the value of Mk[i - 1, j + I] with the
`number of overflow packets created by the arrival of Class
`k cells, Ak[i], during the (i - 1)th cycle. The updating
`algorithm for M k , k = I, 11, I11 is described below.
`For Class I traffic, the updating process is described in
`Fig. 4. Since, as mentioned above, each bin contains the
`number of cells that are predicted to be scheduled for
`transmission for the next hk cycles, each bin's maximum
`value cannot exceed the total server bandwidth available
`in each cycle (i.e., H). Reading the flow of the block
`diagram of Fig. 4 from left to right, we have the set of
`equations :
`M ' [ i , j ] = min (M1[i - 1 , j + 11 + d [ i , j + 11, H)
`(3.5)
`O [ i , j l = max (0, M'[i - 1, j + 11
`+ d[i, j + 11 - H )
`for allj, j = h' - 1, h' - 2, *
`h'] = 0 and d [ i , h'l = A'[i].
`d [ i , j ] in (3.6) stands for overflow and represents the
`number of Class I cells that are predicted not to be trans-
`mitted during the (i + j)th cycle because this bin size
`would exceed the maximum bandwidth allocated to Class
`I for that cycle. It can be interpreted as the result of a
`
`(3.6)
`, 1 , 0 with M1[i - 1,
`
`

`

`HYMAN et al.: REAL-TIME SCHEDULING WITH QOS CONSTRAINTS
`
`1057
`
`... +,
`
`pi+&+
`Fig. 4. Class I bin updating process at the beginning of cycle i.
`
`Fig. 5 . Class I1 bin updating process at the beginning of cycle i.
`
`ripple efect generated by a number of arrivals that is
`larger than the capacity (H) of the server. This ripple ef-
`fect takes place when simultaneous arrivals occur due to
`bursts. As shown by ( 3 3 , those cells will be scheduled
`for transmission in an earlier cycle m, where i I m < i
`+ j . Finally, MI, the number of Class I cells scheduled
`for transmission during the ith cycle, is set to M' = M1[i,
`01.
`Fig. 5 describes the Class I1 schedule updating process.
`This step is similar to the Class I bin updating process
`since, at this time, only the portion of server bandwidth
`not used by Class I traffic can be allocated to Class 11.
`The Class I1 bins are updated as follows:
`~ " [ i , j l = min ( ~ " [ i - 1 , j + 11
`+ d'[i,j + 13, R[i,j])
` - 1, j + 11
`d'[i,j] = max (0, ~ " [
`i
`+ d'[i, j + 11 - R[i,j])
`(3.8)
`, 0, with M"[i - 1 , h"] = 0
`for all j , j = h" - 1,
`and d'[i, h"] = A"[i]. R[i,j], the portion of server band-
`width predicted to be available to Class I1 in the (i + j)th
`cycle, is given by:
`j = 0, 1 , * - - , h' - 1
`f H - M'[i,j]
`
`(3.7)
`
`*
`
`(3.9)
`Note that, if h" > h', R [ i , j] f o r j = h', h' + 1 , *
`,
`h" - 1 will depend on the number of future Class I ar-
`rivals. As this information is not yet available, it is esti-
`mated using a simple first-order estimator. The number of
`Class I1 cells scheduled for transmission during the ith
`cycle is set to M" = M"[i, 01.
`Finally, M"', the number of Class I11 packets to be
`served in the current cycle, is set to
`M"' = min (Q"'[i], H - M' - MI')
`(3.10)
`where Q"'[i] is the queue size of the Class I11 buffer at
`the beginning of cycle i.
`In what follows, the dimensioning of the number of bins
`that guarantees quality of service for Class I and I1 traffic
`will be discussed. As mentioned before, since the Class I
`
`I --r-r
`
`-
`
`cells arriving during the (i - 1)th cycle are transmitted
`no later than during the (i + h' - 1)th cycle, it follows
`that the worst-case delay corresponds to the case of a cell
`arriving at the beginning of the (i - 1)th cycle and being
`transmitted at the end of the (i + h' - 1)th cycle. In this
`case, the maximum Class I delay is given by
`w;,, = (h' + 1) -
`H
`P
`provided that the average Class I load over h' consecutive
`cycles does not exceed p [see also (3.16)]. Therefore, un-
`der mild regularity assumptions on the traffic profile, the
`QOS for Class I traffic is guaranteed if:
`(h' + 1) - I SI.
`H
`P
`The h' value that satisfies (3.12) and gives the largest
`Wkax is given by:
`
`(3.11)
`
`(3.12)
`
`h ' = L $ p l
`
`- 1
`
`(3.13)
`
`where Lx J denotes the largest integer less than or equal
`to z. From (3.11) and (3.13), it follows that the Class I
`maximum delay Wk,, is a function of the maximum cycle
`length H:
`
`(3.14)
`
`Since h' L 1 , it follows from (3.12) that the cycle length
`H is bounded by:
`
`S'
`H 5 1 . t .
`
`(3.15)
`
`In our discussion up to this point, we have not addressed
`the properties of the overflow bin d[i, 01. As mentioned
`before, d [ i , j ] represents the number of Class I cells that
`cannot be transmitted during the (i + j)th cycle. Since the
`Class I bin values are bounded by H (i.e., M'[i - 1 , j +
`11 I H), it follows from (3.5) and (3.6) that
`O'[i, j] 2 0 * O1[i, j + 11 > 0
`and, therefore, if ~ ' [ i , 01 > 0
`M'[i, j] = H
`
`(3.16)
`
`(3.17)
`
`

`

`.
`
`I
`
`
`
`1058
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 9, NO. 7. SEPTEMBER 1991
`
`was allowed before any measurements were taken, and
`the simulations were run for 60 s. The 95% confidence
`bounds for the measured performance criteria were well
`within 5 % of the observed values.
`
`A . Complexity Versus Performance Tradeoff
`In this section, the performance of the MARS sched-
`uling algorithm is studied versus its complexity. The
`complexity of MARS is a function of the number of Class
`I and Class I1 bins. The higher the number of bins, the
`higher the number of operations that the scheduler has to
`perform at the beginning of each cycle. On the other hand,
`as shown in Section III-C, the number of bins is inversely
`proportional to the maximum cycle length H , as deter-
`provided that packets to be 'lipped are dropped from the mined by worst-case delay considerations (3.13). This
`Class I1 buffer.
`worst-case delay represents the pessimistic assumption
`Similarly, it can be shown by arguments parallel to
`that a Class I packet arriving at the beginning of the (i -
`(3*16) and (3*17) that the quantity o"[i, '1
`represents the
`1)th cycle is not transmitted until the end of the (i + h'
`experience a
`number Of 'lass
`'I
`in
`that
`- 1)th cycle. As Class 1 cells are always served at the
`the worst case greater than S". Thus, the scheduler will
`beginning of a cycle, this event would require that H Class
`drop this number of cells from the Class I1 buffer.
`I cells arrive at the very beginning of cycle i - 1, and
`that this will occur at the tail end of a burst, with (h' -
`l ) H Class I cells already in the buffer. This is, thus, a
`rather rare event.