1048
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
`
`Quality of Service Guarantees 1n
`Virtual Circuit Switched Networks
`
`R. L. Cruz, Senior Member, IEEE
`
`(Invited Paper)
`
`Abstract-We review some recent results regarding the prob(cid:173)
`lem of providing deterministic quality of service guarantees in
`slot-based virtual circuit switched networks. The concept of a
`service curve is used to partially characterize the service that
`virtual circuit connections receive. We find that service curves
`provide a convenient framework for managing the allocation
`of performance guarantees. In particular, bounds on end-to-end
`performance measures can be simply obtained in terms of service
`curves and burstiness constraints on arriving traffic. Service
`curves can be allocated to the connections, and we consider
`scheduling algorithms that can support the allocated service
`curves. Such an approach provides the required degree of iso(cid:173)
`lation between the connections in order to support performance
`guarantees, without precluding statistical multiplexing. Finally,
`we examine the problem of enforcing burstiness constraints in
`slot-based networks.
`
`l. INTRODUCTION
`
`F UTURE high-speed networks are expected to carry a
`
`variety of traffic types with diverse quality of service
`requirements. A large number of papers describing method(cid:173)
`ologies to bound quality of service in such integrated services
`networks have recently appeared; the references in this paper
`constitute a noncomprehensive list. In particular, rate based
`flow control (for example, leaky bucket rate control) induces
`deterministic "burstiness constraints" on traffic streams, and
`"exact" analyses of queueing networks with respect to these
`constraints are possible.
`Analysis of queueing networks with burstiness constraints
`were studied at length in [4] and [5]. In particular, achiev(cid:173)
`able bounds on delay and buffering requirements at a single
`network element were presented in [4]. In a virtual cir(cid:173)
`cuit switched network, packets from a connection are routed
`through a fixed sequence of network elements, and [5] dis(cid:173)
`cusses bounds on end-to-end delay that are obtained by adding
`up the bounds on delay at each network element. Although,
`the bounds at each network element are achievable, the end(cid:173)
`to-end bounds on delay are not. Roughly speaking, if a packet
`suffers the worst possible delay at one network element, the
`packet will not suffer the worst possible delay at the next hop.
`Parekh and Gallager [14], [15J present results which make
`use of this idea; more recent work has extended these results
`in other directions [6], [8], [16]. The aim of this paper is to
`
`Manuscript receiveded September 30, 1994; revised April I, 1995. This
`work was supported by the National Science Foundation under Grants NSF
`NCR 89-04029, NSF NCR 91-58618, and NSF NCR 94-15684.
`The author is with the Department of Electrical and Computer Engineering,
`University of California at San Diego, La Jolla, CA 92093 USA.
`IEEE Log Number 9412654.
`
`review some of these results in a reasonably self-contained
`and unified way,
`We will make heavy use of the concept of a service curve,
`which has its roots in the work of Parekh and Gallager [14],
`[15]. As we will see, a service curve partially characterizes
`the service received by a connection at a network element.
`Many scheduling policies studied in the literature induce a
`service curve for each connection under assumptions regarding
`the arriving traffic. In this paper, however, we will take
`the viewpoint that a service curve is allocated rather than
`being induced by a certain scheduling policy. For example,
`after service curves have been allocated, one can synthesize
`scheduling policies which support the allocated service curves,
`independent of any assumptions regarding the arriving traffic,
`This allows the required degree of isolation between connec(cid:173)
`tions in order to support performance guarantees and does
`not preclude statistical multiplexing. Service curves provide
`a particularly convenient structure for the management of
`deterministic quality of service guarantees, since end-to-end
`performance measures can easily be obtained in terms of them.
`We now outline the remainder of this paper. In the next
`section, we briefly review the concept of a burstiness con(cid:173)
`straint. Section III defines the concept of a service curve for a
`single network element and presents some results concerning
`traffic through the network element. Section IV considers a
`tandem queue model that describes a connection in a virtual
`circuit switched network. After defining the concept of a
`network service curve, we present some results which yield
`bounds on end-to-end performance measures in terms of
`burstiness constraints and network service curves. In Section
`V, we consider the problem of scheduling in order to support
`service curves. We examine how burstiness constraints can be
`enforced in Section VI. In particular, we define a "regulator
`element" which is very similar to leaky bucket rate controllers
`that have been defined in the literature, but is slightly more
`general. The results in Section VI are analogous to results in
`[4J, [5], but with more direct proofs. Finally, we conclude in
`Section VII with some closing remarks.
`
`II. BURSTINESS CONSTRAINTS
`Throughout this paper, we consider a discrete time model,
`where the time slots are numbered 0, 1, 2,, · ·. The arrival of
`packets on a communication link is described by a function
`R. Specifically, R[n] denotes the number of packets flowing
`on the link during slot n, which is a nonnegative integer. We
`
`0733-8716/95$04.00 © 1995 IEEE
`
`

`

`CRUZ: QUALITY OF SERVICE GUARANTEES
`
`1049
`
`maximum burst length
`
`Fig. I. An anival curve.
`
`also define R[s + 1, t] to be the number of packets flowing
`on the link during the interval [s + 1, t], i.e. R[s + 1, t] =
`~~=s+l R[n]. Ifs 2: t, define R[s + 1, t] = 0.
`Definition-Arrival Constraints: Given a nondecreasing
`function b(·), we say that R is b-smooth if R[s+l, t] S b(t-s)
`for all s and t satisfying s S t. The inequality defining
`smoothness is termed a "burstiness constraint," and b(.) is
`called an arrival curve . In the special case where b is affine,
`say b(x) = u + px, we say that R is (u,p)-smooth.
`Note that since R is integer valued, if R is b-smooth, then
`it is also Lb J-smooth, where L x J is the largest integer less than
`or equal to x. Fig. 1 illustrates an example of an arrival curve,
`within the context of commonly discussed concepts of peak
`bandwidth, average bandwidth, and maximum burst length.
`For any given value of p 2: 0, define the virtual backlog
`process Wµ(R)[t] according to
`Wµ(R)[t] = rnax{R[s + 1, t] - p(t - s)}
`s:s"5:_t
`for all t. It is clear that Wµ(R)[t] Su for all t if and only if
`R is (u, p)-smooth. It is easy to verify that Wµ(R)[t] satisfies
`the recursion
`Wµ(R)[t] = [Wµ(R)[t - l] + R[t] - p]+
`where [:r]+denotes rnax{x,0}. Note that this recursion is the
`same as that of the amount of work remaining in a work
`conserving queueing system whose arrivals are described by
`R, and has a service capacity of p units of work per slot. This
`is why we call Wµ(R)[t] the virtual backlog process. Note
`that since p is not necessarily an integer, Wµ(R)[t] is not
`necessarily an integer. The magnitude of Wµ(R)[t] measures
`how "bursty" the arrival stream R is at time t, in some sense.
`
`(I)
`
`(2)
`
`III. ANALYSIS OF A SINGLE NETWORK ELEMENT
`
`Consider a network element fed by an arrival stream de(cid:173)
`scribed by Rin. The network element may be fed by other
`packet streams as well, but throughout this section we focus
`our attention on packets from this arrival stream. The departure
`of these packets from the network element is described by
`Rout. We assume that the network element is empty at the
`end of slot zero. Therefore the number of packets from the
`stream stored in the network element at the end of slot t is
`given by B[t] = Rin[l, t] - R 0 ut[l, t] 2: 0. The virtual delay
`relative to slot t, d[t], is defined by
`d[t] = min{ L1 : L1 2: 0 and Rin[l, t] S R 0 ut[L t + L'.l]}. (3)
`
`Fig. 2. Delay and backlog in a network element.
`
`See Fig. 2 for a graphical interpretation of these definitions.
`For simplicity of exposition, we will assume that at most one
`packet departs the network element in each slot, i.e., Rout[t] S
`1 for all t. This insures that Rin[l, t] = Rout[l, t + d[t]] for
`all t. Note that if packets depart the network element in the
`same order in which they arrive (FIFO), then d[t] is an upper
`bound to the delay through the network element suffered by a
`packet that arrives during slot t (d[t] will be equal to the delay
`suffered by the packet if exactly one packet arrives during slot
`t ).
`Lemma 1 ( Lower Bound on Burstiness of Output): For all t
`and 15 2: 0 there holds
`
`Proof Fix t and 15 2: 0. By definition of Wp(Rin)[t],
`there exists s* S t such that Wµ(Rin)[t] = Rin[s* + 1, t] -
`p(t- s*). Define 'U* = max{ 'U: 'US s* and B['U] = 0}. With
`these definitions we have
`Wp(Rin)[t] - pd[t]
`= Ri 11 [s* + 1, t] - p(t - s* + d[t])
`= Rin['U* + 1, t] - Rin['U* + 1, s*] - 15(t - s* + d[t])
`= R 0 ut['U* + 1, t + d[t]] - Rin[u* + 1, s*]
`- 15(t - s* + d[t])
`S Rout[u* + 1, t + d[t]] - R 0 ut['U* + 1, s*]
`- µ(t - s* + d[t])
`= Rout[s* + 1, t + d[t]] - p(t - s* + d[t])
`s Wµ(Rout)[t + d[t]].
`We present an upper bound on Wµ(Rout)[t + d[t]] in the
`next lemma. We first define the concept of a service curve.
`Definition-Service Constraints: Given a nondecreasing
`nonnegative function S(-), we say that the network element
`guarantees a service curve of S if for any t, there exists
`s S t such that B[s] = 0 and R 0 ut[s + 1, t] 2: S(t - s). If
`S(x) = [-usvc + px]+, where usvc 2: 0 and p 2: 0, then we
`say that the network element guarantees a service of ( usvc, p).
`Note that if a service curve of Sis guaranteed, then a service
`curve of I s7 is guaranteed, where Ix l is the smallest integer
`greater than or equal to .T.
`Lemma 2 ( Upper Bound on Burstiness of Output): Suppose
`a network element guarantees a service of ( usvc, p). Then for
`all t and p S p there holds
`
`

`

`1050
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
`
`Proof- Fix t and p :S p, and any s :S t + d[t]. Since
`the network element guarantees a service of ( usvc, p), there
`exists u* :S s such that B[u*] = 0 and R 0 ut[u* + 1, s] 2:
`-usvc + p(s - u*) 2 -usvc + p(s - u*). Thus
`
`R 011t[s + 1, t + d[t]] - p(t + d[t] - s)
`= Rout[u* + 1, t + d[t]] - R0 ut[u* + 1, s]
`- p(t + d[t] - s)
`= Rin[u* + 1, t] - R011t[u* + 1, s] - p(t + d[t] - s)
`:S Wp(Rin)[t] - R0 ut[u* + 1, s] - p(u* + d[t] - s)
`:S Wp(Rin)[t] + <Tsvc - pd[t]
`
`where the first inequality follows from the definition of
`Wp(Rin)[t] and the second inequality follows from
`the
`definition of u*. Since s is arbitrary, this completes the proof.
`Since Wp(Raut)[t + d[t]] 2'. 0 for all t, if the network
`element guarantees a service of ( usvc, p), Lemma 2 implies
`that d[t] :S (Wp(Rin)[t] + usvc)/ p. For example, if in addition
`Rin is (u,p)-smooth, then d[t] :S (u+usvc)/p.
`The next result we present generalizes this bound on delay.
`Theorem ]-Upper Bound on Delay at a Network Element:
`Consider a network element that guarantees a service curve of
`5(-) and suppose that the input traffic to the element, Rin, is
`b-smooth. Then, for all t the delay d[t] is upper bounded by
`
`d[t] :S max min{L1: L1 > 0 and b(k) < 5(k + L1)}.
`k:k?:1
`-
`-
`
`(6)
`
`Proof' If d[t] = 0 the result is trivial, so assume d[t] > 0.
`Since the network element guarantees a service curve of
`5(-), there exists s :S t + d[t] - 1 such that B[s] = 0 and
`Rouds +Lt+ d[t] - 1] 2 5(t + d[t] - 1 - s), Thus
`Rin[l, t] > Rout[l, t + d[t] - 1]
`2 R 011t[l, s] + 5(t + d[t] - 1 - s)
`= Rin[l, s] + 5(t + d[t] - 1 - s)
`
`where the first inequality follows from the definition of d[t]
`and the second inequality follows from the definition of s.
`Note that this implies that s < t, since 5(-) is nonnegative
`and nondecreasing. Hence R;n[s + 1, t] > 5(t + d[t] - 1 - s)
`and thus
`
`b(t - s) > 5(t + d[t] - 1 - s)
`
`(7)
`
`since Rin is b-smooth. It follows from (7) that
`
`d[t] :S min{L1: L1 2: 0 and b(t - s) :S 5(t + L1 - s)}
`:S max min{L1: L1 > 0 and b(k) < 5(k + L1)}.
`k:k?:1
`-
`-
`
`Note that the upper bound on delay in Theorem 1 has
`the graphical interpretation of being the maximum horizantal
`distance between the arrival curve b( •) and the service curve
`5(·), roughly speaking. This is illustrated in Fig. 3.
`We next present an upper bound on B[t], which is the
`maximum vertical distance between the arrival curve b( •) and
`the service curve S( • ), roughly speaking.
`
`service curve = S(x)
`
`X
`Fig. 3. Bounds on delay and backlog in terms of arrival and service curves.
`See also Theorem 4.
`
`Fig. 4. Tandem queue model.
`
`Theorem 2-Upper Bound on Backlog at a Network Element:
`Consider a network element that guarantees a service curve of
`S(,) and suppose that the input traffic to the element, Rin, is
`b-smooth. Then for all t the backlog B[t] is upper bounded by
`B[t] :S max{b(k) - S(k)}.
`(8)
`k:k?:O
`Proof· Fix t. Since the network element guarantees a
`service curve of S (-), there exists s :S t such that B [ s] = 0
`and Rout[s + 1, t] 2 S(t - s). Hence
`B[t] = Rin[l, t] - Rout[l, t]
`:S Rin[l, t] - R 0 ut[l, s] - S(t - s)
`= Rin[s + 1, t] - S(t - s)
`:S b( t - s) - S ( t - s)
`= max{b(k) - S(k)}.
`
`k:k?:O
`
`IV. TANDEM QUEUES
`We next consider an abstraction of a virtual circuit connec(cid:173)
`tion in a packet switched network. The model we consider
`consists of H network elements in tandem. For example, each
`network element could represent a packet switch along the
`route of a given virtual circuit connection. Let Rh-l describe
`the traffic entering network element h, and suppose the traffic
`departing network element h feeds network element h + 1,
`for all h satisfying 1 :S h < H (see Fig. 4). We also define
`Rin = Ro and Rout = RH throughout this section.
`Define dh [t] to be the virtual delay through the first h
`elements, i.e.
`dh[t] = min{L1: L1 2 0 and Ro[l, t] :S Rh[l, t + L1]}
`(9)
`and define d0 [t] = 0. Finally, let Bh[t] be the backlog at the
`end of slot tat network element h, i.e. Bh[t] = Rh-i[l,t] -
`Rh[l, t].
`Suppose network element h guarantees a service of ( u'rc, p)
`to the given connection for each h. Lemma 2 implies that
`Wp(Rh)[t + dh[t]]
`:S Wp(Rh-1)[t + dh_i[t]] + u,,Vc - p(dh[t] - dh-1[t]).
`(10)
`
`

`

`CRUZ: QUALITY OF SERVICE GUARANTEES
`
`1051
`
`Using transitivity, this implies that
`
`Wp(Rout)[t + dH[t]] ::; Wp(Rin)[t] + L crrc - pdn[t].
`
`H
`
`h=l
`
`Since Wp(RH )[t+dH[t]] 2 0, this implies the following upper
`bound on the end-to-end delay dH[t]
`
`(11)
`
`dH[t] S ~(Wp(Rin)[t] + L (Jhvc).
`
`H
`
`h=l
`
`p
`
`(12)
`
`If in addition the input traffic Rin is ( er, p )-smooth, then it
`follows that the end-to-end delay dH[t] is upper bounded by
`(a+ ~~=1 arc)/p. In the remainder of this section we will
`develop some results which yield a generalization of this upper
`bound.
`First, we define the concept of a network service curve.
`Definition-End-to-End Service Constraints: The network
`is said to guarantee a service curve of Snet ( •) if for all t, there
`exists a slot s S t such that Bi[s] = 0 and
`
`Rout[l, t] - Rin[l, s] 2 Snet(t - s).
`
`(13)
`
`Theorem 3-End-to-End Service: Suppose that each net(cid:173)
`work element h guarantees the given connection a service
`curve of Sh ( ·). Then the network guarantees a service curve
`of Snet(·), where
`
`Snet(x) = rnin{L Sh(xh): Xh 2 0 and L Xh = x }.
`
`H
`
`h=l
`
`H
`
`h=l
`
`(14)
`
`Proof- Fix any t and define ts = t. Define th for h < H
`recursively as follows: Given th there exists th-l S th such
`that Bh[th-1] = 0 and Rh[th-1 + 1, th] 2 Sh(th -
`th-1),
`since network element h guarantees a service curve of Sh ( •).
`Hence, B 1 [to] = 0 and
`
`Rout[l, t] - Rin[l, to]
`= RH[l, tH-1] + RH[tH-1 + 1, tH] - Ro[l, to]
`2 RH[l, tH-il + SH(tH -
`tH-1) - Ro[l, to]
`= RH-1[1, tH-1] + SH(tH -
`tH-1) - Ro[l, to]
`2 RH-dl, tH-2] + SH-1(tH-l -
`tH-2)
`+ SH(tH - tH-1) - Ro[l, to]
`
`h=l
`2 Snet(t - to)-
`
`It is interesting to note that Snet ( •) in Theorem 3 does not
`depend on the ordering of the network elements.
`
`Theorem 4-Upper Bound on End-to-End Delay: Suppose
`that the network guarantees a service curve of Snet ( ·) and
`suppose that the input traffic to the system, Rin, is b-smooth.
`Then the end-to-end delay dH [t] is upper bounded by
`dH[t] S max rnin{L1: L1 2 0 and b(k) S Snet(k + L1)}.
`k:k>l
`-
`(15)
`Proof- The proof is almost identical to the proof of
`Theorem I. If dH[t] = 0 the result is trivial, so assume
`dH [t] > 0. Since the network guarantees a service curve of
`Snet( ·), there exists s S t + dH[t] - 1 such that B1 [s] = 0 and
`Rout[l, t+dH[t]-1]-Rin[l, s] 2 Snet(t+dH[t]-1-s). Thus
`Rin[l, t] > Rout[l, t + dH[t] -
`l]
`2 Rin[l, s] + Snet(t + dH[t] - 1 - s)
`where the first inequality follows from the definition of dH [t]
`and the second inequality follows from the definition of s.
`Note that this implies that s < t and Rin [ s + 1, t] > Snet ( t +
`dH[t] - 1 - s). Hence
`b(t - s) > Snet(t + dH[t] - 1 - s)
`
`(16)
`
`since Rin is b-smooth. It follows from (16) that
`dH[t] S min{L1: L1 2 0 and b(t - s) S SH(t + L1 - s)}
`S max rnin{L1: L1 2 0 and b(k) S Snet(k + L1)}.
`
`k:k~l
`
`Note again that the upper bound on delay in Theorem 4 has
`the graphical interpretation of being the maximum horizontal
`distance between the arrival curve b( ·) and the network service
`curve Snet ( · ), roughly speaking. The last result of this section
`is a burstiness constraint on the output traffic of the network
`Rout, which yields a "departure curve."
`Theorem 5-Departure Curve: Suppose the network guar(cid:173)
`antees a service curve of Snet ( ·) and suppose that the input
`traffic to the system, Rin, is b-smooth. Then, there holds for
`all s S t
`R 0 ut[s + U] S rnax{b(t - s + k) - Snet(k)}.
`
`(17)
`
`k:k~O
`
`Proof- Fix s and t with s S t. Since the network
`guarantees a service curve of Snet(·), there exists u S s such
`that B1[u] = 0 and R 0 ut[l, s]-Rin[l, u] 2 Snet(s -u). Thus,
`R 0 ut[s + 1, t] = Rout[l, t] - Rout[l, s]
`S Rout[l,t] - (nn[l,u] + Snet(s - u))
`(Rin[l, u] + Snet(s - u))
`S Rin[l, t] -
`S b(t - u) - Snet(s - u)
`S max{b(t - s + k) - Snet(k)}.
`
`k:k~O
`
`V. SCHEDULING TO INSURE DELIVERY OF SERVICE CURVES
`
`A network element may in fact provide service to more
`than one virtual circuit connection passing through it. Consider
`such a network element, and suppose there are M connections
`passing through it. For the mth connection, let R~ and R:Ut
`describe the input and output traffic for the network element.
`Defining Bm[t] as the number of packets from connection m
`stored in the network element at the end of slot t, we thus have
`
`

`

`1052
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
`
`Bm[t] = Rfr:[1, t] - R:::;-,t[l, t]. We suppose that the network
`element is capable of serving only one packet per slot, i.e.
`
`M L R~t[t] S 1
`
`Tn=l
`
`(18)
`
`for all t. We shall also assume for simplicity that R[~ [ t] S 1
`for all rn and t.
`We would like to allocate each connection a service curve
`that the network element can guarantee. More specifically,
`let Sm(-) be a given nondecreasing nonnegative function for
`1 S rn S M.
`Theorem 6 below is a recent result [16] (see also [9]) that
`identifies a condition under which it is feasible for the network
`element to simultaneously guarantee each connection m a
`service curve 5m ( ·). By definition, this will be the case if
`for each t and m, there exists um St such that Bm[um] = 0
`and R;;:;-,t[um + 1, t] 2 sm(t - um).
`For notational simplicity we will assume that each 5m is
`integer valued. Define zm(k; t) for nonnegative integers k
`and t, k 2 t, according to
`zm(k; t) = min{Rfr:[1, u] + sm(k - u) :
`0 Su St and Bm[u] = O}.
`
`(19)
`
`By considering the v. that achieves the minimum in the
`definition of Z(t; t), it is easily seen that the following
`inequality is necessary and sufficient in order for the network
`element to guarantee a service curve of sm to connection rn
`
`(20)
`
`Consider the following scheduling policy, which we will
`see can guarantee each connection rn a service curve of 5m.
`Each packet arriving from connection rn at time t is assigned
`a deadline Dm[t] according to
`Dm[t] = min{ L1 : L1 2 t and zm(L1; t - 1) 2 R::[1, t]}.
`(21)
`
`The packets are served earliest deadline first (EDF) in a work
`conserving manner. More precisely, in each slot t, there are
`I:~;=J (Bm[t - 1] + Rfr:[t]) packets available for departure in
`slot t, and a packet among these with the smallest deadline is
`selected for departure during slot t.
`Note that Dm[t] can be computed by the network element
`at time t, and that for each rn, Dm[t] is nondecreasing in t.
`Roughly speaking, we would like to assign a deadline Dm[t] to
`a packet that arrives at time t such that zm(Dm[t]; Dm[t]) =
`Rfr:[1, t], since
`if the packet meets
`its deadline
`then
`R~[l, t] S R:::;-,t[l, Dm[tl] and hence R~:t[l, Dm[tl] 2
`zm(Dm[t]; Dm[t]) as
`in
`(20). However,
`the value of
`zm(L1; L1) for L1 >tis not computable at time t. Instead, we
`"estimate" zm(L1; L1) with zm(L1; t - 1) in (21); note that
`zm(L1; t - 1) 2 zm(L1; L1).
`Theorfm 6-Feasible Allocations of Service Curves: If
`L~=J sm(x) S x for all nonnegative integers x, then the
`EDF policy described above guarantees each connection rn
`a service curve of 5m.
`
`Proof' (Sketch). Let Nm[l, t] be the number of packets
`from connection rn which are assigned deadlines within the
`interval [1, t]. It follows easily that
`
`Nm[l, t] S zm(t; t).
`
`(22)
`
`Moreover, it can be shown that equality holds in (22) if no
`deadlines are missed.
`then zm(t; t)
`Thus,
`if no deadlines are missed
`Nm[l, t] S R:::;-,t[l, t] for all t and thus (20) is satisfied, so
`that a service curve of 5m is guaranteed to each connection
`rn. Hence, it suffices to show that no deadlines are missed.
`We argue by contradiction. Suppose a deadline is missed,
`and let D* be the first deadline missed, i.e.
`
`Let s0 be the last slot no later than D* that the network element
`was idle, i.e., so = max{ s : s S D* and L~=J Bm[s] = O}.
`Let SJ be the last slot in [so+ 1, D*] that a packet was served
`which had a deadline greater than D*, or define SJ = so if
`there is no such packet. Let T be the total number of packets
`that have deadlines in [sJ + 1, D*] that depart the network
`element after slot SJ. The total number of packets departing
`the network element in the interval [sJ + 1, D*] is equal to
`D* - s 1 since the scheduling policy is work conserving. Each
`of these packets is counted in T, as well as the packet that
`misses its deadline of D*. Thus
`
`D* - SJ+ 1 ST.
`
`(23)
`
`We now proceed to upper bound T. Let A be the set of
`connections which contain packets which are counted in T.
`Fix a connection rn belonging to A. Each of the packets
`from connection rn that departs the network element during
`the interval [L si] must have a deadline which is less than
`or equal to D*. This is because if the deadline of such
`a packet were greater than D*, that would imply that all
`packets from connection rn that depart after slot SJ would also
`have deadlines greater than D*, contradicting the fact that rn
`belongs to A. Furthermore, if a packet from connection m has
`a deadline before slot SJ+ 1, it must depart the network element
`before slot SJ + 1, since D* is the first deadline missed and
`SJ < D*. Thus, it follows that the number of packets counted
`in T from connection rn is equal to Nm[l, D*] - R;;:;-,t [1, s,].
`Next, we claim that Bm[sJ] = 0 for all m E A. To see
`this, suppose Bm[sJ] > 0 for some rn E A . Recall that a
`packet with a deadline greater than D* is served in slot SJ.
`Thus, by definition of the EDF scheduling policy, all packets
`from connection m backlogged at the end of slot SJ must
`have deadlines greater than D*. However, this implies that all
`packets from connection m that depart the network element
`after slot s 1 have deadlines greater than D*, which contradicts
`our assumption that rn E A.
`
`

`

`CRUZ: QUALITY OF SERVICE GUARANTEES
`
`1053
`
`( ) 'small latency,
`SI x small throughput'
`
`\
`
`\ s (x) 'large latency,
`
`2
`
`large throughput'
`
`X
`Fig. 5. Service curve examples for integrated service of diverse traffic
`types. It is possible to simultaneously guarantee both service curves since
`Si(1·) + 5 2 (J:) ::; .r.
`
`It follows from the above that
`
`T = L Nm[l, D*] - R~~t[l, si]
`
`m:mEA
`
`rn:rnEA
`
`m:rnEA
`
`rn:rnEA
`M
`
`:S L srn(D* - si),
`
`m=l
`
`where the first inequality follows from (22). Combining this
`with (23), we obtain a contradiction to the hypothesis of the
`theorem.
`As an example, Fig. 5 illustrates two service curves that
`can simultaneously be delivered. In this example, connection
`1 is only guaranteed a small throughput (since the asymptotic
`slope of S 1 is small) but receives high-priority service (since
`the slope of S 1 is unity near the origin), in some sense. In
`contrast, connection 2 will potentially suffer a large latency
`(since the slope of S2 is zero near the origin) but is guaranteed
`a large throughput (since the asymptotic slope of S2 is near
`unity).
`Note that a connection might be allocated a service curve
`which is bounded above by a constant, say F. For example,
`such an allocation would be appropriate for a connection
`created in order to support a file transfer consisting of F
`packets. After the file transfer is completed, the connection
`would be tom down, and after an appropriate delay, the service
`curve could be deallocated. This is an interesting area for
`future work.
`In order to set up a connection, one possible framework for
`allocating the connection a given network service curve along
`a path of network elements is the following. First, the "spare
`capacity" at each network element along the path is identified,
`where Theorem 6 indicates the largest possible service curve
`that the network element can guarantee to the connection.
`Theorem 3 can then be utilized to calculate the largest possible
`network service curve that can be guaranteed to the connection.
`In the framework described in the preceding paragraph,
`a connection is allocated a service curve at each network
`
`element, and Theorem 3 is used to calculate the resulting
`network service curve. For a given network service curve,
`the allocation of service curves at each network element is not
`unique. This raises the "budgeting" question of how to allocate
`the service curves at each network element in order to support
`a desired network service curve. Such an allocation at each
`network element is fixed. Intuitively, the network might be
`able to simultaneously support more network service curves
`with a more flexible approach.
`This motivates another possible framework for scheduling
`to guarantee delivery of a network service curve. Deadlines
`could be assigned at the first network element along the path
`of the connection, using the desired network service curve as
`a reference. Specifically, suppose B 1 [t] is the backlog at the
`end of slot t at the first network element along the path of the
`connection, Rin is the traffic offered by the connection to the
`first network element, and a network service curve of Snet is
`to be delivered to the connection. In analogy with (19), define
`
`Znet(k;t) = min{Rin[l,u] + Snet(k- u):
`0 :Su :St and B 1 [u] = O}.
`
`(24)
`
`If Rout is the traffic departing the last network element along
`the path of the connection, it is clear that network guarantees
`the connection a service curve of Snet if and only if
`
`(25)
`
`A deadline of Dnedt] could be assigned to a packet arriving
`to the first network element during slot t according to
`
`Dnet[t] = min{.1: L1 ~ t and Znet(.d;t-1) ~ Rin[Lt]}.
`(26)
`
`Let Nuet [l, t] be the number of packets from the connection
`that are assigned deadlines in [l, t]. It can be shown that if
`no deadlines are missed, then Nnedl, t] = Znet(t; t) for all
`t. Thus, if each packet departs the network before its dead(cid:173)
`line assigned at the first network element, then Znet(t; t) =
`Nnet[l, t]
`:S R 0 ut[l, t] and the network guarantees the con(cid:173)
`nection a service curve of Snet· An interesting open problem
`is identifying the feasible set of network service curves that
`can simultaneously be delivered to several connections. A
`reasonable scheduling policy to investigate in this regard
`would be a distributed-network-wide EDF policy, whereby
`network deadlines are calculated as in (26), and these deadlines
`are utilized for EDF scheduling at all network elements. We
`leave this for future work.
`We conclude this section with the following example. Sup(cid:173)
`pose that a connection generates traffic that is b-smooth for
`some b, and requires that end-to-end delay be at most dmax
`slots. Then, using Theorem 4, this delay guarantee can be made
`if the connection is allocated the network service curve Snet,
`where Snct is equal to b(-) shifted dmax units to the right, i.e.
`
`Suet(x) = {Cbl(, _ d
`
`X
`
`)
`rnax :
`
`if O :S .T :S dmax - 1
`if X ~ drnax·
`
`

`

`1054
`
`IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 13, NO. 6, AUGUST 1995
`
`VI. REGULATION
`In this section, we examine how to transform an arbitrary
`traffic stream into one that is b-smooth. We first define and
`analyze a network element, called a (a, p) regulator, which
`implements "rate-based flow control." The parameters a and
`p will be assumed throughout to satisfy a 2: 1 and O < p s 1.
`We then examine the simultaneous use of several of these
`regulator elements and will see that a more general regulation
`mechanism results.
`Let R;n describe the arrivals to the ( a, p) regulator. For
`simplicity of exposition, we will assume that at most one
`packet arrives in each slot, i.e. R;n[t] s 1 for each t.
`The departure of packets from the regulating element is
`described by Rout• We assume that there are no arrivals before
`slot 1 and that the regulator is empty at the end of slot
`zero. Therefore the number of packets stored in the ( a, p)
`regulator at the end of slot tis given by B[t] = R;n[l, t] -
`Rout [l, t] 2: 0. The function of the ( a, p) regulator is to buffer
`packets, if necessary, so that Rout is (a,p)-smooth, i.e. so
`that Wp(Rout)[t] S a for all t. Since Wp(Rout)[t] decreases
`during intervals where no packets depart, the ( a, p) regulator
`can insure that Wp(Rout)[t] S a by buffering packets long
`enough.
`Specifically, the operation of the ( a, p) regulator is defined
`by specifying Rout recursively as follows
`
`We must have either R 0 ut[t] = 0 or R 0 ut[t] = 1. In the
`former case, (27) implies that Wp(Rout)[t -1] > a - (1- p),
`and hence from (2) it follows that Wp(Rmn)[t] > a - 1. In
`l] = B[t] + R 0 ut[t] - Rin[t] 2:
`the latter case we have B[t -
`B[t] + Rout[t] - 1 = B[t] > 0. Thus, the hypothesis of (b)
`holds, so Wp(R0 ut)[t] > a - p 2: a - 1.
`We can now easily prove Lemma 4.
`Lemma 4: The (a, p) regulator guarantees a service of
`(0,p).
`Proof' Fix any t. By definition of Wp(Rout)[t], there
`exists s* St such that Wp(Rout)[t] = Rout[B* + 1, t] - p(t -
`8*) 2: 0 and Wp(Rout)[B*] = 0. Using Lemma 3 (a), this
`implies B[s*] = 0.
`Regulation inside the network may be desirable in order to
`reduce buffer requirements inside the network [5], [10], [21].
`Lemma 4 can then be used in conjunction with the results
`of Section IV to analyze the resulting end-to-end impact on
`latency.
`Next, note that Lemmas 1, 2, and 4 immediately imply the
`following.
`Corollary 1: For the ( a, p) regulator there holds
`Wp(Rout)[t + d[t]] = Wp(Rin)[t] - pd[t].
`Lemma 5 (Regulator Delay) For the (a, p) regulator there
`holds
`
`(28)
`
`Rout[t] =
`
`{
`
`l, if B[t - 1] + R;n[t] > 0
`and Wp(R 0 ut)[t - l] Sa - (1 - p)
`0, otherwise.
`
`(27)
`Note that Wp(Rout)[t] can be computed recursively using
`(2). In words, (27) says that a packet will depart from
`the (a, p) regulator at time t as long as there are packets
`available (this includes packets arriving during slot t) and
`l] Sa - (1 - p). Using (2), this implies that
`Wp(Rout)[t -
`Wp(Rout)[t] S a whenever a packet departs from the (a, p)
`regulator at time t. Since Wp(Raut) is nonincreasing during
`interdeparture intervals, this implies that Wp(Rout)[t] s a for
`all t, as desired.
`Note that p corresponds to the token arrival rate in a leaky
`bucket regulator. The (a, p) regulator is slightly more general
`than many common definitions of a leaky bucket regulator.
`In many defin