Leonid, Guerin, Vperis Kumar@ece - Iisc.ernet - in
Leonid, Guerin, Vperis Kumar@ece - Iisc.ernet - in
Leonid, Guerin, Vperis Kumar@ece - Iisc.ernet - in
L. Georgiadis, R. Guerin, V. Peris Advanced Networking Laboratory IBM T. J. Watson Research Center P.O. Box 704, Yorktown Heights, NY 10598
kumar@ece.iisc.ernet.in
fleonid,guerin,vperisg@watson.ibm.com
This paper addresses the problem of providing per-connection end-to-end delay guarantees in a highspeed network. We assume that the network is connection oriented and enforces some admission control which ensures that the source tra c conforms to speci ed tra c characteristics. We concentrate on the class of Rate-Controlled Service Disciplines, in which tra c from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where di erent reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same \minimal" envelope. The main disadvantage of this class of service disciplines is that the end-to-end delay guarantees are obtained as the sum of the worst case delays at each node, but we show that this problem can be alleviated through \proper" reshaping of the tra c to an envelope, which is in general di erent from the original envelope of the source tra c. We illustrate the impact of this reshaping by demonstrating its use in designing Rate-Controlled Service disciplines that outperform GPS-based service disciplines. Furthermore, we show that we can restrict the space of \good" shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving, and as a result reduce the average end-to-end delays. Keywords: QoS Provisioning, Real-time Tra c, Tra c Shaping, ATM, Scheduling, End-to-end Delay Guarantees.
Abstract
1 Introduction
In this paper, we consider the problem of providing per connection end-to-end delay (and throughput) guarantees in high speed networks. Various scheduling policies have been suggested in the literature for this purpose. Among them, policies based on Fair Queueing, alternatively known as Generalized Processor Sharing (GPS) 7, 13, 11, 12], have attracted special attention since they guarantee throughput to individual connections and provide smaller end-to-end delay bounds than other policies, for connections that cross several nodes. A key factor in obtaining these smaller delay bounds is the ability to take into account (delay) dependencies in the successive nodes that a connection has to cross, which is in general very di cult to do with other policies.
And IBM T.J. Watson Research Center.
One notable attempt at addressing this general problem is that of 6] which introduced the concept of service burstiness, and used it to provide a framework to characterize service disciplines and evaluate their end-to-end delay performance. However, the generality of the framework in 6] did not result in as tight end-to-end delay bounds as those obtained by focusing on a speci c policy. For example, the bounds available based on the techniques of 6] are no better than the looser bounds found in 12]. In this paper we concentrate on Rate-Controlled Service (RCS) disciplines, which have also been proposed in the literature 16] to provide performance guarantees to individual connections. In this class of service disciplines, the tra c of each connection is reshaped at every node to ensure that the tra c o ered to the scheduler arbitrating local packet transmissions conforms to speci c characteristics. In particular, it is typically used to enforce, at a node inside the network, the same tra c parameter control as the one performed at the network access point, which is based on the parameters negotiated during connection establishment. Reshaping makes the tra c at each node more predictable and, therefore, simpli es the task of guaranteeing performance to individual connections when used with a particular scheduling policy, it allows the speci cation of worst case delay bounds at each node 16]. End-to-end delay bounds can then be computed as the sum of the worst case delay bounds at each node along the path. The main advantages of an RCS discipline, especially when compared to GPS, are simplicity of implementation and exibility. Also, in the single node case the RCS discipline that uses the Non Preemptive Earliest Deadline First (NPEDF) scheduling policy, is known to be optimal 8]. However, for the more interesting case of general networks with many nodes, optimality does not hold. In section 4.1 we show with simple examples that when a connection has to cross many nodes, GPS outperforms the \naive" rate-controlled NPEDF discipline. As a result, it has been argued that despite its potentially greater complexity, a GPS-based service discipline should be the solution of choice to provide performance guarantees to individual connections (see for example 3]). A key result of this paper is to establish that RCS disciplines can be designed so as to outperform GPSbased ones, even in a network environment. This is achieved by proper selection of the tra c reshaping performed at each node. Speci cally, any end-to-end delay bounds that can be guaranteed by the GPS discipline, can also be achieved by an RCS discipline by using a simple algorithm to determine how to reshape the tra c, and then specify worst case delay bounds at each node. The sum of the worst case delay bounds of this RCS discipline is then no larger than the delay guarantees provided by the GPS discipline. We also show that RCS disciplines have the additional exibility of providing end-to-end delay bounds that cannot be guaranteed by the GPS discipline. Furthermore, because of tra c reshaping, the network bu er requirements of RCS disciplines are in general signi cantly smaller than those of the GPS discipline (see 6] for related discussions). Based on these advantages and their implementation simplicity, we believe that RCS disciplines are very e ective candidates for providing end-to-end performance guarantees to individual connections in integrated services networks. The paper is structured as follows. In Section 2 we introduce our tra c model, and in particular our assumptions concerning properties of the envelope of the input tra c, and the general structure of our shapers. Section 3 is dedicated to the description of RCS disciplines and to the derivation of several results concerning the delay guarantees they can provide given the tra c and shaper models of Section 2. Section 4 is devoted to a comparison with the GPS service discipline. Section 4.1 considers rst the simpler 2
U(J) Packetizer
A(J)
Scheduler
Figure 1: Connection Tra c Flow version of GPS, i.e., Rate Proportional Processor Sharing (RPPS), as it is of greater practical signi cance. Section 4.2 considers the more complicated case of general GPS for which similar results are established. Various properties of tra c shapers are investigated in Section 5, and used to establish that the reshaping needed for RCS disciplines to perform well can be achieved using \simple" shapers. Finally, the important extension demonstrating that the results of the paper hold when reshaping is performed only in case of congestion, is the topic of Section 6. A brief conclusion summarizes the main ndings of the paper. The Appendices contain proofs of the Lemmas, as well as an extension to the more general case of subadditive tra c envelopes.
U t t + ] U( )
3
t 0
0:
The envelope function is not unique without loss of generality (see 2]) we can assume that U ( ) is
right-continuous, nondecreasing, and subadditive. The packetizer splits the input tra c into packets of maximum length L, that are instantaneously delivered to the shaper when the last bit of the packet is received. We denote the tra c at the output of the packetizer in the interval t t + ] as I t t + ]. It is easy to see that, for any non-negative t and ,
I t t + ] U t t + ] + L U ( ) + L =: I ( )
(1)
The tra c shaper reshapes the incoming tra c by delaying the packets according to the rules described next, and then delivers them to the scheduler. The tra c shaper is characterized by a tra c envelope, A( ), which upper bounds the amount of tra c that is output by the shaper in any interval of length . If A t t + ] denotes the tra c that is output from the shaper in the interval t t + ], then A t t + ] A( ). More precisely, the tra c shaper outputs packets in order with each packet being released at the smallest time t such that A t ; t] A( ) 0 t: (2) The tra c shapers that we use in this paper can be constructed from simple ( ) tra c shapers that can alternatively be described in terms of the backlog tra c in a hypothetical queue with a server of rate 4]. Assume that tra c I 0 t] is queued for transmission at a link of speed > 0 and de ne W (I )(t) as the amount of tra c queued at time t at this link, including the packet that may have arrived at time t. It is known 4] that W (I )(t) is given by
(3)
The ( ) tra c shaper, operates on the ith packet arriving at time si , according to the following rule. The packet is released to the scheduler at the earliest time ti si , such that the shaper output tra c, A t t + ], satis es the condition
W (A)(ti)
=L+
where W (A)(ti) is de ned as in (3). Note that the condition 0 is necessary in order to allow packets of size L to pass through the shaper. This shaper corresponds to the operation of a leaky bucket in a store-and-forward network 1], which di ers from the one de ned in 4] in two minor respects: i) packets are entering and exiting the shaper instantaneously and not at a constant rate C , and ii) the length of the packet that exits the tra c shaper at time ti is taken into account in the calculation of W (A)(ti). Note that si and ti are de ned as the times when the last (not the rst as in 4]) bit of the ith packet enters and exits the shaper respectively. However, with di := ti ; si denoting the delay that the ith packet experiences in a shaper, the analysis in 4] can be repeated with minor modi cations to show that
di = 1 (W (I )(si) ; )+ and At t+ ]
+ : The ( ) shaper has also been described in the literature in terms of a token bucket (leaky bucket), with being the rate of token accumulation, and being the bucket depth. In general, we will be using shapers 4
whose output is a concave, increasing (i.e., f (t1 ) < f (t2 ) whenever t1 < t2 ), piecewise linear function with nite number of slopes, K . We are interested in these types of shapers because they are a generalization of the shapers adopted by the the Internet 15] and ATM standards 1]. These shapers can also be easily implemented by passing the tra c through a series of K ( m m )-shapers 5]. Let A be such a shaper and for the input tra c model described earlier, the delay of packet i through the shaper is 5, Theorem 5.1]
di = At t+ ]
m)
and
(4) (5)
m+ m
where (x)+ = max(0 x). From (4) we can develop a worst case delay bound that depends on the envelope of the input process to the shaper. Taking into account (3) we have that
di
8 ( < max max I ( ) ; m=1 2 ::: K : 0 8 ( < = max : m=1 2 ::: K I ( ) ; max 0 m 8 < D I A := max : 0
m=1 2 ::: K
max
max i I (si ; s) ; s s
m; m m m
m (si ; s) ; m
o +)
)!+9 =
:
(6) (7)
!+ 9 =
We will denote the bound on the delay of tra c with envelope I ( ) through shaper A as,
m=1 2 ::: K
max
I( ) ;
m
!+ 9 =
:
m
(8)
We can write (8) in another form that will be useful in the sequel. The range of A( ) is minm and the inverse of A( ) is given by
1)
(9)
min m
Extending the de nition of A(;1) (y ) by setting A(;1)(y ) = 0 whenever 0 from (8) and (9) that + D(I A) = max A(;1) I ( ) ; : 0
When the tra c entering shaper A is the output of a shaper A1 with envelope A1( ), we will also use the notation D (A1 A) := D A1 A . Notice that if I ( ) A( ) 0, then from (6) we have that D I A = 0 which implies that no packet is delayed in shaper A. In particular, D (A A) = 0. 5
System
5 )
I[t,t+ J ) Shaper
di
(1 )
System
5
Shaper
I[t,t+ J )
Delay 2 i
di
(2 )
2 i + d i(2 )
Figure 2: The Systems S1 and S2 Consider next two shapers A1 , A2 in series. Equations (4) and (5) imply that this arrangement is equivalent to a tra c shaper A3 with envelope
(11)
Equivalence here means that for any input tra c pattern, the delay of every packet from the time it enters A1 to the time it exits A2 is identical to the delay of the packet in A3: Next, we state a useful lemma, that relates the packet delays in the two systems S1 and S2 of Figure 2. System S1 consists of a tra c shaper, A. System S2 consists of a \delay" subsystem and an identical shaper A connected in series. The delay subsystem delays the ith arriving packet by i 0, and then delivers it to A.
all i = 1 2 : : :,
Lemma 1. Assume that packets arrive to systems S1, S2 according to the same arrival process I t t + ]. If d(1) and d(2) are the delays of packet i in the tra c shaper in systems S1 and S2 respectively, then for i i
d(1) d(2) + i i
i
that is, the delays of all packets in system S1 are smaller than their corresponding delay in system S2 .
The proof of the above lemma is given in Appendix A. Lemma 1 identi es the monotonicity property of the shaper with respect to the arrival process. This is an important property of the tra c shapers considered in this paper and is key to establishing the general end-to-end delay bounds for RCS disciplines. 6
Proposition 1. Assume that the output of tra c shaper A1 enters a system S where it is known that the delay experienced by these packets is upper bounded by DS . The output of system S enters shaper A2 . The b total delay, di, that packet i experiences from the time it exits A1 to the time it exits A2 is upper bounded
by
b di DS + D(A1 A2):
7
Original System
I[t,t+ J )
Shaper
System
5
di
Shaper
di
di
(1 )
Modified System
I[t,t+ J )
Shaper
System
5
D 5
Delay D - d 5 Shaper i
di
(2 )
Proof. Let di be the delay of packet i in system S , and let d(1) be its delay in A2. By de nition, i (1) b di = di + di . Consider next a modi ed system where a delay system that delays the ith packet by (2) i = DS ; di , is inserted between S and A2 (see Figure 3). Now let di denote the delay of packet i in A2
i
d(1) DS ; di + d(2) i i
b di DS + d(2): i
Observe now that since the delay of every packet between its entrance time to S and its exit from the delay system is di + i = DS , the tra c entering shaper A2 when the delay system is inserted, is a time-shifted version of the tra c exiting A1 , and therefore it has envelope A1 ( ). Hence, d(2) D(A1 A2). i Note: As explained in Section 2, when the shapers A1 A2 are identical, D(A1 A2) = 0, i.e., in this case reshaping does not introduce extra delays. Also, from the proof we see that any shaper that has the property described in Lemma 1 satis es Proposition 1 as well. In particular, the shaper of 16] can easily be seen to satisfy Lemma 1. Assume now, that connection n passes through M network nodes, numbered from 1 to M , and let M + 1 denote the destination. We then, apply Proposition 1 with the system S consisting of both the 8
scheduler at node m and the link l = (m m + 1), and the shapers A1 Am , and A2 Am+1 . We can n n conclude that the delay that a packet from connection n experiences between the time it exits shaper Am n and the time it exits Am+1 is upper bounded by, n
m Dn(m m + 1) = Dn + T (m m+1) + D Am Am+1 : n n M ;1 X m=1 M ;1 X m=1
(12)
Taking (12) into account we then have the following guaranteed upper bound on the end-to-end delay
Dn = D(I n A1 ) + n
= D(I n A1 ) + n
M Dn(m m + 1) + Dn + T (M M +1)
D Am Am+1 + n n
M X m=1
m Dn +
M X m=1
T (m m+1) :
(13)
m It is important to note that the delay bounds Dn depend on the choice of the tra c shapers Am . Therefore, n one should not conclude from (13) that the end-to-end delay guarantees are minimized by choosing I n ( ) as the envelope for all the tra c shapers so that D(I n A1 ) = D (Am Am+1 ) = 0. In fact, as we will see in n n n the next section, this choice may be quite inappropriate. As in the policies proposed in 16], the delay bounds in (13) are basically a sum of the worst case delays at each node along the path of a connection. However, an individual packet may not encounter the worst case delays at each node. Therefore, one may suspect that these bounds are overly pessimistic and lead to ine cient allocations compared to bounds for other disciplines, that take into account delay dependencies between nodes along the path. As mentioned earlier, the impact of delay dependencies is in general di cult to evaluate but can be accounted for in some instances. In particular, it can be done for the GPS discipline 7, 11, 12], which is one of the reasons that tight bounds can be obtained for this discipline. This argument about the ine ciency of worst-case delay assignment relative to GPS was also mentioned in 16]. In the next section we address this issue, by demonstrating that with a suitable choice of shaper envelopes the RCS discipline can provide the same end-to-end delay guarantees that the best delay bounds of GPS can provide. More speci cally, we show that for a given set of connections, and their associated paths, the RCS discipline can provide the same end-to-end delay bounds as the GPS discipline. In addition, we show that the RCS discipline can accept a set of connections with associated delay requirements, that cannot be accepted by GPS. This demonstrates the advantage of RCS over GPS in providing e cient end-to-end delay guarantees.
function I n( ), and traverses path Pn of the network, 1 n NT . Under these assumptions, we require that the packets of connection n have an upper bound on their end-to-end delay (delay guarantee), Dn, 1 n NT . The vector D = D1 : : : DNT is schedulable under discipline if the delay bound Dn can be guaranteed under for all packets of connection n, 1 n NT . The schedulable region of discipline is the set of all vectors D that are schedulable under . Note that the schedulable region of a service discipline depends on the envelope functions I n( ) and the paths Pn . We say that service discipline 1 is at least as good as the discipline 2 , if the schedulable region of 1 is a superset of 2 , for any given set of connections and paths. If, in addition, there is a set of connections, paths and associated delay bounds that can be guaranteed by 1, but not by 2 , we say that 1 is better than 2. Note that the schedulable region is de ned in terms of delay bounds that can be guaranteed a priori. These bounds are an integral part of the service discipline and may in fact be signi cantly worse than the delays actually experienced by packets. Their choice may be due either to their simplicity or to the fact that these are the only bounds that can be guaranteed and no method is known to derive lower bounds. From the point of view of admission control, it is irrelevant if in the actual operation of a policy smaller delays are observed, since what is required at the time of connection establishment, is to know whether the delay bounds can be guaranteed or not. Before we proceed with the comparison of RCS and GPS disciplines, we need to recall some preliminary results regarding the NPEDF scheduling policy. This policy has the largest schedulable region among the class of non-preemptive policies in the single-node case 8], and is therefore the most e cient to use when considering RCS disciplines. The schedulable region is de ned here with respect to scheduler delays only. The schedulable region for N connections that are entering the scheduler through tra c shapers with envelopes An( ) = L + n + n , 1 n N and contending for an output link of speed r, is given by Theorem 4 in 8], which we repeat here for convenience, slightly rephrased to conform to our de nitions and notation.
Theorem 1. The NPEDF policy is optimal among the class of non-preemptive scheduling policies when
the connection n tra c entering the scheduler has envelope An ( ) = L + n + n , 1 n N . Under the P stability condition N=1 n r, the schedulable region of NPEDF consists of the set of vectors (D1 : : : DN ) n that satisfy the constraints
min fk + 1 N g L +
whenever Di1
k X n=1
in
Dik r ;
k;1 X n=1
in
! k ;1 X
+
n=1
in Din
1 k N:
: : : DiN .
We note that while the optimality of NPEDF was established in 8] for envelopes of the form I n ( ) = L + n + n , it is straightforward to see that all the arguments used to derive Theorem 1 in 8], go through by simply replacing L + n + n with a general envelope An( ) of the type considered here. For these general envelopes, the appropriate analogue of Theorem 1 can be easily derived by simply rephrasing Lemmas 1 and 2 in 8]. 10
n2C m l
rm l :
The GPS policy operates by allocating weight m for connection n whose tra c crosses node m. These n weights are used to determine the rate at which tra c from connection n is served when a set B m of connections is backlogged at the output link l of node m through which connection n passes. Speci cally, the service rate of connection n is given by
m gn = P m n rm m m k k2B rm l as rm when there
where for simplicity in notation we denote is no possibility of confusion. PGPS is a non-preemptive policy that tracks GPS. In general the procedure developed in 11] to obtain delay bounds given the weights, m , is complicated and imposes certain restrictions on the m . Moreover, it becomes even n n more cumbersome in the practically more important inverse procedure of specifying appropriate weights, in order to satisfy predetermined delay bounds. However, a simple bound can be obtained in the special case of non-preemptive RPPS, where m = n for all nodes through which the connection passes. Speci cally, n the end-to-end delay bound, Dn, obtained under non-preemptive RPPS for connection n with envelope I n( ) = L + n + n , that crosses nodes 1 : : : M , is given by,
Dn =
n + ML n
M X L + m=1 r
(14)
where we have replaced n with n + L to conform to our input model (see 12, 9]). From formula (14) we can already see the weakness of the RCS disciplines relative to RPPS, if the tra c shapers for connection n at every node have envelopes identical to the input envelope I n ( ). In this case the delays D(I A1 ) = D (Am Am+1 ) = 0, 1 m M ; 1. Since propagation delays are assumed n n n zero, we therefore have that
Dn =
M X
m=1
m Dn :
m It is easy to see that since the connection n shaper at node m has envelope I n ( ), the delay bound Dn is at least ( n + L)=rm . Therefore, the end-to-end delay bound guaranteed by the RCS discipline veri es,
Dn
M X m=1
n rm
m=1
M X L rm :
11
Since n can be much larger than L, the bounds provided by the RCS discipline under the scenario considered here can be much worse than those obtained under RPPS. For example, if n = 50L and rm = 1:25 n, 1 m M , we have 40:8 M : Dn Dn 50 + 1:8 M Therefore, when M = 2 we already have Dn =Dn 1:52, and for large M , Dn =Dn 22:67. As was mentioned in Section 3, this discrepancy is due to the fact that the bounds for RPPS take into account delay dependencies at the various nodes, while the bounds for the RCS disciplines are based on independently summing the worst case bounds at each node. The previous example notwithstanding, we show next that we can design RCS disciplines that provide the same delay guarantees as RPPS, by employing tra c shapers with envelopes that are, in general, di erent from that of the input tra c. We design the RCS discipline as follows. We choose NPEDF as the scheduling policy at the output link of each node. The tra c shaper for connection n at each node along its path has envelope
Am ( ) = L + n
1 m M:
Assume that connection n is routed through output link l at node m and let rm denote the speed of this link. For connection n, we specify the delay bounds for the NPEDF scheduling policy, at node m as
m Dn = L= n + L=rm :
(15)
Let us rst show that these bounds can be guaranteed by the NPEDF policy at every node. Consider output link l at node m. Denote by N the total number of connections multiplexed on this link, and index the connections by i1 i2 : : : iN such that Dim Dim : : : Dim . Using Theorem 1, and noting that 1 2 N m = 0 for all tra c shapers by design, it su ces to show that n min fk + 1 N g L Using (15) we have
Dim k
1 k N:
(16)
Dim k
rm ;
n=1
m in Din
rm ; Pk;1 n=1 = L
ik
in
+(k ; 1)L + L
m = Lr ;
Pk;1
rm ; Pk;1 n=1 +L rm
n=1 in rm
in
Pk;1
ik
n=1 in
(k + 1)L
PN
n=1 i.
We now proceed to derive the end-to-end delay bounds for the connections. Since the tra c shapers are identical, we have that D (Am Am+1 ) = 0, 1 m M ; 1. Therefore, from (13) we have n n
D n = D I n An +
1
M X m=1
m Dn :
D I n An = max I n ( ) ; L ; 0
n
n: n
Dn =
=
n n
m=1 n
M M XL X L + rm
n + ML n
m=1
M X L rm :
m=1
(17)
Since (14) is identical to (17) we see that the proposed RCS discipline can guarantee the same delays as RPPS. From the above argument we see that if the delay bounds in (14) are required by the connections in the network, then the RCS discipline , proposed above can be used. Its implementation is simpler than that of RPPS. In addition, it provides the exibility of easily specifying other delay bounds, whereas the bounds in RPPS are tied to the rate n of a connection. If the end-to-end delay requirements of a connection are smaller than (14), a slightly more general version of RPPS can be used. Rather than providing a rate of n to connection n, better delay performance can be obtained by giving it a rate of gn n, at each node. The end-to-end delay bound is then given by,
Dn =
n + ML gn
M X L + rm : m=1
(18)
The previous analysis still applies with very little modi cation and can be used to specify an RCS discipline that guarantees the bounds in (18). In this case, all tra c shapers have envelopes Am ( ) = L + gn and n the delay guarantees at the scheduler of node m are,
m Dn = L=gn + L=rm : m Observe that, the schedulability check for RPPS is now l2Cn gl rm , m = 1 : : : M , where Cn denotes m the set of connections that are multiplexed on the same link as connection n at node m. This implies P m that some amount of bandwidth viz. rm ; l2Cn gl , cannot be utilized by RPPS. This bandwidth can be used by an RCS discipline to accept additional connections that require relatively larger end-to-end delay guarantees. At the end of this section we provide a speci c example of this bene t of RCS disciplines over the more general GPS disciplines.
13
The proof can be found in Appendix A. For our purposes, the case where I n( ) = minfcn n + n g cn n , n en will be of interest. For convenience, we summarize in the next corollary two speci c cases of Lemma 2 that will be useful in the rest of this section. recall from 11] that Sn(t) is a piece-wise linear function, convex in the range 0 tB ] where tB is the end of the rst busy period of connection n, when all the N connections are greedy. In this range, Sn (t) is characterized by the pairs (sk bk)kn where k=1 sk is the slope of the kth segment and bk is its duration. Because of the convexity of Sn(t) we have that
s1 s2 : : : skn :
Corollary 1. Assume that the conditions of Lemma 2 hold, so that I l ( ) el + l , and furthermore let I n ( ) = minfcn n + n g en + n , cn n, 0.
1. If s1
0, 1
N,
cn, then Dn = 0.
14
D n
*n
~ _ en _
D n
_ In (J) Sn (J)
*n
_ cn sj
sj-1 s1
0
b1 bj-1
The rst part of the corollary follows by observing that s1 cn implies that I n ( ) Sn( ) and therefore
A geometric interpretation of the second part is given in Figure 4. The development of GPS bounds for connection n is based on the Universal Service Curve (USC) for that connection 12, Section VIII]. Just as Sn(t) characterizes the service that connection n receives at a single node, the USC of a connection characterizes the end to end service that it receives. We summarize here the method by which the USC is obtained when all the nodes use a GPS discipline. 12].
m 1. Under a CRST weight assignment, an algorithm is developed by which an envelope function, n + n is guaranteed for every connection n tra c entering node m 12, page 142]. For our purposes, it is important to note that, 1 m (19) n 2 m M: n= n n
2. Given the envelope functions lm + l , for all connections that are multiplexed with connection n m on the same output link at node m, the service function for connection n, Sn ( ), is calculated. Let m m (sm bm), k = 1 : : : kn be the set of slopes that characterize Sn ( ). k k 15
o P Pm
kn m M where GM ( ) is de ned as in nity for > M=1 kn bm , and for n k=1 k m m=1 k=1 bk it is composed m m of the segments (sm bm), m = 1 : : : M , k = 1 : : : kn of Sn ( ), arranged in a nondecreasing order k k P m b b of slopes 12, page 144]. We denote by (sk bk), k = 1 : : : M=1 kn this nondecreasing order. m
(20) We are now ready to design an RCS discipline that is at least as good as GPS. Consider rst the design of tra c shapers. Recall from the beginning of Section 4.1, that for the purpose of comparison with GPS we assume that the envelope of connection n tra c entering the rst tra c shaper is of the form I n( ) = n + n (Recall, that we have assumed L = 0). For connection n, at each node m on the path, we choose tra c shapers that have the same envelope i.e. Am ( ) = min fcn n + n g. To specify how n the parameter cn is picked, we need to distinguish between two classes of connections.
n
b sk <
b k = 1 : : : kq ; 1 skq
n:
0kq;1 1 b Xb Sn @ bk A <
(21)
b where the USC, Sn is de ned as above. In this case, the delay bound for connection n tra c under GPS is given by the solution of the equation 13, p. 136] (see Figure 5.i), b Dn : S(Dn) = n:
Let k kq , be the index of the slope of the USC at time Dn . If at time Dn there is a change in slope, then de ne k as the index of the smaller of the two slopes (in fact either slope would work). b We set cn = sk . 2. Class (b). Connection n belongs to this class when ,
0kq;1 1 b Xb Sn @ bk A
k=1
n:
In this case, the delay bound for connection n tra c under GPS is 13, p. 136] (see Figure 6.i),
Dn =
We then set cn = n.
kq ;1 X k=1
b Pkq;1 b bk ; Sn k=1 bk ; n : b
n
16
m For connection n, we assign the scheduler delay at node m, Dn , to be equal to the maximum delay that would be experienced by the connection under the GPS scheduling policy at that node, when the conditions of Corollary 1 are satis ed. This amounts to the following assignment.
If at node m, sm 1
jX1 m; k=1
bm ; k
where
bm k
!,
cn:
We rst establish that the speci ed delays can be guaranteed by the EDF policy at each node. Instead of using the extension of Theorem 1 to general shaper envelopes, it will be simpler to argue indirectly as follows: we will show that the speci ed delays are guaranteed when the RCS discipline uses GPS as the scheduling policy at each node. Since EDF is better than GPS in the single node case, it will follow that the same delay guarantees can at a minimum be provided when the EDF scheduling policy is employed. m Observe that according to (19), we have that Av ( ) v + v for any connection v that is multiplexed with connection n on the same output link of node m . It is also true that cn n. This follows by de nition for a connection in class (b). For a connection in class (a), observe that because of (20) and the fact that b b b sk , k = 1 2 : : :, is nondecreasing we have cn = sk skq n. Applying Corollary 1 (where we replace m m en n ), we conclude that the delay Dn = 0 can be guaranteed under the GPS policy for any node m for which sm cn. For a node m, where sm < cn, k = 1 : : : jm ; 1, sm cn , we apply part 2 of Corollary 1 k jm 1 and, therefore, we rst need to show that
m Sn jX1 m; k=1
bm k
cn n cn ; n :
k ;1 ! bn X bk S b k=1 n
This is trivially true for a connection in class (b) since cn n=(cn ; n) = 1. If connection n belongs to b b class (a), observe that from the de nition of sk , jm and Sn ( ), we have (see Figure 5),
m Sn jX1 m; k=1
bm k
n b sk ; n :
b sk
Thus, we have established that in both cases (a) and (b), the speci ed delay bound can be guaranteed at node m. Next, we need to establish that the end-to-end delay guarantee of the RCS discipline as given by (13), does not exceed Dn . The delays D(Am Am+1 ) are all zero since the tra c shapers are identical. Recall that the input tra c envelope for connection n, I n( ) = n + n , and so from (8), the delay in the rst tra c shaper is D I n A1 = cn :
n
17
End-to-End Delay
D
^ S n( J)
D
m *n _
*n h 0
A_
hm
hm
hm
^* s
3
S n( J)
*n
_ cn E h1
m m s4
^ sm ^ sm ^ sm
1
h2
h3 sm
3
m s1
m s2
_ * Dn
J
Dn
m
(i)
(ii)
Figure 5: Delay Decomposition of a Class (a) Connection Therefore, it su ces to show that
n cn M X m=1
m Dn = Dn:
(22)
m m m Let M0 be the set of nodes for which Dn > 0. Obviously then, M=1 Dn = m2M0 Dn . Assume rst that m b connection n belongs to class (a). Observe that the set of slopes sk k = 1 : : : k ; 1, can be partitioned into subsets Fm , m 2 M0 , where
b k b We denote by mk the index l for which sl = sm , i.e., smk = sm . For the rest of the discussion, it is best k b b to use geometric arguments. Referring to Figure 5.i, draw lines with slope sk from all the points in Sn ( ) b where the slope changes and remains less than sk . These lines intersect segment AB (corresponding to the delay Dn) and divide it into segments of length hk , 0 k k ; 1, where segment hk corresponds b b to slope sk , 1 k k ; 1. Denote by hmk the segment that corresponds to smk . Since by construction h0 = n=cn, we then have
Dn = cn +
n
m; X jX1
m2M0 k=1
hmk :
(23)
m b Similarly, in Figure 5.ii, draw lines with slope sk from all the points in Sn ( ) where the slope changes m b and remains less than sk . These lines intersect segment EF (corresponding to the delay Dn ) and divide
18
End-to-End Delay
^ S n(J)
h0
hm
hm
hm
cn= D
3
S ( J)
n
n m s4
B ^ sm
*n
^ sm
*n _
E
m s1
h1
m s2
h2 h 3 sm
3
^ sm
_ Dn*
J
Dn
m
(i)
(ii)
Figure 6: Delay Decomposition of a Class (b) Connection it into segments hm , 1 k jm ; 1 (in the gure we have jm ; 1 = 3). We can then write, k
m Dn = jX1 m; k=1
hm : k
(24)
b Using the facts that smk = sm and that bmk = bm , it can be easily seen that hmk = hm . Taking into account b k k k (23) and (24), we conclude the correctness of (22). Similar arguments can be made for a connection that belongs to class (b). The main di erence is that we now draw lines with slope n. Figure 6 illustrates the construction in this case. Note: In the course of the previous argument we showed that the delay guarantees provided by a pure GPS policy can also be achieved by an RCS discipline working with worst case delays at each node, where the scheduling policy at each node is GPS. If we replace GPS with the (simpler) EDF scheduling policy at each node, we are not only assured that we can still guarantee the GPS end-to-end delays, but we also create a service discipline that is better than GPS. This is due to the fact that in the single node case, EDF is better that GPS. That is, there are delay vectors that can be guaranteed by EDF but cannot be guaranteed by GPS no matter what weights are chosen. For example, consider a link of capacity r, where two connections are multiplexed and I n( ) = n + n , n = 1 2, with 1 + 2 r. Using Theorem 1 with L = 0, we can see that the delays that can be guaranteed by EDF policy are
D1 = r1 D2 = r ;2 + r1 1
19
For GPS on the other hand, it can be seen from the construction in 11, Section VI.C], that in order to guarantee D1 = 1=r we need to specify 2 = 0, and then the minimum guaranteed delay for connection 2 is D2 = r ;2 + r ;1 :
1 1
The di erence between the GPS and EDF delay guarantees for connection 2 is
D2 ; D2 = r(r 1 1 ) ; 1
which can be quite large. Similar examples can be given for the packetized model when comparing PGPS to NPEDF. In this section, we have shown how \proper" selection of the tra c shapers allows us to construct an RCS discipline that outperforms GPS. In general, it is of interest to determine how the choice of shaper envelopes impacts the performance of rate controlled service disciplines. This is the topic of the next section. Note that so far we have always used identical shapers at all nodes. Di erent shapers could however, be used at each node albeit at the cost of greater complexity. The question then is whether the use of di erent shapers a ords su cient bene ts that compensate for the increase in complexity. We address this issue in the next section, together with an investigation of how shaper envelopes impact the performance of RCS disciplines.
m 0, Am ( ) is also an envelope for the tra c exiting Bn . n m By de nition, Dk remains an upper bound on the delay of any connection k tra c as long as connection n still has envelope Am( ). n We will show next (Proposition 2), that it su ces to restrict attention to RCS disciplines that for the same connection, use identical shapers at all nodes. We rst need some notation. We write A1 A2 (or A2 A1) whenever A1( ) A2( ), 0. We denote by A1 ^ A2 the arrangement of A1 and A2 in series. Since the output of shaper A1 has envelope A1( ), it follows that
D (A A1 ^ A2 ) D (A A1 ) + D (A1 A2) :
20
(25)
Ai A1 ^ A2 i = 1 2:
(26)
Proposition 2. Consider connection n that traverses nodes 1 2 : : :M and let I n( ) be its envelope at the input to the rst shaper.Given any RCS discipline that uses shapers Am , and guarantees scheduler delays n
m Dn , 1 m M , the RCS discipline m Bn = B = ^M=1 Am m n
0 that uses the same scheduling policy at all nodes as , and shapers
Proof.
Dn = D I n B +
Finally observe that by (25)
M X
m=1
m Dn +
M X
m=1
( Tnm m+1) :
D In B
0
D I n A1 + n
M ;1 X m=1
D Am Am+1 : n n
Using (13) again we conclude that Dn Dn . Note: According to Proposition 2 we can restrict our attention to disciplines that use identical shapers at all nodes. However, formula (13) can still be useful in a heterogeneous environment, where the various nodes are not designed to support identical shapers. In the rest of this section, we consider disciplines that use identical shapers, i.e. Am = An . Then, the n end-to-end delay guarantee for connection n becomes
Dn = D I n An +
M X m=1
m Dn +
M X m=1
( Tnm m+1) :
(27)
We consider next, the problem of constructing the \smallest" shaper that causes a speci ed maximum delay on the input tra c I n ( ). Speci cally, given d 0, we want to construct a shaper An (d) such that D I n An(d) d and An(d) A, for any shaper A, with D I n A d. Recall that U n( ) denotes the input tra c envelope of connection n before the rst packetizer in the network (see Figure 1). We further assume that the input tra c envelope, U n ( ), is an increasing, concave, piecewise linear function with a nite number of slopes. In Appendix B, we show that these assumptions on the input tra c envelope do not entail any essential loss of generality. We can write U n ( ) in the form (see Figure 7)
nk
(28)
_ Un (J ) _ ad (J ) Qk*
*n,K _
*n,1 _
* cn(d)
_ U n(J -d)
Jn,k*
d
Jn,k* + d
<
n k+1
and when K
n k ; n k;1 n k;1 ; n k
<
n k+1 ; n k n k ; n k+1
k = 2 : : : K ; 1:
Let n 1 = 0 and n k = ( n k ; n k;1)/ ( n k;1 ; n k ), 2 k K . At the point Pk = ( n k n k + n k n k ), the slope of the envelope, U n( ), changes from n k;1 to n k. According to (1) the envelope of the tra c entering the rst shaper is, I n( ) = L + k=1 ::: K f n k + n k g : min Now, let A( ) = L + minj =1 ::: J f j +
g be the envelope of A. According to (7), D I n A = 1 when minj =1 ::: J f j g < n K , while D I n A n K = n K whenever minj =1 ::: J f j g n K . Therefore, it is
j
n K= n K.
Proposition 3. Let 0 d
Let k be the smallest index k such that the line with slope passing through the point Qk = n k + d U n( n k) intersects the y -axis at nonnegative values, i.e.,
n K = n K.
nk
n k)
n k ( n k + d)
0 :
22
Then, the envelope of the smallest shaper An (d), such that D I n An(d)
d is
An (d)( ) = L + ad ( )
where, denoting cn(d) := U n (
nk
)=(
nk
ad( ) =
+ d),
cn (d) if 0 U n ( ; d) if
nk
<
+ d:
nk
+d
= =
n K + n K n K ; n K ( n K + d) nK ; nK
0:
Next, we show that An (d)( ) corresponds to a shaper envelope function. For this, it is su cient to show that An (d)( ) is a concave function, which will follow by construction, if we show that cn(d) n k but this is a consequence of the de nition of k . To show that D I n An (d) d, recall that according to (10) we can write + D I n An(d) = max A(n;1) (d) I n( ) ; 0
d, for all 0. Finally, we need to show that An (d)( ) A( ) for the envelope of any other shaper A such that D I n A d. To see this, observe that if An (d)( ) > (;1) A( ) for some An(d)( ) > . Also, by construction, An(d)( ) = I n( ; d), n k + d, then A n k + d. From (10), for all n k + d we have, D In A A(;1) I n ( ; d) ; ( ; d) > ; ( ; d) = d
a contradiction. Therefore, An(d)( ) A( ) for all n k + d. Using the inequalities An (d)(0) = L A(0), An(d)( n k + d) A( n k + d) and the concavity of A( ), we conclude that we also have An (d)( ) A( ) for 0 n k + d as well. Using now Lemma 3 and Proposition 3, we easily conclude that given the input envelope function I n ( ), and a maximum shaper delay d, it is su cient to restrict our attention to RCS disciplines that use shapers with envelopes of the form An (d)( ):
Corollary 2. Given an RCS discipline that for connection n uses shaper A at all nodes, the RCS discipline that uses the shaper with envelope An(d)( ), where d = D I n A , can guarantee the same end-to-end
23
From the above discussion we see that given I n( ), the search for the appropriate shaper envelope, is reduced to the one-parameter family An(d)( ). We can further constrain the range of the parameter d by taking into account the link speeds, rm , along the path of connection n. This is done in the next proposition, where it is shown that it is su cient to restrict attention to envelopes An (d)( ) whose maximum slope cn(d) (peak rate) is not larger than the minimum of rm .
Proposition 4. Consider connection n with input tra c envelope U n( ) that traverses nodes 1 : : :M with
corresponding output link speeds rm . Then, given an RCS discipline that uses shaper envelope An (d)( ), there is an RCS discipline using shaper envelope An(d0)( ) with peak rate cn(d0) such that
nK
cn(d0) min
m=1 ::: M
min
m=1 ::: M
min frm g cn
where cn is the peak rate of U n ( ), i.e., cn = same end-to-end delays to all connections.
if
n1
we have
nK
cn(d)
cn(d) cn :
m Denote by Un +1 t t + ] the connection n tra c entering node m + 1 in the interval t t + ]. Then, since the output link of node m has speed rm , m Un +1 t t + ] rm :
Therefore, for the tra c exiting the packetizer at node m + 1, we have (see (1))
m In +1 t t + ] Bm ( ) = L + rm :
Therefore, we can replace An (d) with Bm ^An(d), without altering the shaper delay or the scheduler delay at node m + 1, m = 1 : : :M ; 1. Also, by introducing a shaper with envelope B M ( ) at the exit point of connection n, we do not a ect the end-to-end delay guarantees. Using Proposition 2, we conclude that the delay guarantees are not a ected if we employ the RCS discipline that uses shapers
m Bn = Bn = An(d) ^M=1 Bm m
But then, for the peak rate c0n of the envelope of shaper Bn, we have
c0n min
m=1 ::: M
min
m=1 ::: M
min frm g cn :
Let d0 = D(I n Bn). Using Corollary 2, we can replace Bn with shaper An (d0) without altering the delay guarantees for any connection. Since by design An (d0) Bn , we must have cn(d0) c0n and the proposition follows. 24
In the important special case of shapers used in the ATM standards 1] and those proposed for the Internet as well 15], we have
U n( ) = min fcn
In this case,
n 2 = n = (cn ; n),
n+ n
g cn > n:
<
n2+d
ad( ) =
k = 2,
(cn n) =( n + d(cn ; n)) if 0 if n + n ( ; d)
n 2 + d:
cn n min n + d(cn ; n)
m=1 ::: M
min frm g cn :
Therefore, to specify an RCS discipline, one has to determine the single parameter d as well as the scheduler m delays, Dn for each node m along the path of connection n. The determination of these parameters is an interesting design problem, which is the subject of ongoing research and is not addressed in this paper. The use of tra c shapers at each hop can introduce extra delays for the tra c of connection n, even if there is no congestion in the network. While this leads to a reduction of jitter and bu er requirements at each node in the network, there may be instances where the resulting increase in the average delay is undesirable. In the next section we describe some simple modi cations to the RCS discipline that make it work conserving, without compromising the end-to-end delay guarantees that can be provided.
scheduler in the non-work conserving discipline, NW , only selects packets in Qm for transmission on the e output link. Once a packet has completed its transmission it is removed from Qm and the scheduler repeats e the above process. Packets from each of the connections at node m enter Qm in conformance with their respective tra c e envelopes. The call admission criteria, ensures that packets in Qm can be scheduled without violating e their deadlines. Note that NW is non-work conserving since packets can be queued in Qm , but are not considered for transmission by the scheduler, even though the link may be idle. We now develop a work-conserving discipline W , by modifying the scheduler in NW as follows. Whenever Qm is empty, ineligible packets from Qm are transmitted (in any order). Next, we specify the operation e of scheduler during periods when Qm is non-empty. If Qm is non-empty at time t de ne a Qm -busy period e e e m is non-empty. Let t0 denote the start of at t to be the largest closed interval containing t, during which Qe one such busy period. Note that at time t0 it is possible that an ineligible packet is being served, in which case let ts denote the time that the ineligible packet begins transmission otherwise de ne ts := t0 . Let q be the packet that begins transmission at time ts. Consider the sequence of packet arrivals consisting of packet q , whose arrival time is set to ts , along with the other packets that arrive to Qm during the e m -busy period. Assume that this sequence is fed to the scheduler in NW with packet q corresponding Qe being the rst packet to ever arrive at that scheduler. The scheduler in W then schedules this sequence of packets in the same manner as the scheduler in NW . Note that if the scheduler in NW is NPEDF (FCFS, PGPS, Fixed-Priority scheduler, etc.) the corresponding scheduler in W is again NPEDF (FCFS, PGPS, Fixed-Priority scheduler, etc.) during a Qm -busy period. The next proposition shows that the e end-to-end delay guarantees are not a ected when the service discipline at each node is modi ed to be work-conserving, as de ned above.
does not increase the guaranteed upper bound on the end-to-end delays. If Dn is the end-to-end delay guarantee for connection n, we still have,
Proposition 5. Let connection n traverse nodes 1 : : : M . The above modi cation to the service discipline
M ;1 X m=1 M M ;Am Am+1 + X Dm + X T (m m+1): D n n n n m=1 m=1
D n D I n An +
1
( Assume for clarity in the exposition that the propagation delays, Tnm m+1) , 1 m M , are zero. We rst establish that with the above modi cation to the service discipline, the scheduler delays at m node m, 1 m M , are still upper bounded by Dn .
Proof.
scheduler in node m, 1 m M .
W,
The proof of the above lemma can be found in Appendix A. We denote by tli m , the timestamp with which the ith packet is enqueued in Qm tli m is the time that the ith packet would leave shaper Am in n m m (to be transmitted conformance with the tra c envelope An ( ) . The time at which the packet leaves Q 26
*W )
m+1 n
)
ti
a,m
m n
5
ti
l,m
)
ti
d,m
5
t il,m+1
m+1
ti
a,m+1
M odified System
)
ti
a,m
m n
5
ti
l,m
Delay
)
^ ti
d,m
m+1 n
m+1
ti
d,m
^ til,m+1
Figure 8: Original (work conserving) system and the modi ed system on the link or promoted to Qm ) is denoted by ta m . If the link is idle, the packet may be transmitted before i e it becomes eligible, i.e., ta m tli m . The departure time of the ith packet from the scheduler is denoted as i d m . Similarly, let ti i a be the arrival time of the ith packet of connection n to the rst tra c shaper, and let i d be the time it arrives at its destination. Since ta m tlnm , 1 m M , we can write n
id; ia
tlnM ;
=
M ;1 ; X m=1
aM i a + i d ; tn aM i a + i d ; tn :
Let Sm be the system consisting of the scheduler at node m. Consider the modi ed system which is same as the work conserving system operating under W except for a delay system inserted between Sm m and shaper Am+1 as shown in Figure 8. The delay system delays packet i by i = Dn + tli m ; td m i n m bd m = Dn + tli m . First we verify that i 0, therefore, packet i departs the delay system at time ti
i m = Dn + tli m ; td m i
27
m Dn + ta m ; td m i i 0:
(30) (31)
Inequality (30) follows because packets never depart the shaper later than they are supposed to, i.e., tli m ta m , and (31) follows from Lemma 4. Let bli m+1 be the timestamp with which packet i is enqueued t i m+1 in the modi ed system. From Lemma 1, we conclude that in Q
(32)
m Since for all i, bd m = tli m + Dn , the tra c exiting the delay system has envelope Am ( ). Therefore, ti n
7 Conclusions
In this paper, we have established that RCS disciplines o er a powerful solution to provide end-to-end delay and throughput guarantees in high speed networks. We showed that the main disadvantage of these service disciplines, namely that of summing worst case delays at each node to determine end-to-end delay bounds, can be overcome through \proper" reshaping of the source tra c. In particular, we have shown that controlling the peak rate of a connection as a function of its delay requirements is critical to e cient network QoS provisioning. How to perform this reshaping was also investigated in the paper, and illustrated by designing RCS disciplines that outperform GPS. This is signi cant since the bounds available for these policies take dependencies between nodes into account. In addition to their e ciency, RCS disciplines are also relatively simple to implement, and o er the exibility to accommodate a wide range of implementation constraints. For example, it is possible to use di erent schedulers and shapers at di erent nodes depending on the capabilities available locally. Furthermore, because we also showed that guarantees are not a ected when operating in a work conserving manner, i.e., reshaping tra c only in case of congestion, RCS disciplines also enable us to o er low average delays when the network is not congested. Finally, note that the greater exibility of RCS disciplines also introduces new and interesting problems, e.g., how to best split a given end-to-end delay budget into local delay bounds, and addressing them is the topic of ongoing work. 28
We are indebted to Raju Rajan for suggesting the proof to Lemma 1 as well as numerous insightful comments on early versions of this paper. We would like to thank Abhay Parekh for many fruitful discussions regarding the comparative performance of GPS and EDF, and Subir Varma for prompting us to look into the issue of the e ciency of RCS disciplines as well as for many comments which helped improve the paper. We would also like to thank Armand Makowski for many helpful discussions and comments on an earlier draft.
Acknowledgements
Appendix
A Lemma Proofs
denote the arrival times, and fi(1), fi(2) denote the departure times of the ith packet at the shapers of system S1 and S2 respectively (see Figure 2). By de nition, s(2) = s(1) + i , with i 0, and therefore it i i su ces to show that fi(1) fi(2) i = 1 2 : : : Since A(0) L, the rst packet leaves the shaper instantaneously in both the systems, i.e. f1(1) = s(1) and 1 (2) (2) (1) (2) f1 = s1 . Therefore, we have f1 f1 . Let li denote the length of the ith packet, and assume that
Proof of Lemma 1. Let A( ) denote the envelope of the shaper with A(0) L. Also, let s(1), s(2) i i
fi(1) fi(2)
i = 1 2 : : : m:
m+1 X k=i m+1 X k=i m+1 X k=i
(33)
From (2) we can compute the departure time for the (m + 1)th packet in system S1 as,
(1) m+1
= minft s
(1) m+1
: A(t ; fi )
(1)
minft s(2) : A(t ; fi(1) ) m+1 minft s(2) : A(t ; fi(2) ) m+1
(2) = fm+1
where (34) is because s(2) s(1) , and (35) follows from the non-decreasing nature of the the shaper m+1 m+1 envelope, A( ), and the induction hypothesis, (33).
29
Proof of Lemma 2. The busy period containing t is de ned as the largest closed interval containing
period can have positive delays and, therefore, we only need to consider the delays of such tra c (since by de nition Dn 0). Assume that connection n tra c arrives at time tb which is within a busy period of connection n that starts at time t0 . Then, since the order of service within a connection is FCFS, the delay of the connection n tra c arriving at time tb is given by,
t, during which the backlog of connection n is positive. Note that only tra c arriving during a busy
= tmin ft0 : Sn 0 t0) + Sn t0 t0] In 0 t0) + In t0 tb]g ; tb 0 tb = tmin ft0 : Sn t0 t0 ] In t0 tb]g ; t0 ; (tb ; t0 ): 0 tb
The last equality follows from the fact that since t0 is the start of a connection n busy period, Sn 0 t0) = In 0 t0). Setting t = t0 ; t0 and = tb ; t0 , and observing that
t0 tb
we then get
d(tb) = min ft : Sn t0 t + t0 ] In t0 tb ]g ; : t
Now, since the connection n tra c satis es I t t + ] n + n , t 0, from Lemma 10 in 11], we conclude that Sn t0 t + t0 ] Sn(t): Since by de nition we also have In t0 tb] I n(tb ; t0 ) it follows that n o ft : Sn t0 t + t0] In t0 tb]g t : Sn(t) I n(tb ; t0) and therefore, min ft : Sn t0 t + t0 ] In t0 tb ]g min t : Sn(t) I n (tb ; t0 ) : t t
30
as de ned in Section 6 and repeat some notation for the sake of clarity. We denote by the timestamp with which the ith packet l m is the time that the ith packet would leave shaper Am in conformance is enqueued in Qm recall that ti n m m (to be transmitted on the link with the tra c envelope An ( ) . The time at which the packet leaves Q or promoted to Qm ) is denoted as ta m and we say that the packet arrives at the scheduler at time ta m . If i i e a m tl m . The departure the link is idle, the packet may be transmitted before it becomes eligible, i.e., ti i time of the ith packet from the scheduler is denoted as td m . We need to show that for any packet i, i
m td m ; ta m D n i i
scheduled before they become eligible can never miss their deadline. All the eligible packets are scheduled in Qm -busy periods, and so it su ces to show that packets that enter Qm are never delayed by more than e e m Dn . Let t0 tf ] be a Qm -busy period. At time t0 a packet either starts transmission or is in the process of e being transmitted and recall that ts t0 is the time that this packet starts transmission. If ts = t0 (in this case a packet from Qm starts transmission at t0 ), then the tra c of all connections arriving to the e scheduler in ts tf ] are conformant to their respective tra c shapers. In addition, in the interval ts tf ] the operation of the scheduler in W is identical to the one in NW if ts were the start of the rst busy period. m Thus, for ts = t0 the result is true by the de nition of Dn . Now assume that ts < t0 , i.e., an ineligible packet from connection j starts transmission at ts . Observe that in a busy period t0 tf ], the scheduler in W only schedules packets that are in Qm , except for the e packet that is being transmitted at the start of the busy period. We will show next that the packets of all connection that have been transmitted in the interval ts tf ] have arrived to the scheduler in conformance with their respective tra c envelopes. The truth of the lemma will then follow as before. Recall that Am t1 t2] denotes the tra c from connection n that is promoted to Qm in the interval n e bm t1 t2] denote the connection n tra c that arrives at the scheduler in the interval t1 t2]. t1 t2]. Let An We need to show that bn Am t1 t2] Am(t2 ; t1 ) ts t1 t2 tf : n Since we are only concerned with node m here, we drop the superscript m for the sake of clarity. By the de nition of t0 , we have that for any connection n,
m Dn has to be larger than the time it takes to transmit a complete packet, and so packets that are
An t1 t2] An(t2 ; t1 ) t0 t1 t2 tf :
For a connection n 6= j , we have in addition, An ts t0) = 0 and therefore,
An t1 t2] An(t2 ; t1 ) ts t1 t2 tf n 6= j:
(36)
b Note also that by de nition An t1 t2 ] = An t1 t2], ts t1 t2 tf , holds for n 6= j since connection j is the only connection which transmits an ineligible packet in ts tf ].
31
Consider next connection j , and let pj be the packet that starts transmission at ts . Let e denote the ^ eligibility time of packet pj . If e tf , then clearly Aj t1 t2] L Aj (0) ts t1 t2 tf , since no more packets from connection j will be transmitted in ts tf ]. Now suppose ts e < tf . Then, all other packets of connection j will arrive after e . For the case when ts t1 e and e t2 tf , we have ^ Aj t1 t2] Aj (t2 ; e ) Aj (t2 ; t1 ): The other cases can be similarly checked.
b b b D In An(d) ^ A = max D In An(d) D(In A) d: nb o b But the shaper An( ) ^ A has envelope B ( ) = min An (d)( ) A( ) . Since A( 0) < An (d)( 0), the b envelope B ( ) is strictly smaller than An (d)( ), which contradicts the optimality of An (d).
References
1] ATM UNI Speci cation, Version 3.1, ATM Forum, September 1994. 32
2] C.-S. Chang. Stability, queue length and delay of deterministic and stochastic queueing networks. IEEE Transactions on Automatic Control, 39(5):913{931, May 1994. 3] D. Clark, S. Shenker, and L. Zhang. Supporting real-time applications in an integrated packet network: Architecture and mechanisms. In Proceedings of ACM SIGCOMM'92, Baltimore, MD, August 1992. 4] R. L. Cruz. A calculus for network delay, part I: Network elements in isolation. IEEE Transactions on Information Theory, 37:114{131, January 1991. 5] R. L. Cruz. A calculus for network delay, part II: Network analysis. IEEE Transactions on Information Theory, 37:132{141, January 1991. 6] R. L. Cruz. Service burstiness and dynamic burstiness measures: A framework. Journal of High Speed Networks, 1(2):105{127, 1992. 7] A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Journal of Internetworking: Research and Experience, 1:3{26, January 1990. 8] L. Georgiadis, R. Guerin, and A. Parekh. Optimal multiplexing on a single link: Delay and bu er requirements. Research Report RC 19711 (97393), IBM, T. J. Watson Research Center, August 1994. Short version appeared in Proceedings of INFOCOM'94. 9] P. Goyal and H. Vin. Generalized guaranteed rate scheduling algorithms: A framework. Technical Report TR-95-30, Department of Computer Sciences, University of Texas at Austin, 1995. 10] D. D. Kandlur, K. G. Shin, and D. Ferrari. Real-time communication in multi-hop networks. In Proceedings of INFOCOM'91, pages 300{307, 1991. 11] A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to ow control in integrated services networks: The single-node case. IEEE/ACM Transactions on Networking, 1(3):344{357, June 1993. 12] A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to ow control in integrated services networks: The multiple node case. IEEE/ACM Transactions on Networking, 2(2):137{150, April 1994. 13] A. K. J. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks. PhD thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, February 1992. No. LIDS-TH-2089. 14] D. Pollard. Convergence of Stochastic Processes. Springer-Verlag, 1984. 15] S. Shenker and C. Partridge. Speci cation of guaranteed quality of service. Internet Draft, draft-ietf-intserv-guaranteed-svc-04.txt, Integrated Services WG, IETF, 1995. 16] H. Zhang and D. Ferrari. Rate-controlled service disciplines. Journal of High Speed Networks, 3(4):389{ 412, 1994. 17] Q. Zheng and K. Shin. On the ability of establishing real-time channels in point-to-point packetswitching networks. IEEE Transactions on Communications, 42(3):1096{1105, March 1994. 33