Minimizing end-to-end delay in high-speed networks with a simple coordinated schedule.
We study the problem of providing end-to-end delay guarantees in connection-oriented networks. In this environment, multiple-hop sessions coexist and interfere with one another.Parekh and Gallager showed that the Weighted Fair Queueing (WFQ) scheduling discipline provides a worst-case delay guarantee comparable to (1/i)  Ki for a session with rate i and Ki hops. Such delays can occur since a session-i packet can wait for time 1/i at every hop.We describe a randomized work-conserving scheme that guarantees, with high probability, an additive delay bound of approximately 1/i + Ki. This bound is smaller than the multiplicative bound (1/i)  Ki of WFQ, especially when the hop count Ki is large. We call our scheme COORDINATED-EARLIEST-DEADLINE-FIRST (CEDF) since it uses an earliest-deadline-first approach in which simple coordination is applied to the deadlines for consecutive hops of a session. The key to the bound is that once a packet has passed through its first server, it can pass through all its subsequent servers quickly.We conduct simulations to compare the delays actually produced by the two scheduling disciplines. In many cases, these actual delays are comparable to their analytical worst-case bounds, implying that CEDF outperforms WFQ.
INTRODUCTION
The provision of end-to-end delay guarantees in high-speed
networks remains one of the most important and widely studied
Quality-of-Service (QoS) issues. Many real time audio and
video applications rely on the ability of the network to provide
small delays. One key mechanism for achieving this aim
is scheduling at the outputs of the switches. In this paper, we
attempt to minimize end-to-end delay using a novel scheduling
scheme.
Before we introduce our scheme we first recall the delay
bounds for the much studied Weighted Fair Queueing (WFQ)
scheduling discipline, also known as Packet-by-Packet Generalized
Processor-Sharing (PGPS). In their seminal papers [1], [2],
Parekh and Gallager showed that WFQ achieves the following
session-i delay bound for Rate Proportional Processor Sharing
(RPPS). 1
(1)
For session i, L i is the maximum packet size, K i is the number
of servers and r m is the service rate of the mth server. The maximum
packet size over all sessions is Lmax . Session i is leaky-bucket
constrained with burst size oe i and rate ae i . Throughout
this paper, we assume that all service is non-cut-through and
non-preemptive.
We briefly review the definitions of WFQ and RPPS in Section II.
To understand the delay guarantee of (1) better, we compare
the delay bound when session i has a single hop (K
the bound when session i has multiple hops (K i ? 1). We observe
the following. When the burst size oe i is large then the
multiple-hop delay bound is much less than K i times the single-hop
delay bound. However, when oe i is small then the multiple-hop
delay can be approximately K i times the single-hop delay.
To see this, let us assume a uniform packet size for all sessions
a uniform service rate for all servers (r
The delay bound of (1) now becomes,
Hence, for a small burst size, e.g. oe the multiple-hop delay
is essentiallyae i
\Theta K i
and the single-hop delay is essentially 1
. Moreover, it is possible
to construct an example in which this bound is achieved
since a packet can wait for time 1
at every hop. This illustrates
our earlier observation.
In this paper, we demonstrate with both analysis and simulation
that even for small burst sizes, a bound of 1
\Theta K i is not
necessary, i.e. the K-hop delay does not have to be K times the
1-hop delay. Indeed, in the case of uniform packet sizes, uniform
service rates and small burst sizes, [3] showed that each
session i can achieve a delay bound, 2
O
using a centralized scheme. The same paper also proposed a
simple distributed protocol with a slightly weaker bound,
O
ae min
Here, n is the number of servers in the network and ae min is the
minimum session rate.
Our Results In Section III we generalize the above simple protocol
to accommodate arbitrary packet sizes and arbitrary server
2 The bound O
\Delta is best possible up to a constant factor. To see
this, under non-cut-through service all sessions must suffer delay K i . Moreover,
examples can be constructed in which some sessions must suffer delay ae i .
Delay
Session Length
Multiplicative Delay Bound
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 1. A plot of the multiplicative delay bound 1
\Theta K i . Each curve
represents a different value of ae i
. The delays are plotted against
Delay
Session Length
Additive Delay Bound
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 2. A plot of the additive delay bound 1
rates. We derive the following exact delay bound which allows
us to provide a direct comparison with (1).
The parameter " is the server utilization factor defined later. The
logarithmic term, although small, is somewhat involved. We
give the full definition later. In Section IV we provide simulation
results to compare the actual performance of our protocol and
WFQ.
The basic ideas of our protocol are an earliest-deadline-first
approach coupled with randomization and coordination. We assign
a deadline for every server through which a packet passes.
By introducing some randomness, the deadlines can be sufficiently
"spread out" so that all the packets can meet all their
deadlines. By introducing simple coordination among the dead-
lines, we can ensure that once a packet has passed through
its first server, it can pass through all its subsequent servers
quickly. We refer to our protocol as COORDINATED-EARLIEST-
DEADLINE-FIRST (CEDF).
The traffic lights in Manhattan provide an intuitive analogue
to CEDF. Since the lights are coordinated, when one traffic light
turns green, many lights further down the street turn green also.
This means that once a car waits through one red light it can
then drive through many green lights quickly. In this way, delay
does not have to accumulate at every light.
From now on, we refer to a delay bound of the form 1
\Theta K i
as a multiplicative bound and a bound of the form 1
an additive bound. In Figures 1 and 2, we plot these bounds for
different values of K i and ae i . The curves for the multiplicative
bound have different slopes for different ae i , whereas the curves
for the additive bound all have the same slope. We can see that
in general it is desirable to have an additive bound. We note that
the bound (2) of CEDF is close to an additive bound. (It does not
contain a term K i =ae i .) Apart from the bound in reference [3] we
know of no previous end-to-end delay bound that is close to an
additive bound.
In our simulations, we observe that the actual delays under
WFQ and CEDF are often comparable to their analytical
bounds. In many scenarios, the former exhibits the behavior of
a multiplicative bound, and the latter exhibits the behavior of
an additive bound. For these scenarios, CEDF produces significantly
lower delays. In other scenarios where there is less contention
between sessions, both protocols exhibit the behavior of
an additive bound.
CEDF has other desirable properties. First, we do not need
traffic reshaping between hops. Second, we only need to do
per-session processing at the points where the sessions enter the
network. That is, we do no per-session processing within the
network.
Previous Work The Earliest-Deadline-First (EDF) scheduling
discipline when applied to a single server has received much at-
tention. For example, Ferrari and Verma [4] and Verma, Zhang
and Ferrari [5] showed that it can provide delay bounds and
delay-jitter bounds. Georgiadis, Gu-erin and Parekh [6] and
Liebeherr, Wrege and Ferrari [7] proved that EDF is delay-optimal
in the sense that if a set of delay bounds is achievable
then it can be achieved by EDF. Necessary and sufficient conditions
for a set of delay bounds to be achievable were given.
Liebeherr et al. also presented schemes with low implementation
complexity that approximate EDF [7], [8]. For networks,
Georgiadis, Gu-erin, Peris and Sivarajan [9] showed that EDF
can be sub-optimal. Nevertheless they proved that if the traffic
is correctly reshaped after each node then EDF can outperform
Weighted Fair Queueing. However, the best explicit bound on
end-to-end delay given in [9] is the same as Equation (1). General
techniques for calculating end-to-end delay bounds were
obtained by Goyal, Lam and Vin [10] and Goyal and Vin [11].
A number of papers have simulated end-to-end delay per-
formance. Simulation results for EDF are presented in [4],
[5]. Clark, Shenker and Zhang [12] used simulation to compare
WFQ with variants of FIFO. Yates, Kurose, Towsley and
Hluchyj [13] examined end-to-end delay distributions for WFQ,
FIFO and Golestani's Stop-and-Go Fair Queueing [14], [15].
They found that the analytic delay bounds can be too pes-
simistic. Grossglauser and Keshav [16] showed that FIFO
can outperform the Weighted Round Robin (WRR) and Round
Robin (RR) disciplines for CBR traffic.
Our protocol CEDF is motivated by techniques of Leighton,
Maggs and Rao [17] and Leighton, Maggs and Richa [18] for
static packet scheduling. In this static setting, all packets are
present in the network initially. Similar techniques were used
by Rabani and Tardos [19] and Ostrovsky and Rabani [20]. For
an overview of different scheduling disciplines, see [21], [22].
The rest of the paper is divided into sections as follows. We
define our model and briefly review WFQ and RPPS in Section
II. Our protocol CEDF is described and analyzed in Section
III. The simulation results are presented in Section IV. We
give our conclusions in Section V. The Appendix provides the
details of the proofs.
II. MODEL AND DEFINITIONS
We consider a packet-based connection-oriented network. We
equate each link in the network with the server that schedules the
sessions on the link. Each session is specified by a fixed path
through the network. Let K i be the number of servers along the
path of session i, and let m (i)
be these servers.
When it causes no confusion, we drop the superscript (i). We
define L i to be the maximum size of a session-i packet in bits.
We use the (oe; ae) traffic model introduced by Cruz [23], [24]
in which the traffic entering the network is leaky-bucket con-
strained. The session-i traffic is characterized by a burst size
oe i and a session rate ae i . If A i denotes the amount of
session-i traffic entering the network during the time interval
r m be the service rate of server m, i.e. m can service at
most r m bits during the interval
the set of sessions served by server m. We require the following
stability condition,
The parameter " is a server utilization factor. It is crucial in
allowing us to use coordination to achieve low delay bounds.
We adopt the non-cut-through and non-preemptive convention
for scheduling. First, no packet is eligible for service until
its last bit has arrived. Second, once a server begins serving a
packet, it must continue until the whole packet has been serviced

Review of Weighted Fair Queueing Since we refer frequently to
Weighted Fair Queueing, we now provide a brief definition. For
details see [25], [1], [2]. WFQ attempts to emulate the Generalized
Processor Sharing (GPS) scheme, in which all backlogged
sessions receive service simultaneously. In particular, if session
i is backlogged at server m then under GPS it receives service
at rate,
where Bm is the set of backlogged sessions at server m and the
are a set of allocated weights.
WFQ is a non-preemptive scheme that emulates GPS on a
packet-by-packet basis. In particular, if a server needs to select
a packet for transmission at time t then it selects the first packet
that would complete service under GPS if no additional packets
were to arrive after time t.
In this paper we restrict our attention to a special case of WFQ
known as Rate Proportional Processor Sharing (RPPS) in which
sessions i and servers m. The end-to-end delay
bound for RPPS derived in [2] is stated in Equation (1).
III. ANALYTICAL BOUND
A.

Overview

The basic idea of COORDINATED-EDF is very simple. For
each packet p, we assign deadlines
server, passes. The deadlines
at a server m are defined using a parameter Gm , where Gm is
essentially Lmax
log(\Delta). (We define the logarithmic term in Gm
later.) In particular, D 1 is rand +Gm1 time after p's injection,
where rand is a random number chosen from an appropriate
range. Each subsequent deadline D k+1 is
gives priority to the packet with the earliest deadline if more
than one packet is waiting for a server. Ties are broken arbitrarily

Note that randomness is only added to the first deadline
of each packet. This randomness has the important effect of
"spreading out" the deadlines. If rand is chosen from a large
enough range, i.e. proportional to L i =ae i for session i, then deadlines
from different sessions do not cluster together. In this way,
packets do not compete for the same server simultaneously, and
hence all packets are able to meet all their deadlines.
The Gm 's provide coordination among the deadlines. We
point out that the values of the Gm 's are usually small, especially
in high-speed networks where the server rates r m are
large. This means that once a packet passes through its first
server, it passes through all its subsequent servers quickly. As
an analogy to our strategy, consider the traffic lights on an avenue
in Manhattan. If a car is stopped at a red light then once
that light turns green, many of the subsequent lights turn green
also. In other words, the coordination of the lights means that
once the car has passed through one light, it can quickly travel
through many lights in succession.
We emphasize that the Gm 's are independent of the session
rates. Under CEDF, session-i packets do not accumulate a delay
of 1
for each server that they pass through. Hence, CEDF does
not have a multiplicative term of the form 1
\Theta K i in its delay
bound. This provides a significant contrast with the delay bound
of WFQ. We discuss in more detail the advantages of CEDF in
Section III-B.
B. Protocol and Analysis
Parameters We define parameters T i and M for generating
random numbers. Roughly speaking, M serves as the "period"
of the deadlines. Once the deadlines are defined in an interval
of length M , all deadlines are defined. The parameter T i is the
size of the intervals from which the random numbers for session
are chosen. When T i is about 2L i
, the amount of randomness
is sufficient to "spread out" the deadlines. We choose to write T i
in the following (slightly complicated) form, because it ensures
that M is an integral multiple of all the T i 's. For reasons that
will become clear later, we also define S i such that S i =T i is
slightly greater than the session rate ae i . Let,
We define Gm for each server m, which determines how the
deadline for a packet is incremented when it advances from one
server to the next. Let,
. The parameter
is the success probability
of the protocol. (We discuss this success probability in the Remarks
section.) Note that ff is independent of L i , oe i , ae i , K i and
r m .
Tokens We use tokens to define deadlines. For session i, let
chosen uniformly at random from
each of the intervals [0; T i
tokens appear periodically with period M at the following times.
be the servers on the path of
session i. For each session-i packet, we define a sequence of
deadlines traversing the servers.
When a packet of size ' bits obtains a token, it consumes '
bits from that token. At most S i bits can be consumed from
each session-i token. Suppose a session-i packet p is injected at
time t inj and has ' p bits. Suppose also that the session-i packet
injected immediately before p obtains its token at time t prev .
Packet p obtains the first session-i token after maxft inj ; t prev g
that has at least ' p bits unconsumed. Let - be the time that the
token appears. The deadlines are defined as follows.
Now that all deadlines are defined, each server gives priority
to the packet that has the earliest deadline.
Remarks
1. The only coordination required comes from the above iterative
definition of the deadlines. This coordination can be
achieved simply by stamping each packet with its current dead-
line. 3 Each server can then update the deadlines of its pending
3 This can be done using techniques similar to the protocols of [26].
packets autonomously, i.e. we do not require explicit communication
among servers.
2. We do not place tokens at times T rather
we introduce some randomness. This randomness is essential
for spacing out the deadlines so that not many deadlines contend
for the same server simultaneously. Once the tokens are chosen,
the deadlines are chosen deterministically.
3. We emphasize that our protocol is work conserving and requires
no traffic shaping. As long as some packets are waiting
for a server, the packet with the earliest deadline gets serviced.
In particular, a packet can be serviced before it obtains a to-
ken. The concept of a "packet obtaining/consuming a token" is
merely a method of counting for the purpose of assigning deadlines

4. The only per-session processing is the determination of
which token a packet obtains. This can be done at the point
on the edge of the network where the session enters. Once the
token has been obtained, the deadlines for the packet are independent
of its session parameters. This means that we need no
per-session state within the network.
5. We say that the protocol is successful if all the packets meet
all their deadlines. The success of the protocol is equivalent to
the successful placing of a finite number of tokens due to the periodicity
of the token placement. Hence, we can use a Chernoff-
bound argument to analyze the success probability.
6. To prove the desired end-to-end delay bound, we prove two
statements in the Appendix. First, with high probability the protocol
is successful. (See Lemmas 2 and 3.) Second, - is at most
for each session-i packet, where t inj is the injection
time of that packet. (See Lemma 4.) Therefore,
Theorem 1: With high probability, the end-to-end delay guarantee
for session i is
r mk log e
We emphasize that when the protocol is successful, every packet
meets all of its deadlines, i.e. the bound in Theorem 1 is a worst-case
delay bound.
7. The factor 1=" in the term 4L i =" is needed in the proof of
Lemma 4. However, we conjecture that in many situations it
will be possible to obtain a delay bound in which the term 4L i ="
is replaced by 4L i .
8. We now compare the bound of WFQ with the bound of
CEDF when r m is large, e.g. in high-speed networks. Here,
the terms containing 1=r m are negligible. The bound for WFQ
becomes,
and the bound for CEDF becomes,
We note that the bound for CEDF does not contain K i .
IV. SIMULATION RESULTS
Our experiments simulate a simple situation with uniform
packet sizes and uniform server rates. Since CEDF involves
Mean
Delay
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 3. Mean delay of the long session due to WFQ.1030507090110130150
Mean
Delay
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 4. Mean delay of the long session due to S-CEDF.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 5. 98%-percentile delay of the long session due to WFQ.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 6. 98%-percentile delay of the long session due to S-CEDF.
many parameters, we simulate a simplified version, SIMPLE-
CEDF, which nevertheless contains the essence of CEDF. Under
S-CEDF, the deadline for the first server is chosen randomly
(without reference to periodic tokens). Every subsequent deadline
is the deadline for the previous server incremented by one
packet service time. (See Figure 11.) As we shall see, the performance
of S-CEDF corresponds to the analytical bounds of
Section III.
ffl p: A session-i packet
Injection time of p
of p at its kth hop
randomly chosen from [t
3 Each link gives priority to the packet with the
earliest deadline.
Fig. 11. S-CEDF, the SIMPLE-CEDF protocol.
We compare the performance of WFQ and SIMPLE-CEDF
(S-CEDF) using the mean end-to-end delay and the 98%-
percentile end-to-end delay. We use the following simulation
parameters. The link speed is set to 1Mb/sec and all packets
have a size 1000 bits. The packet service time on each link is
therefore 1ms. The end-to-end delay consists of the packet service
time and the queueing time, i.e. the time that the packet
spends waiting in a buffer. Buffers have a large size and no
packet is dropped in any experiments.
packet size link speed packet service time buffer size
1000b 1Mb/sec 1ms 1
A. Single Long Session
We begin with a very simple configuration as illustrated in

Figure

12. The network consists of a line of N links. A long
session of N hops travels through the network sharing each hop
with a short session of 1 hop. These short sessions provide the
"cross-traffic" for the long session. The length N of the long
session varies from 5 to 40. The link utilization is set to 0:8
0:2). The rate of the long session ae ' varies in the
range from 0:03 to 0:7. The rate of each short session ae s is set
to 0:8 \Gamma ae ' . Experiments of a similar setup were conducted in
other simulation studies, e.g. [16], [27], [5].1245
Fig. 12. Session 0 is the long session with 5 hops. Sessions 1 through 5 are the
1-hop sessions.
We first use a deterministic injection model that conforms
to the (oe; ae) traffic model with each session. Figures
4, 5 and 6 illustrate the end-to-end delay experienced by
the long session. We note the striking resemblance between the
curves for these actual delays and the curves for the analytical
y
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 7. Probabilistic on-off source. Mean delay due to WFQ.1030507090110130150
Mean
Delay
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 8. Probabilistic on-off source. Mean delay due to S-CEDF.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 9. Probabilistic on-off source. 98%-percentile delay due to WFQ.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
rate=0.3
rate=0.4
rate=0.6
rate=0.7
Fig. 10. Probabilistic on-off source. 98%-percentile delay due to S-
CEDF.
delay bounds. (Recall Figures 1 and 2.) These plots demonstrate
that for small values of ae ' , S-CEDF has a significant advantage
over WFQ in terms of the end-to-end delay of the long session.
The two disciplines present similar behavior for larger values of
ae ' .
We take a closer look at the behavior of the long session for
small ae ' . Under WFQ, packets from the long session are frequently
delayed by packets from the 1-hop sessions, since ae s is
much larger than ae ' . Furthermore, a packet from the long session
suffers from a similar amount of queueing delay at each
link. This behavior of WFQ supports the analytical bound of the
multiplicative form 1
ae '
\Theta K.
Under S-CEDF, the long session behaves differently. When
traversing the first few links, a packet from the long session is
likely to queue in the buffers. This is because the initial deadline
is chosen from the range [t
ae '
than ae s , the long session is likely to have later deadlines than
the interfering 1-hop sessions at the beginning of its path, and
hence its packets are delayed. However, as the packet from the
long session moves further along its path, its deadline becomes
earlier in comparison to the deadlines of the 1-hop sessions, and
hence it suffers less delay. This behavior of S-CEDF supports
the analytical bound of the additive form 1
ae '
+K.
Despite the fact that the long sessions with small ae ' have
much smaller end-to-end delay under S-CEDF than under WFQ,
the 1-hop sessions do not suffer a great deal under S-CEDF. The
following table summarizes the mean delay of the 1-hop sessions

ae s 0.77 0.7 0.6 0.5 0.4 0.3 0.2 0.1
S-CEDF 1.06 1.16 1.26 1.3 1.42 1.53 1.79 2.15
Variations of the above experiments are conducted. We first
vary the configuration of the network and the sessions. For ex-
ample, instead of having one 1-hop session at each link, we use
multiple 1-hop sessions at each link where the total rates of these
1-hop sessions add up to 0:8 \Gamma ae ' . As another example, we experiment
with a ring of 40 nodes and 40 links. Multiple long
sessions wrap around the ring interfering with one another in
addition to the 1-hop sessions on each link. These experiments
yield similar results to those shown in Figures 3-6. (We omit the
plots here.)
We also vary the injection patterns at the source for the single
long session configuration shown in Figure 12. Experiments
with a larger burst size, e.g. plots similar to

Figures

3-6. A probabilistic on-off source with exponentially
distributed on and off times yields the plots in Figures 7-10.
We have results for similar experiments using the FIFO dis-
cipline. In this setting, the delays produced by FIFO are close
to the delays of WFQ, i.e. the delays can be approximated by a
multiplicative formula. (We omit the plots here.)
y
Length of network
rate=0.03
rate=0.1
rate=0.15
Fig. 13. Multiple long sessions. Mean delay due to
Mean
Delay
Length of network
rate=0.03
rate=0.1
rate=0.15
Fig. 14. Multiple long sessions. Mean delay due to
98th
Percentile
Length of Network
rate=0.03
rate=0.1
rate=0.15
Fig. 15. Multiple long sessions. 98%-percentile delay due to
98th
Percentile
Length of Network
rate=0.03
rate=0.1
rate=0.15
Fig. 16. Multiple long sessions. 98%-percentile delay due to S-CEDF.
B. Multiple Long Sessions
We now consider a more complicated configuration. We use
a ring of 40 nodes, where neighboring nodes are connected by
links. Sessions with hops 1, 5, 10, 15, 20, 25, 30,
coexist and interfere with one another in this network. The paths
and rates of these sessions are chosen as follows. We first choose
a set of 40-hop paths. Each path begins with a random node and
then follows the ring. Each hop of the path between two neighboring
nodes can follow any of the 8 links between these nodes.
The choice is made randomly subject to the constraint that the
number of paths going through each link is the same. We now
cut some of these 40-hop paths into shorter paths. Some 40-hop
paths are divided into a 5-hop path and a 35-hop path, others
are divided into a 10-hop path and 30-hop path, etc. After this
process, the network has paths with lengths 5, 10, 15, ., 40. We
also have some 1-hop paths. All sessions have the same rate. By
varying the number of the original 40-hop paths, we achieve the
desired session rates. Figures 13-16 summarize the performance
of WFQ and S-CEDF. As we can see, the curves for WFQ have
the multiplicative characteristic, although it is less pronounced
than in Figures 3 and 5. The curves for S-CEDF have the additive
characteristic. We also observe that long sessions perform
better under S-CEDF than under WFQ, whereas short sessions
perform marginally better under WFQ.
We finally note that the analytical bound for WFQ is a worst-case
bound, and therefore can be overly conservative. In our
experiments, we have encountered situations in which WFQ behaves
in a similar manner to S-CEDF, i.e. the additive form ofae +K is more apparent. In one such experiment, we consider a
line of 41 nodes and 80 links, where neighboring nodes are connected
by double links. All sessions have 40 hops, starting from
the node on the left end and finishing at the node on the right
end. Each hop along the path of a session can follow either the
upper or the lower link. The choice is made randomly, subject
to the constraint that each link has an equal number of sessions
passing through it. All sessions have the same injection rate.
We vary the number of sessions in order to achieve the desired
session rate. Figures 17 and 19 illustrate the end-to-end delays
due to WFQ averaging over all the 40-hop sessions. These delays
have little multiplicative behavior. This is because in this
network there is little contention among packets. S-CEDF produces
similar end-to-end delays.
V. CONCLUSION
We have described a work-conserving scheduling discipline
COORDINATED-EARLIEST-DEADLINE-FIRST with end-to-end
delay bound,
r mk log(\Delta):
CEDF uses randomization and simple coordination to ensure
that once a packet passes through its first server it can pass
through all its subsequent servers quickly. Under CEDF, a
session-i packet does not accumulate a delay of L i K i
over K i
hops, and therefore its delay bound is smaller than that of the
y
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
Fig. 17. Double-link network. Mean delay due to WFQ.1030507090110130150
Mean
Delay
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
Fig. 18. Double-link network. Mean delay due to S-CEDF.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
Fig. 19. Double-link network. 98%-percentile delay due to WFQ.1030507090110130150
98th
Percentile
Session Length
rate=0.03
rate=0.1
rate=0.15
rate=0.2
Fig. 20. Double-link network. 98%-percentile delay due to S-CEDF.
Weighted Fair Queueing discipline. We have also presented simulation
results to show that the performance of CEDF and WFQ
can be comparable to the analytical bounds.
The major open problem is to reduce the delay bound still fur-
ther. The ultimate goal is a simple protocol with a delay bound,

ACKNOWLEDGMENTS

We thank Antonio Fern-andez, Mor Harchol-Balter and Tom
Leighton for their help in earlier stages of this work. Antonio
Fern-andez also provided many detailed comments on a preliminary
draft of this paper. We thank Jorg Liebeherr for his insight
on implementation issues.



--R

A generalized processor sharing approach to flow control in integrated services networks: The single-node case
A generalized processor sharing approach to flow control in integrated services networks: The multiple-node case
Dynamic packet routing with per-packet delay guarantees of O(distance
A scheme for real-time channel establishment in wide-area networks
Guaranteeing delay jitter bounds in packet switching networks.
Optimal multiplexing on a single link: delay and buffer requirements.
Exact admission control for networks with a bounded delay service.

Efficient network QoS provisioning based on per node traffic shaping.
Determining end-to-end delay bounds in heterogeneous networks
Generalized guaranteed rate scheduling algorithms: A framework.
Supporting real-time applications in an integrated services packet network: Architecture and mechanism

A framing strategy for congestion management.

On CBR service.
Packet routing and job-shop scheduling in O(congestion
Fast algorithms for finding O(congestion
Distributed packet switching in arbitrary net- works
switching algorithm.
An engineering approach to computer networking.
Service disciplines for guaranteed performance service in packet-switching networks
A calculus for network delay
A calculus for network delay
Analysis and simulation of a fair queueing algorithm.
The Tenet real-time protocol suite: Design
Traffic scheduling in packet-switched networks: analysis design and implementation
--TR
Supporting real-time applications in an Integrated Services Packet Network
A generalized processor sharing approach to flow control in integrated services networks
On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements
A generalized processor sharing approach to flow control in integrated services networks
The Tenet real-time protocol suite
Distributed packet switching in arbitrary networks
Exact admission control for networks with a bounded delay service
Universal <italic>O</italic>(congestion local control packet switching algorithms
An engineering approach to computer networking
Determining End-to-End Delay Bounds in Heterogeneous Networks
General dynamic routing with per-packet delay guarantees of O(distance+1/session rate)
A Near-Optimal Packet Scheduler for QoS Networks
Generalized Guaranteed Rate Scheduling Algorithms: A Framework
Traffic scheduling in packet-switched networks
packet routing;earliest deadline first;scheduling;weighted fair queueing;delay bounds