Description
Scheduling is the process of deciding how to commit resources between a variety of possible tasks. Time can be specified (scheduling a flight to leave at 8:00) or floating as part of a sequence of events
Carry-Over Round Robin: A Simple Cell Scheduling Mechanism for ATM Networks
Debanjan Saha
y
Sarit Mukherjee
z
Satish K. Tripathi
x
We propose a simple cell scheduling mechanism for ATM networks. The proposed mechanism, named Carry-Over Round Robin (CORR), is an extension of weighted round robin scheduling. We show that albeit its simplicity, CORR achieves tight bounds on end-to-end delay and near perfect fairness. Using a variety of video tra c traces we show that CORR often outperforms some of the more complex scheduling disciplines such as Packet-by-Packet Generalized Processor Sharing (PGPS).
Abstract
This work is supported in part by NSF under Grant No. CCR-9318933 and Army Research Laboratory under Cooperative Agreement No. DAAL01-96-2-0002. A short version of the paper appeared in the proceedings of IEEE Infocom'96. y IBM T.J. Watson Research Center, Yorktown Heights, NY 10598. Email:[email protected]. z Dept. of Computer Science & Engg. University of Nebraska, Lincoln, NE 68588. Email:[email protected]. x Dept. of Computer Science, University of Maryland, College Park, MD 20742. Email:[email protected].
1 Introduction
This paper presents a simple yet e ective cell multiplexing mechanism for ATM networks. The proposed mechanism, named Carry-Over Round Robin (CORR), is a simple extension of weighted round robin scheduling. It provides each connection a minimum guaranteed rate of service at the time of connection setup. The excess capacity is fairly shared among active connections. CORR overcomes a common shortcoming of most round robin and frame based scheduler, that is, coupling delay performance and bandwidth allocation granularity. We show that despite its simplicity, CORR often outperforms some of the more sophisticated schemes, such as Packet-by-Packet Generalized Processor Sharing (PGPS) in terms of delay performance and fairness. Rate based service disciplines for packet switched network is a well studied area of research 1, 2, 4, 7, 11, 8]. Based on bandwidth sharing strategies, most of the proposed schemes can be classi ed into one of the two categories { (1) fair queuing mechanisms, and (2) frame-based or weighted round robin policies. Virtual clock 11], packet-by-packet generalized processor sharing (PGPS) 3, 7], self clocked fair queueing (SFQ) 6], are the most popular examples of schemes that use fair queueing strategies to guarantee a certain share of bandwidth to a speci c connection. The most popular frame-based schemes are Stop-and-Go (SG) 4, 5] and Hierarchical-Round-Robin (HRR) 2]. While fair queueing policies are extremely exible in terms of allocating bandwidth in very ne granularity and fair distribution of bandwidth among active connections, they are expensive in terms of implementation. Frame-based mechanisms on the other hand are inexpensive in terms of their implementation. However, they su er from many shortcomings, such as ine cient utilization of bandwidth, coupling between delay performance and bandwidth allocation granularity, unfair allocation of bandwidth. CORR strives to integrate the exibility and fairness of the fair queueing strategies with the simplicity of frame-based/round robin mechanisms. The starting point of our algorithm is a simple variation of round robin scheduling. Like round robin, CORR divides the time-line into allocation cycles, and each connection is allocated a fraction of the available bandwidth in each cycle. However, unlike slotted implementations of round robin schemes where bandwidth is allocated as a multiple of a xed quantum, in our scheme bandwidth allocation granularity can be arbitrarily small. This helps CORR to break the coupling between framing delay and granularity of bandwidth allocation. Another important di erence between CORR and frame based schemes, such as SG and HRR is that CORR is a work conserving service discipline. It does not waste the spare capacity of the system, rather share it fairly among active connections. A recent paper 10] proposed a similar idea for e cient implementation of fair queuing. However, the algorithm proposed in 10] has not been analyzed for delay and other related performance metrics. We have presented detailed analysis of CORR and derived tight bounds on end-to-end delay. Our derivation of delay bounds does not assume a speci c tra c arrival pattern. Hence, unlike PGPS (for which delay bound is available only for leaky bucket controlled sources) we can derive end-to-end delay bounds for CORR for a variety of tra c sources. Using tra c traces from real life video sources we have shown that CORR often performs better than PGPS in terms of the size of the admissible 1
region. We have also analyzed the fairness properties of CORR under the most general scenarios and have shown that it achieves nearly perfect fairness. The rest of this paper is organized as follows. In section 2 we present the intuition behind CORR and its algorithmic description. We discuss the properties of the algorithm in section 3. Section 4 is devoted to the analysis of the algorithm and its evaluation in terms delay performance and fairness. In section 5 we compare the end-to-end performance of CORR with PGPS and SG using a variety of tra c traces. We conclude the paper in section 6.
2 Scheduling Algorithm
Like round robin scheduling, CORR divides the time line into allocation cycles. The maximum length of an allocation cycle is T . Let us assume that the cell transmission time is the basic unit of time. Hence, the maximum number of cells (or slots) transmitted during one cycle is T . At the time of admission, each connection Ci is allocated a rate Ri expressed in cells per cycle. Unlike simple round robin schemes, where Ri s have to be integers, CORR allows Ri s to be real. Since Ri s can take real values, the granularity of bandwidth allocation can be arbitrarily small, irrespective of the length of the allocation cycle. The goal of the scheduling algorithm is to allocate each connection Ci close to Ri slots in each cycle and exactly Ri slots per cycle over a longer time frame. It also distributes the excess bandwidth among the active connections Ci s in the proportion of their respective Ris. The CORR scheduler (see gure 1) consists of three asynchronous events | Initialize, Enqueue, and Dispatch. The event Initialize is invoked when a new connection is admitted. If a connection is admissible 1, it simply adds the connection to the connection-list fC g. The connection-list is ordered in the decreasing order of Ri bRi c, that is, the fractional part of Ri. The event Enqueue is activated at the arrival of a packet. It puts the packet in the appropriate connection queue and updates the cell count of the connection. The most important event in the scheduler is Dispatch. The event Dispatch is invoked at the beginning of a busy period. Before explaining the task performed by Dispatch, let us introduce the variables and constants used in the algorithm and the basic intuition behind it. The scheduler maintains separate queues for each connection. For each connection Ci , ni keeps the count of the waiting cells, and ri holds the number of slots currently credited to it. Note that ris can be real as well as negative fractions. A negative value of ri signi es that the connection has been allocated more slots than it deserves. A positive value of ri re ects the current legitimate requirement of the connection. In order to allocate slots to meet the requirement of the connection as closely as possible, CORR divides each allocation cycle into two sub-cycles | a major cycle and a minor cycle. In the major cycle, integral requirement of each connection is satis ed rst. Slots left over from major cycle are allocated in minor cycle to connections with still unful lled fractional requirements. Obviously, a fraction of a slot cannot be allocated. Hence, eligible connections are allocated a full slot each in the minor cycle whenever slots are available. However, all the connections
1
We discuss admission control later.
2
Constants Variables
T : Cycle length. Ri : Slots allocated to Ci .
Events
t: Slots left in current cycle. ni : Number of cells in Ci . ri : Current slot allocation of Ci.
fC g: Set of all connections.
Initialize(Ci) /* Invoked at connection setup time. */ add Ci to fC g; /* fC g is ordered in decreasing order of Ri bRic. */ ni 0; ri 0; Enqueue() /* Invoked at cell arrival time. */ ni = ni + 1 add cell to connection queue; Dispatch() /* Invoked at the beginning of a busy period. */ 8Ci :: ri 0; while not end-of-busy-period do t T; 1. Major Cycle: for all Ci 2 fC g do /* From head to tail. */ ri min(ni ; ri + Ri); xi min(t; bri c); t t xi; ri ri xi; ni ni xi; dispatch xi cells from connection queue Ci;
2. Minor Cycle: for all Ci 2 fC g do /* From head to tail. */ xi min(t; dri e); t t xi; ri ri xi; ni ni xi; dispatch xi cells from connection queue Ci;
end for
end while
end for
Figure 1: Carry-Over Round Robin Scheduling. with fractional requirements may not be allocated a slot in the minor cycle. The connections that get a slot in the minor cycle over-satisfy their requirements and carry a debit to the next cycle. The eligible connections that do not get a slot in the minor cycle carry a credit to the next cycle. The 3
allocations for the next cycle are adjusted to re ect this debit and credit carried over from the last cycle. Following is a detailed description of the steps taken in the Dispatch event. At the beginning of a busy period, all ris are set to 0 and a new cycle is initiated. The cycles continue until the end of the busy period. At the beginning of each cycle, the current number of unallocated slots t is initialized to T , and the major cycle is initiated. In the major cycle, the dispatcher cycles through connection-list and, for each connection Ci , updates ri to ri + Ri . If the number of cells queued in the connection queue, ni , is less than the updated value of ri , ri is set to ni . This is to make sure that a connection cannot accumulate credits. The minimum of t and bric cells are dispatched from the connection queue of Ci. The variables are appropriately adjusted after dispatching the cells. A minor cycle starts with the slots left over from preceding major cycle. Again, the dispatcher walks through the connection-list. As long as there are slots left, a connection is deemed eligible for dispatching i 1) it has queued packets, and 2) its ri is greater than zero. If there is no eligible connection or if t reaches zero, the cycle ends. Note that the length of the major and minor cycles may be di erent in di erent allocation cycles. Example: Let us consider a CORR scheduler with cycle length T = 4 and serving three connections C1, C2 , and C3 with R1 = 2, R2 = 1:5, and R3 = 0:5, respectively. In an ideal system where fractional slots can be allocated, slots can be allocated to the connections in a fashion shown in gure 2, resulting in full utilization of the system. CORR also achieves full utilization, but with a di erent allocation of slots. For ease of exposition, let us assume that all three connections are backlogged starting from the beginning of the busy period. In the major cycle of the rst cycle, CORR allocates C1 , C2 , and C3 , bR1c = 2, bR2c = 1, and bR3c = 0 slots, respectively. Hence, at the beginning of the rst minor cycle, t = 1, r1 = 0:0, r2 = 0:5, and r3 = 0:5. The only slot left over for the minor cycle goes to C2. Consequently, at the end of the rst cycle, r1 = 0:0, r2 = 0:5, and r3 = 0:5, and the adjusted requirements for the second cycle are
r = r + R = 0:0 + 2:0 = 2:0
1 1 1
r = r + R = 0:5 + 1:5 = 1:0 r = r + R = 0:5 + 0:5 = 1:0
2 2 2 3 3 3
Since all the ris are integral, they are all satis ed in the major cycle. The main attraction of CORR is its simplicity. In terms of complexity, CORR is comparable to round robin and frame based mechanisms. However, CORR does not su er from the shortcomings of round robin and frame based schedulers. By allowing the number of slots allocated to a connection in an allocation cycle to be a real number instead of an integer, we break the coupling between the service delay and bandwidth allocation granularity. Also, unlike frame based mechanisms, such as SG and HRR, CORR is a work conserving discipline capable of exploiting the multiplexing gains of packet switching. In the following section we discuss some of its basic properties. 4
Cycle 1 Ideal
Cycle 2
R 1 = 2.0
r1 =2.0 r2=1.5
r1 =0.0 r2 =0.5
r1 =2.0 r2 =1.0
r1 =0.0 r2=0.0
R2 = 1.5
R3 = 0.5
r3 = 0.5
Major Cycle
r3 = 0.5
Minor Cycle
r =1.0 3
Major Cycle
r3 =0.0
Minor Cycle Connection 3
Connection 1
Connection 2
Figure 2: An Example Allocation.
3 Basic Properties
In this section, we discuss some of the basic properties of the scheduling algorithm. Lemma 3.1 de nes an upper bound on the aggregate requirements of all streams inherited from the last cycle. This result is used in lemma 3.2 to determine the upper and lower bounds on the individual requirements carried over from the last cycle by each connection.
Lemma 3.1 If P8C 2fCg Ri T then at the beginning of each cycle P8C 2fCg ri 0:
i i
period, and then we will show that if it hold in the kth cycle, it also holds in the (k + 1)th cycle. Base Case: From the allocation algorithm we observe that at the beginning of a busy period ri = 0 for all connection Ci . Hence, X ri = 0
8Ci2fC g
Proof: We will prove this by induction. We will rst show that it holds at the beginning of a busy
Thus, the assertion holds in the base case. Inductive Hypothesis: Assume that the premise holds in the kth cycle. We need to prove that it also holds in the (k + 1)th cycle. We use superscript for cycles in the following proof.
X
8Ci2fC g
rik =
+1
X
8Ci2fC g
rik +
X
8Ci2fC g
Ri T
0+T T
0:
5
This completes the proof. Henceforth we assume that the admission control mechanism makes sure that 8C 2fC g Ri T at all nodes. This simple admission control test is one of the attractions of the CORR scheduling.
i
P
Lemma 3.2 If P8C 2fCg Ri T then at the beginning of each cycle
i
1<
where
i
i
ri
i < 1;
= maxk fkRi bkRi cg; k = 1; 2; : : :
Proof: To derive the lower bound on ri, observe that in each cycle no more than drie slots are
i
allocated to connection Ci . Also, note that ri is incremented in steps of Ri. Hence, the lowest ri can get to is, = maxk fkRi dkRi eg; k = 1; 2; : : : 1 = maxk fkRi bkRi cg; k = 1; 2; : : : 1
Derivation of the upper bound is little more complex. Let us assume that there are n connections Ci, i = 1; 2; : : :; n. With no loss of generality we can renumber them, such that Ri Rj , when i < j . For the sake of simplicity, let us also assume that all the Ris are fractional. We show later that this assumption is not restrictive. To prove the upper bound we rst prove that ri never exceeds 1, for all connections Ci . Now, since Rn is the lowest of all Ri s, i = 1; 2; : : :; n, Cn is the last connection in the connection list. Consequently, Cn is the last connection considered for a possible cell dispatch in both major and minor cycles. Hence, if we can prove that rn never exceeds 1, so is true for all other ris. We will prove this by contradiction. Let us assume that Cn enters a busy period in allocation cycle 1. Observe, that Cn experiences the worst case allocation when all other connections also enter their busy period in the same cycle. Let us assume that rn exceeds 1. This would happen in the allocation cycle d1=Rne. Since rn exceeds 1, Cn is considered for a possible dispatch in the major cycle. Now, Cn is not scheduled during the major cycle of the allocation cycle d1=Rne if and only if the following is true at the beginning of the allocation cycle,
n 1 X i=1
P
bri + Ric T
Pn
From lemma 3.1 we know that, n i=1 ri 0 at the beginning of each cycle. Since rn > 0, at the beginning of the allocation cycle d1=Rne. But,
n 1 X i=1
i=1 ri < 0
1
bri + Ric
n 1 X i=1
(ri + Ri ) < 0 + 6
n 1 X i=1
Ri < T
This contradicts our original premise. Hence, rn cannot exceed 1. Noting that rn is incremented in steps of Rn the bound follows. We have proved the bounds under the assumption that all Ris are fractional. If we relax that assumption, the result still holds. This is due to the fact that the integral part of Ri is guaranteed to be allocated in each allocation cycle. Hence, even when Ris are not all fractional, we can reduce the problem to an equivalent one with fractional Ris using the transformation ^i = Ri bRi c and T ^=T R This completes the proof.
n X i=1
bRic:
4 Quality of Sevice Envelope
In this section we analyze the worst-case end-to-end delay performance of CORR. Other measures of performance such as delay jitter and bu er size at each node can also be found from the results derived in this section. In order to nd the end-to-end delay, we have rst derived delay bounds for a single node system. We then show that the end-to-end delay for a multi-node system can be reduced to delay encountered in an equivalent single node system. Hence, the delay bounds derived for single node system can be substituted to nd the end-to-end delay. We have also presented a comprehensive analysis of CORR's fairness. We de ne a fairness index to quantify how fairly bandwidth is allocated among active connections, and show that the fairness index of CORR is within a constant factor of any scheduling discipline.
4.1 Delay Analysis
In this section we derive the worst case delay bounds of a connection spanning single or multiple nodes, each employing CORR scheduling to multiplex tra c from di erent connections. We assume that each connection has an associated tra c envelope that describes the characteristics of the tra c it is carrying, and a minimum guaranteed rate of service at each multiplexing node. Our goal is to determine the maximum delay su ered by any cell belonging to the connection. We start with a simple system consisting of a single multiplexing node, and nd the worst case delay for di erent tra c envelopes.
Single-node Case
Let us consider a single server employing CORR scheduling to service tra c from di erent connections. Since we are interested in the worst case delay behavior, and each connection is guaranteed a minimum rate of service, we can consider each connection in isolation. Our problem then is to nd the maximum di erence between the arrival and the departure times of any cell, assuming that the 7
cells are serviced using CORR scheduling with a minimum guaranteed rate of service. The arrival time of a cell can be obtained from the tra c envelope de ned by the tra c envelope associated with a connection. Tra c envelope associated with a connection depends on the shaping mechanism (see Appendix) used at the network entry point. In this paper we have considered leaky bucket and moving window shapers. Following, we derive the worst case departure time a cell in terms of the service rate allocated to the connection and the length of the allocation cycle. Knowing both the arrival and the departure functions, we can compute the worst case delay bound. Before presenting the results let us rst formally introduce the de nition of a connection busy period and a system busy period.
Cell Index
Arrival Function
delay encountered by cell i
i
backlog at time t
Departure Function
t
Time
Figure 3: Computing delay and backlog from the arrival and departure functions.
De nition 4.1 A connection is said to be in the busy period if connection queue is non-empty. The
system is said to be in the busy period if at least one of the active connection is in the its busy period.
Note, that a particular connection can switch between busy and idle periods even when the system is in the same busy period. The following theorem determines the departure time of a speci c cell belonging to a particular connection.
Theorem 4.1 Assume that a connection enters a busy period at time 0. Let d(i) be the latest time
R
by which the ith cell, starting from the beginning of the current busy period, departs the system. Then d(i) can be expressed as, d(i) = i + 1 + T; i = 0; 1; : : :; 1: where R is the rate allocated to the connection and T is the maximum length of the allocation cycle.
Proof: Since a cell may leave the system any time during an allocation cycle, to capture the worst
case we assume that all the cells served during an allocation cycle leave at the end of the cycle. Now, 8
when a connection enters a busy period, in the worst case, r = . If cell i departs at the end of the allocation cycle L, the number of slots allocated by the scheduler is L R + and the number of slots consumed is i + 1 (since packet number starts from 0). In the worst case, 1>L R This implies that, (i + 1) 0:
i+1+ +1 > L i+1+ : R R From the above inequality and noting that L is an integer and d(i) = L T , we get 1 + T: d(i) = i + R
Theorem 4.1 precisely characterizes the departure function d( ) associated with a connection. As mentioned earlier, the arrival function a( ) associated with a connection is determined by the tra c envelope and has been characterized for di erent composite shapers in the Appendix. Knowing both a(i) and d(i), the arrival and departure time of the ith cell in a busy period, delay encountered by the ith cell can be computed as d(i) a(i) (see gure 3). Note that this is really the horizontal distance between the arrival and departure functions at i. Hence, the maximum delay encountered by any cell is really the maximum horizontal distance between the arrival and the departure functions. Similarly, the vertical distance between these functions represents the backlog in the system. Unfortunately, nding the maximum delay, that is the maximum horizontal di erence between the arrival and the departure functions, is a di cult task. Hence, instead of nding the maximum delay directly by measuring the horizontal distance between these functions, we rst determine the point at which the maximum backlog occurs and the index i of the cell which is at the end of the queue at that point. The worst case delay is then computed by evaluating d(i) a(i). Following we carry out this procedures for a(i) de ned by composite leaky bucket, and moving window shapers.
through a single multiplexing node employing CORR scheduling with an allocation cycle of length T 2 . If the connection is allocated a service rate of R, then the worst case delay encountered by any cell belonging to the connection is upper bounded by,
Lemma 4.1 Consider a connection shaped using an n-component moving window shaper and passing
DCORR=MW
8 > > > > < > > > > :
n mj + T X ml R ml 1 wl ; l j n ml 2mj + T w X j R ml 1 wl; l j
1 = +1 1 = +1
R+ wj (R=T mj =wj ) = 1 R+ wj (R=T mj =wj ) > 1
when
2
mj < R < mj ; wj T wj
+1 +1
j = 1; 2; : : :; n 1:
We assume that the cycle length is smaller than the smallest window period.
9
length of the busy period is nite. To prove that, it is su cient to show that there exists a positive integer k such that, the number of cells serviced in kwj time is more than equal to kmj . In other words, we have to show that there exists a k such that the following holds,
Proof: First we will show that under the conditions stated above the system is stable. That is, the
kwj kwj kwj k
d(kmj 1) (kmj 1) + 1 + T R (kmj 1) + 1 + + 1 T R R+ wj (R=T mj =wj )
Clearly, for there to exists a positive integer k so that the above equality is satis ed, the following condition needs to hold.
R=T mj =wj > 0 or R=T > mj =wj
By our assumption, R=T > mj =wj . Hence, the system is stable. Now, we need to determine the point at which the maximum backlog occurs. Depending on the value of k, the maximum backlog can occur at one of the two places. Case 1: k = 1. If k = 1, that is, when tra c coming in during a time window of length wj departs the system in the same window, the maximum backlog occurs at the arrival instant of the (mj 1)th cell 3. Clearly, the index of the cell at the end of the queue at that instant is (mj 1)th . Hence, the maximum delay encountered by any cell under this scenario is the same as the delay su ered by the (mj 1)th cell, and can be enumerated by computing d(mj 1) a(mj 1). We can evaluate a(mj 1) as following,
a(mj 1) =
= + =
3
n X l=1 j X l=1 n X l=j +1 n X l=j +1
mj 1 ml mj 1 ml mj 1 ml mj 1 ml
mj 1 ml w ml ml l mj 1 ml w ml ml l mj 1 ml w ml ml l mj 1 ml w ml ml l
1 1 1 1 1 1 1 1
(since ml 1 > ml )
Note that cells are numbered from 0. Since R can be non-integral, we can choose T arbitrarily small without a ecting the granularity of bandwidth allocation
10
=
n X l=j +1
ml ml
1
1 wl :
Therefore, the worst case delay is bounded by,
DCORR=MW
d(mj 1) a(mj 1) n mj + T X ml R ml l j
= +1
1
1 wl :
Case 2: k > 1. When k is greater than 1, the connection busy period continues beyond the rst window of length wj . Since R=T > mj =wj , the rate of tra c arrival is lower than the rate of departure. Still, in this case, not all cells that arrive during the rst window of length wj are served during that period and the left over cells are carried over into the next window. This is due to the fact that unlike the arrival curve, the departure function does not start at time 0 but at time d(1+ )=Re. This is the case when k = 1 also. However, in that case, the rate of service is high enough to serve all the cells before the end of the rst window. When k > 1 the backlog carried over from the rst window is cleared in portions over the next k 1 windows. Clearly, the backlogs carried over into subsequent windows diminish in size and is cleared completely by the end of the kth window. Hence, second window is the one where the backlog inherited from the last window is the maximum. Consequently, absolute backlog in the system reaches its maximum at the arrival of the 2mj 1 cell. Hence, the maximum delay encountered by any cell under this scenario is the same as the delay su ered by the (2mj 1)th cell, and can be enumerated by computing d(2mj 1) a(2mj 1). We can evaluate a(2mj 1) as following,
a(2mj 1) =
ml ml ml wl l j X 2mj 1 ml w 2mj 1 = ml ml ml l l 2mj 1 mj w j 1 + 2m j mj mj mj n X 2mj 1 2mj 1 ml w + ml ml ml l l j n X 2mj 1 2mj 1 ml = 0 + wj + m m ml l l l j n X ml = wj + ml 1 wl : l j
1 =1 1 1 1 =1 1 1 1 1 = +1 1 = +1 1 1 = +1
n X
2mj 1
2mj 1 ml
1
wl
(since ml
1
2ml )
Therefore the worst case delay is bounded by,
DCORR=MW
d(2mj 1) a(2mj 1)
11
2mj +
R
T wj
n X l=j +1
ml ml
1
1 wl :
Lemma 4.2 Consider a connection shaped by an n-component leaky bucket shaper and passing
through a single multiplexing node employing CORR scheduling with an allocation cycle of maximum length T . If the connection is allocated a service rate of R, then the worst case delay su ered by any cell belonging to the connection is upper bounded by, Bj + 1 + T (B b + 1) t ; CORR=LB Dmax j j j when
Proof: In order to identify the point where maximum the backlog occurs, observe that the rate
of arrivals is more than the rate of service until the slope of the tra c envelope changes from t 1 +1 to t1 . This change in the slope occurs at the arrival of the Bj th cell in the worst case. Hence, the maximum delay encountered by any cell is at most as large as the delay su ered by Bj th cell. We can compute a(Bj ) as following,
j j
R 1
Scheduling is the process of deciding how to commit resources between a variety of possible tasks. Time can be specified (scheduling a flight to leave at 8:00) or floating as part of a sequence of events
Carry-Over Round Robin: A Simple Cell Scheduling Mechanism for ATM Networks
Debanjan Saha
y
Sarit Mukherjee
z
Satish K. Tripathi
x
We propose a simple cell scheduling mechanism for ATM networks. The proposed mechanism, named Carry-Over Round Robin (CORR), is an extension of weighted round robin scheduling. We show that albeit its simplicity, CORR achieves tight bounds on end-to-end delay and near perfect fairness. Using a variety of video tra c traces we show that CORR often outperforms some of the more complex scheduling disciplines such as Packet-by-Packet Generalized Processor Sharing (PGPS).
Abstract
This work is supported in part by NSF under Grant No. CCR-9318933 and Army Research Laboratory under Cooperative Agreement No. DAAL01-96-2-0002. A short version of the paper appeared in the proceedings of IEEE Infocom'96. y IBM T.J. Watson Research Center, Yorktown Heights, NY 10598. Email:[email protected]. z Dept. of Computer Science & Engg. University of Nebraska, Lincoln, NE 68588. Email:[email protected]. x Dept. of Computer Science, University of Maryland, College Park, MD 20742. Email:[email protected].
1 Introduction
This paper presents a simple yet e ective cell multiplexing mechanism for ATM networks. The proposed mechanism, named Carry-Over Round Robin (CORR), is a simple extension of weighted round robin scheduling. It provides each connection a minimum guaranteed rate of service at the time of connection setup. The excess capacity is fairly shared among active connections. CORR overcomes a common shortcoming of most round robin and frame based scheduler, that is, coupling delay performance and bandwidth allocation granularity. We show that despite its simplicity, CORR often outperforms some of the more sophisticated schemes, such as Packet-by-Packet Generalized Processor Sharing (PGPS) in terms of delay performance and fairness. Rate based service disciplines for packet switched network is a well studied area of research 1, 2, 4, 7, 11, 8]. Based on bandwidth sharing strategies, most of the proposed schemes can be classi ed into one of the two categories { (1) fair queuing mechanisms, and (2) frame-based or weighted round robin policies. Virtual clock 11], packet-by-packet generalized processor sharing (PGPS) 3, 7], self clocked fair queueing (SFQ) 6], are the most popular examples of schemes that use fair queueing strategies to guarantee a certain share of bandwidth to a speci c connection. The most popular frame-based schemes are Stop-and-Go (SG) 4, 5] and Hierarchical-Round-Robin (HRR) 2]. While fair queueing policies are extremely exible in terms of allocating bandwidth in very ne granularity and fair distribution of bandwidth among active connections, they are expensive in terms of implementation. Frame-based mechanisms on the other hand are inexpensive in terms of their implementation. However, they su er from many shortcomings, such as ine cient utilization of bandwidth, coupling between delay performance and bandwidth allocation granularity, unfair allocation of bandwidth. CORR strives to integrate the exibility and fairness of the fair queueing strategies with the simplicity of frame-based/round robin mechanisms. The starting point of our algorithm is a simple variation of round robin scheduling. Like round robin, CORR divides the time-line into allocation cycles, and each connection is allocated a fraction of the available bandwidth in each cycle. However, unlike slotted implementations of round robin schemes where bandwidth is allocated as a multiple of a xed quantum, in our scheme bandwidth allocation granularity can be arbitrarily small. This helps CORR to break the coupling between framing delay and granularity of bandwidth allocation. Another important di erence between CORR and frame based schemes, such as SG and HRR is that CORR is a work conserving service discipline. It does not waste the spare capacity of the system, rather share it fairly among active connections. A recent paper 10] proposed a similar idea for e cient implementation of fair queuing. However, the algorithm proposed in 10] has not been analyzed for delay and other related performance metrics. We have presented detailed analysis of CORR and derived tight bounds on end-to-end delay. Our derivation of delay bounds does not assume a speci c tra c arrival pattern. Hence, unlike PGPS (for which delay bound is available only for leaky bucket controlled sources) we can derive end-to-end delay bounds for CORR for a variety of tra c sources. Using tra c traces from real life video sources we have shown that CORR often performs better than PGPS in terms of the size of the admissible 1
region. We have also analyzed the fairness properties of CORR under the most general scenarios and have shown that it achieves nearly perfect fairness. The rest of this paper is organized as follows. In section 2 we present the intuition behind CORR and its algorithmic description. We discuss the properties of the algorithm in section 3. Section 4 is devoted to the analysis of the algorithm and its evaluation in terms delay performance and fairness. In section 5 we compare the end-to-end performance of CORR with PGPS and SG using a variety of tra c traces. We conclude the paper in section 6.
2 Scheduling Algorithm
Like round robin scheduling, CORR divides the time line into allocation cycles. The maximum length of an allocation cycle is T . Let us assume that the cell transmission time is the basic unit of time. Hence, the maximum number of cells (or slots) transmitted during one cycle is T . At the time of admission, each connection Ci is allocated a rate Ri expressed in cells per cycle. Unlike simple round robin schemes, where Ri s have to be integers, CORR allows Ri s to be real. Since Ri s can take real values, the granularity of bandwidth allocation can be arbitrarily small, irrespective of the length of the allocation cycle. The goal of the scheduling algorithm is to allocate each connection Ci close to Ri slots in each cycle and exactly Ri slots per cycle over a longer time frame. It also distributes the excess bandwidth among the active connections Ci s in the proportion of their respective Ris. The CORR scheduler (see gure 1) consists of three asynchronous events | Initialize, Enqueue, and Dispatch. The event Initialize is invoked when a new connection is admitted. If a connection is admissible 1, it simply adds the connection to the connection-list fC g. The connection-list is ordered in the decreasing order of Ri bRi c, that is, the fractional part of Ri. The event Enqueue is activated at the arrival of a packet. It puts the packet in the appropriate connection queue and updates the cell count of the connection. The most important event in the scheduler is Dispatch. The event Dispatch is invoked at the beginning of a busy period. Before explaining the task performed by Dispatch, let us introduce the variables and constants used in the algorithm and the basic intuition behind it. The scheduler maintains separate queues for each connection. For each connection Ci , ni keeps the count of the waiting cells, and ri holds the number of slots currently credited to it. Note that ris can be real as well as negative fractions. A negative value of ri signi es that the connection has been allocated more slots than it deserves. A positive value of ri re ects the current legitimate requirement of the connection. In order to allocate slots to meet the requirement of the connection as closely as possible, CORR divides each allocation cycle into two sub-cycles | a major cycle and a minor cycle. In the major cycle, integral requirement of each connection is satis ed rst. Slots left over from major cycle are allocated in minor cycle to connections with still unful lled fractional requirements. Obviously, a fraction of a slot cannot be allocated. Hence, eligible connections are allocated a full slot each in the minor cycle whenever slots are available. However, all the connections
1
We discuss admission control later.
2
Constants Variables
T : Cycle length. Ri : Slots allocated to Ci .
Events
t: Slots left in current cycle. ni : Number of cells in Ci . ri : Current slot allocation of Ci.
fC g: Set of all connections.
Initialize(Ci) /* Invoked at connection setup time. */ add Ci to fC g; /* fC g is ordered in decreasing order of Ri bRic. */ ni 0; ri 0; Enqueue() /* Invoked at cell arrival time. */ ni = ni + 1 add cell to connection queue; Dispatch() /* Invoked at the beginning of a busy period. */ 8Ci :: ri 0; while not end-of-busy-period do t T; 1. Major Cycle: for all Ci 2 fC g do /* From head to tail. */ ri min(ni ; ri + Ri); xi min(t; bri c); t t xi; ri ri xi; ni ni xi; dispatch xi cells from connection queue Ci;
2. Minor Cycle: for all Ci 2 fC g do /* From head to tail. */ xi min(t; dri e); t t xi; ri ri xi; ni ni xi; dispatch xi cells from connection queue Ci;
end for
end while
end for
Figure 1: Carry-Over Round Robin Scheduling. with fractional requirements may not be allocated a slot in the minor cycle. The connections that get a slot in the minor cycle over-satisfy their requirements and carry a debit to the next cycle. The eligible connections that do not get a slot in the minor cycle carry a credit to the next cycle. The 3
allocations for the next cycle are adjusted to re ect this debit and credit carried over from the last cycle. Following is a detailed description of the steps taken in the Dispatch event. At the beginning of a busy period, all ris are set to 0 and a new cycle is initiated. The cycles continue until the end of the busy period. At the beginning of each cycle, the current number of unallocated slots t is initialized to T , and the major cycle is initiated. In the major cycle, the dispatcher cycles through connection-list and, for each connection Ci , updates ri to ri + Ri . If the number of cells queued in the connection queue, ni , is less than the updated value of ri , ri is set to ni . This is to make sure that a connection cannot accumulate credits. The minimum of t and bric cells are dispatched from the connection queue of Ci. The variables are appropriately adjusted after dispatching the cells. A minor cycle starts with the slots left over from preceding major cycle. Again, the dispatcher walks through the connection-list. As long as there are slots left, a connection is deemed eligible for dispatching i 1) it has queued packets, and 2) its ri is greater than zero. If there is no eligible connection or if t reaches zero, the cycle ends. Note that the length of the major and minor cycles may be di erent in di erent allocation cycles. Example: Let us consider a CORR scheduler with cycle length T = 4 and serving three connections C1, C2 , and C3 with R1 = 2, R2 = 1:5, and R3 = 0:5, respectively. In an ideal system where fractional slots can be allocated, slots can be allocated to the connections in a fashion shown in gure 2, resulting in full utilization of the system. CORR also achieves full utilization, but with a di erent allocation of slots. For ease of exposition, let us assume that all three connections are backlogged starting from the beginning of the busy period. In the major cycle of the rst cycle, CORR allocates C1 , C2 , and C3 , bR1c = 2, bR2c = 1, and bR3c = 0 slots, respectively. Hence, at the beginning of the rst minor cycle, t = 1, r1 = 0:0, r2 = 0:5, and r3 = 0:5. The only slot left over for the minor cycle goes to C2. Consequently, at the end of the rst cycle, r1 = 0:0, r2 = 0:5, and r3 = 0:5, and the adjusted requirements for the second cycle are
r = r + R = 0:0 + 2:0 = 2:0
1 1 1
r = r + R = 0:5 + 1:5 = 1:0 r = r + R = 0:5 + 0:5 = 1:0
2 2 2 3 3 3
Since all the ris are integral, they are all satis ed in the major cycle. The main attraction of CORR is its simplicity. In terms of complexity, CORR is comparable to round robin and frame based mechanisms. However, CORR does not su er from the shortcomings of round robin and frame based schedulers. By allowing the number of slots allocated to a connection in an allocation cycle to be a real number instead of an integer, we break the coupling between the service delay and bandwidth allocation granularity. Also, unlike frame based mechanisms, such as SG and HRR, CORR is a work conserving discipline capable of exploiting the multiplexing gains of packet switching. In the following section we discuss some of its basic properties. 4
Cycle 1 Ideal
Cycle 2
R 1 = 2.0
r1 =2.0 r2=1.5
r1 =0.0 r2 =0.5
r1 =2.0 r2 =1.0
r1 =0.0 r2=0.0
R2 = 1.5
R3 = 0.5
r3 = 0.5
Major Cycle
r3 = 0.5
Minor Cycle
r =1.0 3
Major Cycle
r3 =0.0
Minor Cycle Connection 3
Connection 1
Connection 2
Figure 2: An Example Allocation.
3 Basic Properties
In this section, we discuss some of the basic properties of the scheduling algorithm. Lemma 3.1 de nes an upper bound on the aggregate requirements of all streams inherited from the last cycle. This result is used in lemma 3.2 to determine the upper and lower bounds on the individual requirements carried over from the last cycle by each connection.
Lemma 3.1 If P8C 2fCg Ri T then at the beginning of each cycle P8C 2fCg ri 0:
i i
period, and then we will show that if it hold in the kth cycle, it also holds in the (k + 1)th cycle. Base Case: From the allocation algorithm we observe that at the beginning of a busy period ri = 0 for all connection Ci . Hence, X ri = 0
8Ci2fC g
Proof: We will prove this by induction. We will rst show that it holds at the beginning of a busy
Thus, the assertion holds in the base case. Inductive Hypothesis: Assume that the premise holds in the kth cycle. We need to prove that it also holds in the (k + 1)th cycle. We use superscript for cycles in the following proof.
X
8Ci2fC g
rik =
+1
X
8Ci2fC g
rik +
X
8Ci2fC g
Ri T
0+T T
0:
5
This completes the proof. Henceforth we assume that the admission control mechanism makes sure that 8C 2fC g Ri T at all nodes. This simple admission control test is one of the attractions of the CORR scheduling.
i
P
Lemma 3.2 If P8C 2fCg Ri T then at the beginning of each cycle
i
1<
where
i
i
ri
i < 1;
= maxk fkRi bkRi cg; k = 1; 2; : : :
Proof: To derive the lower bound on ri, observe that in each cycle no more than drie slots are
i
allocated to connection Ci . Also, note that ri is incremented in steps of Ri. Hence, the lowest ri can get to is, = maxk fkRi dkRi eg; k = 1; 2; : : : 1 = maxk fkRi bkRi cg; k = 1; 2; : : : 1
Derivation of the upper bound is little more complex. Let us assume that there are n connections Ci, i = 1; 2; : : :; n. With no loss of generality we can renumber them, such that Ri Rj , when i < j . For the sake of simplicity, let us also assume that all the Ris are fractional. We show later that this assumption is not restrictive. To prove the upper bound we rst prove that ri never exceeds 1, for all connections Ci . Now, since Rn is the lowest of all Ri s, i = 1; 2; : : :; n, Cn is the last connection in the connection list. Consequently, Cn is the last connection considered for a possible cell dispatch in both major and minor cycles. Hence, if we can prove that rn never exceeds 1, so is true for all other ris. We will prove this by contradiction. Let us assume that Cn enters a busy period in allocation cycle 1. Observe, that Cn experiences the worst case allocation when all other connections also enter their busy period in the same cycle. Let us assume that rn exceeds 1. This would happen in the allocation cycle d1=Rne. Since rn exceeds 1, Cn is considered for a possible dispatch in the major cycle. Now, Cn is not scheduled during the major cycle of the allocation cycle d1=Rne if and only if the following is true at the beginning of the allocation cycle,
n 1 X i=1
P
bri + Ric T
Pn
From lemma 3.1 we know that, n i=1 ri 0 at the beginning of each cycle. Since rn > 0, at the beginning of the allocation cycle d1=Rne. But,
n 1 X i=1
i=1 ri < 0
1
bri + Ric
n 1 X i=1
(ri + Ri ) < 0 + 6
n 1 X i=1
Ri < T
This contradicts our original premise. Hence, rn cannot exceed 1. Noting that rn is incremented in steps of Rn the bound follows. We have proved the bounds under the assumption that all Ris are fractional. If we relax that assumption, the result still holds. This is due to the fact that the integral part of Ri is guaranteed to be allocated in each allocation cycle. Hence, even when Ris are not all fractional, we can reduce the problem to an equivalent one with fractional Ris using the transformation ^i = Ri bRi c and T ^=T R This completes the proof.
n X i=1
bRic:
4 Quality of Sevice Envelope
In this section we analyze the worst-case end-to-end delay performance of CORR. Other measures of performance such as delay jitter and bu er size at each node can also be found from the results derived in this section. In order to nd the end-to-end delay, we have rst derived delay bounds for a single node system. We then show that the end-to-end delay for a multi-node system can be reduced to delay encountered in an equivalent single node system. Hence, the delay bounds derived for single node system can be substituted to nd the end-to-end delay. We have also presented a comprehensive analysis of CORR's fairness. We de ne a fairness index to quantify how fairly bandwidth is allocated among active connections, and show that the fairness index of CORR is within a constant factor of any scheduling discipline.
4.1 Delay Analysis
In this section we derive the worst case delay bounds of a connection spanning single or multiple nodes, each employing CORR scheduling to multiplex tra c from di erent connections. We assume that each connection has an associated tra c envelope that describes the characteristics of the tra c it is carrying, and a minimum guaranteed rate of service at each multiplexing node. Our goal is to determine the maximum delay su ered by any cell belonging to the connection. We start with a simple system consisting of a single multiplexing node, and nd the worst case delay for di erent tra c envelopes.
Single-node Case
Let us consider a single server employing CORR scheduling to service tra c from di erent connections. Since we are interested in the worst case delay behavior, and each connection is guaranteed a minimum rate of service, we can consider each connection in isolation. Our problem then is to nd the maximum di erence between the arrival and the departure times of any cell, assuming that the 7
cells are serviced using CORR scheduling with a minimum guaranteed rate of service. The arrival time of a cell can be obtained from the tra c envelope de ned by the tra c envelope associated with a connection. Tra c envelope associated with a connection depends on the shaping mechanism (see Appendix) used at the network entry point. In this paper we have considered leaky bucket and moving window shapers. Following, we derive the worst case departure time a cell in terms of the service rate allocated to the connection and the length of the allocation cycle. Knowing both the arrival and the departure functions, we can compute the worst case delay bound. Before presenting the results let us rst formally introduce the de nition of a connection busy period and a system busy period.
Cell Index
Arrival Function
delay encountered by cell i
i
backlog at time t
Departure Function
t
Time
Figure 3: Computing delay and backlog from the arrival and departure functions.
De nition 4.1 A connection is said to be in the busy period if connection queue is non-empty. The
system is said to be in the busy period if at least one of the active connection is in the its busy period.
Note, that a particular connection can switch between busy and idle periods even when the system is in the same busy period. The following theorem determines the departure time of a speci c cell belonging to a particular connection.
Theorem 4.1 Assume that a connection enters a busy period at time 0. Let d(i) be the latest time
R
by which the ith cell, starting from the beginning of the current busy period, departs the system. Then d(i) can be expressed as, d(i) = i + 1 + T; i = 0; 1; : : :; 1: where R is the rate allocated to the connection and T is the maximum length of the allocation cycle.
Proof: Since a cell may leave the system any time during an allocation cycle, to capture the worst
case we assume that all the cells served during an allocation cycle leave at the end of the cycle. Now, 8
when a connection enters a busy period, in the worst case, r = . If cell i departs at the end of the allocation cycle L, the number of slots allocated by the scheduler is L R + and the number of slots consumed is i + 1 (since packet number starts from 0). In the worst case, 1>L R This implies that, (i + 1) 0:
i+1+ +1 > L i+1+ : R R From the above inequality and noting that L is an integer and d(i) = L T , we get 1 + T: d(i) = i + R
Theorem 4.1 precisely characterizes the departure function d( ) associated with a connection. As mentioned earlier, the arrival function a( ) associated with a connection is determined by the tra c envelope and has been characterized for di erent composite shapers in the Appendix. Knowing both a(i) and d(i), the arrival and departure time of the ith cell in a busy period, delay encountered by the ith cell can be computed as d(i) a(i) (see gure 3). Note that this is really the horizontal distance between the arrival and departure functions at i. Hence, the maximum delay encountered by any cell is really the maximum horizontal distance between the arrival and the departure functions. Similarly, the vertical distance between these functions represents the backlog in the system. Unfortunately, nding the maximum delay, that is the maximum horizontal di erence between the arrival and the departure functions, is a di cult task. Hence, instead of nding the maximum delay directly by measuring the horizontal distance between these functions, we rst determine the point at which the maximum backlog occurs and the index i of the cell which is at the end of the queue at that point. The worst case delay is then computed by evaluating d(i) a(i). Following we carry out this procedures for a(i) de ned by composite leaky bucket, and moving window shapers.
through a single multiplexing node employing CORR scheduling with an allocation cycle of length T 2 . If the connection is allocated a service rate of R, then the worst case delay encountered by any cell belonging to the connection is upper bounded by,
Lemma 4.1 Consider a connection shaped using an n-component moving window shaper and passing
DCORR=MW
8 > > > > < > > > > :
n mj + T X ml R ml 1 wl ; l j n ml 2mj + T w X j R ml 1 wl; l j
1 = +1 1 = +1
R+ wj (R=T mj =wj ) = 1 R+ wj (R=T mj =wj ) > 1
when
2
mj < R < mj ; wj T wj
+1 +1
j = 1; 2; : : :; n 1:
We assume that the cycle length is smaller than the smallest window period.
9
length of the busy period is nite. To prove that, it is su cient to show that there exists a positive integer k such that, the number of cells serviced in kwj time is more than equal to kmj . In other words, we have to show that there exists a k such that the following holds,
Proof: First we will show that under the conditions stated above the system is stable. That is, the
kwj kwj kwj k
d(kmj 1) (kmj 1) + 1 + T R (kmj 1) + 1 + + 1 T R R+ wj (R=T mj =wj )
Clearly, for there to exists a positive integer k so that the above equality is satis ed, the following condition needs to hold.
R=T mj =wj > 0 or R=T > mj =wj
By our assumption, R=T > mj =wj . Hence, the system is stable. Now, we need to determine the point at which the maximum backlog occurs. Depending on the value of k, the maximum backlog can occur at one of the two places. Case 1: k = 1. If k = 1, that is, when tra c coming in during a time window of length wj departs the system in the same window, the maximum backlog occurs at the arrival instant of the (mj 1)th cell 3. Clearly, the index of the cell at the end of the queue at that instant is (mj 1)th . Hence, the maximum delay encountered by any cell under this scenario is the same as the delay su ered by the (mj 1)th cell, and can be enumerated by computing d(mj 1) a(mj 1). We can evaluate a(mj 1) as following,
a(mj 1) =
= + =
3
n X l=1 j X l=1 n X l=j +1 n X l=j +1
mj 1 ml mj 1 ml mj 1 ml mj 1 ml
mj 1 ml w ml ml l mj 1 ml w ml ml l mj 1 ml w ml ml l mj 1 ml w ml ml l
1 1 1 1 1 1 1 1
(since ml 1 > ml )
Note that cells are numbered from 0. Since R can be non-integral, we can choose T arbitrarily small without a ecting the granularity of bandwidth allocation
10
=
n X l=j +1
ml ml
1
1 wl :
Therefore, the worst case delay is bounded by,
DCORR=MW
d(mj 1) a(mj 1) n mj + T X ml R ml l j
= +1
1
1 wl :
Case 2: k > 1. When k is greater than 1, the connection busy period continues beyond the rst window of length wj . Since R=T > mj =wj , the rate of tra c arrival is lower than the rate of departure. Still, in this case, not all cells that arrive during the rst window of length wj are served during that period and the left over cells are carried over into the next window. This is due to the fact that unlike the arrival curve, the departure function does not start at time 0 but at time d(1+ )=Re. This is the case when k = 1 also. However, in that case, the rate of service is high enough to serve all the cells before the end of the rst window. When k > 1 the backlog carried over from the rst window is cleared in portions over the next k 1 windows. Clearly, the backlogs carried over into subsequent windows diminish in size and is cleared completely by the end of the kth window. Hence, second window is the one where the backlog inherited from the last window is the maximum. Consequently, absolute backlog in the system reaches its maximum at the arrival of the 2mj 1 cell. Hence, the maximum delay encountered by any cell under this scenario is the same as the delay su ered by the (2mj 1)th cell, and can be enumerated by computing d(2mj 1) a(2mj 1). We can evaluate a(2mj 1) as following,
a(2mj 1) =
ml ml ml wl l j X 2mj 1 ml w 2mj 1 = ml ml ml l l 2mj 1 mj w j 1 + 2m j mj mj mj n X 2mj 1 2mj 1 ml w + ml ml ml l l j n X 2mj 1 2mj 1 ml = 0 + wj + m m ml l l l j n X ml = wj + ml 1 wl : l j
1 =1 1 1 1 =1 1 1 1 1 = +1 1 = +1 1 1 = +1
n X
2mj 1
2mj 1 ml
1
wl
(since ml
1
2ml )
Therefore the worst case delay is bounded by,
DCORR=MW
d(2mj 1) a(2mj 1)
11
2mj +
R
T wj
n X l=j +1
ml ml
1
1 wl :
Lemma 4.2 Consider a connection shaped by an n-component leaky bucket shaper and passing
through a single multiplexing node employing CORR scheduling with an allocation cycle of maximum length T . If the connection is allocated a service rate of R, then the worst case delay su ered by any cell belonging to the connection is upper bounded by, Bj + 1 + T (B b + 1) t ; CORR=LB Dmax j j j when
Proof: In order to identify the point where maximum the backlog occurs, observe that the rate
of arrivals is more than the rate of service until the slope of the tra c envelope changes from t 1 +1 to t1 . This change in the slope occurs at the arrival of the Bj th cell in the worst case. Hence, the maximum delay encountered by any cell is at most as large as the delay su ered by Bj th cell. We can compute a(Bj ) as following,
j j
R 1