Jitter control in QoS networks.
We study jitter control in networks with guaranteed quality of service (QoS) from the competitive analysis point of view: we propose on-line algorithms that control jitter and compare their performance to the best possible (by an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of different packets, we show that a simple on-line algorithm using a buffer of B slots guarantees the same delay jitter as the best off-line algorithm using buffer space B/2. We prove that the guarantees made by our on-line algorithm hold, even for simple distributed implementations, where the total buffer space is distributed along the path of the connection, provided that the input stream satisfies a certain simple property. For rate jitter, where the goal is to minimize the difference between inter-arrival times, we develop an on-line algorithm using a buffer of size 2B + h for any h  1, and compare its jitter to the jitter of an optimal off-line algorithm using buffer size B. We prove that our algorithm guarantees that the difference is bounded by a term proportional to B/h.
Introduction
The need for networks with guaranteed quality of service (QoS) is widely recognized today
(see, e.g., [8, 11]). Unlike today's ``best effort'' networks such as the Internet, where the user
has no guarantee on the performance it may expect from the network, QoS networks guarantee
the end-user application a certain level of performance. For example, ATM networks
support guaranteed QoS in various parameters, including end-to-end delay and delay jitter
(called Cell Transfer Delay and Cell Delay Variation, respectively [5, 12]).
Jitter measures the variability of delay of packets in the given stream, which is an important
property for many applications (for example, streaming real-time applications). Ideally,
packets should be delivered in a perfectly periodic fashion; however, even if the source generates
an evenly spaced stream, unavoidable jitter is introduced by the network due to the
variable queuing and propagation delays, and packets arrive at the destination with a wide
range of inter-arrival times. The jitter increases at switches along the path of a connection
due to many factors, such as conflicts with other packets wishing to use the same links, and
non-deterministic propagation delay in the data-link layer.
Jitter is quantified in two ways. One measure, called delay jitter, bounds the maximum
difference in the total delay of different packets (assuming, without loss of generality, that the
abstract source is perfectly periodic). This approach is useful in contexts such as interactive
communication (e.g., voice and video tele-conferencing), where a guarantee on the delay
jitter can be translated to the maximum buffer size needed at the destination. The second
measure, called rate jitter, bounds the difference in packet delivery rates at various times.
More precisely, rate jitter measures the difference between the minimal and maximal inter-arrival
times (inter-arrival time between packets is the reciprocal of rate). Rate jitter is a
useful measure for many real-time applications, such as a video broadcast over the net: a
slight deviation of rate translates to only a small deterioration in the perceived quality.
Another important reason for keeping the jitter under control comes from the network
management itself, even if there are no applications requiring jitter guarantees. For example,
it is well known that traffic bursts tend to build in the network [8, 15]. Jitter control provides
a means for regulating the traffic inside the network so that the behavior of internal traffic
is more easily manageable. A more subtle argument in favor of jitter control (given by [17])
proceeds as follows. When a QoS network admits a connection, a type of "contract" is agreed
upon between the network and the user application: the user is committed to keeping its
traffic within certain bounds (such as peak bandwidth, maximal burst size etc.), and the
network is committed to providing certain service guarantees (such as maximal delay, loss
rate etc. Since the network itself consists of a collection of links and switches, its guarantees
must depend on the guarantees made by its components. The guarantees made by a link or a
switch, in turn, are contingent on some bounds on the locally incoming traffic. As mentioned
above, unless some action is taken by the network, the characteristics of the connection may
in fact get worse for switches further down the path, and thus they can only commit to lower
QoS. Jitter control can be useful in allowing the network to ensure that the traffic incoming
into a switch is "nicer," and get better guarantees from the switch.
Jitter control implementation is usually modeled as follows [17, 8]. Traffic incoming into
the switch is input into a jitter-regulator, which re-shapes the traffic by holding packets in an
internal buffer. When a packet is released from the jitter-regulator, it is passed to the link
scheduler, which schedules packet transmission on the output link. In this work we focus on
studying jitter-regulators.
Nature of our results. Before we state concrete results, we would like to explain the
insight we seek. Prior to our work, performance of jitter control algorithm was measured
either by worst-case behavior, or under statistical assumptions. Thus the properties of the
algorithms were either deterministic (given deterministic worst-case assumptions on the input
stream), or probabilistic (given stochastic assumptions on the input stream). In this work,
we prove relativistic guarantees: we compare the performance of the algorithm in question to
the performance of the best possible algorithm, which we treat as an adversary we compete
against. The adversary algorithm is not assumed to be constrained by the on-line nature
of the problem: it is assumed to produce the best possible output for the given input, even
if the best output may be computable only in hindsight (hence the adversary algorithm is
sometimes called the off-line algorithm). Algorithms whose performance can be bounded
with respect to the performance of an off-line adversary are called competitive [10, 7, 1]. We
argue that proving that an algorithm is competitive is meaningful, and sometimes superior,
to proving deterministic or stochastic guarantees: first, deterministic or stochastic guarantees
say nothing about the case where the underlying assumptions do not hold for some reason
(even worse, the underlying assumptions-in particular, tractable stochastic assumptions-
are notoriously hard to justify). On the other hand, a competitive algorithm does not
assume anything about the input, and therefore its guarantees are more robust in this sense.
Secondly, worst-case guarantees usually do not say much about individual cases: for example,
an algorithm may be called deterministically optimal even if it performs always as bad as
the worst case; competitive algorithms, by contrast, are guaranteed to do relatively well on
each and every instance. Thirdly, if we add an assumption about the input sequence, the
relativistic guarantee would immediately translate to a specific deterministic guarantee.
We remark that unlike conventional competitive analysis, in most cases we shall compare
the performance of our on-line algorithms to the performance of an (optimal, off-line) adversary
which is restricted to use less buffer space. For example, we prove statements such
as "an algorithm Z using space B produces jitter which never more than the jitter produced
by an optimal algorithm, for the given arrival sequence, using space B=2." One possible
interpretation for this result is that algorithm Z always uses at least half of its buffer space
optimally-as if it knew the future in advance.
Our Results. We consider both delay- and rate-jitter. For delay-jitter, we give a very
simple on-line algorithm, and prove that the delay-jitter in its output is no more than the
delay-jitter produced by an optimal (off-line) algorithm using half the space. We give a
lower bound on delay-jitter showing that doubling the space is necessary. We also consider
a distributed implementation of our algorithm, where the total space of 2B is distributed
along a path. We prove that the distributed algorithm guarantees the same delay-jitter of a
centralized, off-line algorithm using space B, provided that an additional condition on the
beginning of the sequence is met. To complete the picture, we also describe an efficient
optimal off-line algorithm. For all our delay-jitter algorithms, we assume that the average
inter-arrival time of the input stream (denoted X a ) is given ahead of time.
One way to view the relativistic gurantee of our algorithm is the following. Assume that
the specific arrival sequence is such that using a buffer of size B one can reduce the jitter
comletely (i.e. zero jitter). In such a case, our online algorithm, using space 2B would also
output a completely periodic sequence (i.e. zero jitter).
For rate jitter, we assume that the on-line algorithm receives, in addition to X a , two
parameters denoted I max and I min , which are a lower and an upper bound on the desired
time between consecutive packets in the output stream. The on-line algorithm we present
uses a buffer of size 2B + h where h  1 is a parameter, and B is such that an off-line
algorithm using buffer space B can release the packets with inter-departure times in the
interval [I min ; I max ] (but the optimal jitter may be much lower). The algorithm guarantees
that the rate-jitter of the released sequence is at most the best off-line jitter plus an additive
term of 2(B We also show how can the algorithm adapt to unknown
X a . Finally, we prove that on-line algorithms using less than 2B buffer space are doomed to
have trivial rate-jitter guarantees with respect to an off-line algorithm using space B.
Related Work. QoS has been the subject of extensive research in the current decade,
starting with the seminal work of Ferrari [2] (see [16] for a comprehensive survey). A number
of algorithms has been proposed for jitter control. Partridge [9] proposed to time-stamp each
message at the source, and fully reconstruct the stream at the destination based on a bound
on the maximal end-to-end delay. Verma et al. [13] proposed the jitter-EDD algorithm, where
a jitter controller at a switch computes for each packet its eligibility time, before which the
packet is not submitted for to the link scheduler. The idea is to set the eligibility time to
the difference between maximum delay for the previous link and the actual delay for the
packet: this way the traffic is completely reconstructed at each jitter node. Note that jitter-
EDD requires nodes to have synchronized clocks. The Leave-in-Time algorithm [3] replaces
the synchronized clocks requirement of jitter-EDD with virtual clocks [19]. Golestani [4]
proposed the Stop-and-Go algorithm, which can be described as follows. Time is divided to
frames; all packets arriving in one frame are released in the following frame. This allows for
high flexibility in re-shaping the traffic. Hierarchical Round-Robin (HRR), proposed in [6],
guarantees that in each time frame, each connection has some predetermined slots in which
it can send packets. A comparative study of rate-control algorithms can be found in [18]. A
new jitter control algorithm was proposed in [14].
Paper Organization. In Section 2 we give the basic definitions and notations. In Section
3 we study delay jitter for a single switch. In Section 4 we extend the results of Section 3 to
a distributed implementation. In section 5 we study rate jitter.
Model
jitter-control
algorithm
packet arrival sequence
FIFO buffer
packet release sequence

Figure

1: Abstract node model. The jitter control algorithm controls packet release from the
buffer, based on the arrival sequence.
We consider the following abstract communication model for a node in the network (see
Fig. 1). We are given a sequence of packets denoted 0; arrives
at time arrival(k). Packets are assumed to have equal size. Each packet is stored in the buffer
upon arrival, and is released some time (perhaps immediately) after its arrival. Packets are
released in FIFO order. The time of packet release (also called packet departure or packet
send) is governed by a jitter control algorithm. Given an algorithm A and an arrival time
sequence, we denote by send A (k) the time in which packet k is released by A.
We consider jitter control algorithms which use bounded-size buffer space. We shall
assume that each buffer slot is capable of storing exactly one packet. All packets must be
delivered, and hence the buffer size limitation can be formalized as follows. The release
time sequence generated by algorithm A using a buffer of size B must satisfy the following
condition for all 0  k  n:
where we define The lower bound expresses the fact that a packet
cannot be sent before it arrives, and the upper bound states that when packet k +B arrives,
packet k must be released due to the FIFOness and the limited size of the buffer. We call
a sequence of departure times B-feasible for a given sequence of arrival times if it satisfies
Eq. (1), i.e., it can be attained by an algorithm using buffer space B. An algorithm is called
on-line if its action at time t is a function of the packet arrivals and releases which occur
before or at t; an algorithm is called off-line if its action may depend on future events too.
A times sequence is a non-decreasing sequence of real numbers. We now turn to define
properties of times sequences, which are our main interest in this paper. Given a times
sequence
i=0 , we define its average, minimum, and maximum inter-arrival times as
follows.
ffl The average inter-arrival time of oe is X oe
n .
ffl The minimum inter-arrival time of oe is X oe
ng.
ffl The maximum inter-arrival time of oe is X oe
ng.
We shall omit the oe superscript when the context is clear. The average rate of oe is simply
1=X oe
a .
We shall talk about the jitter of oe. We distinguish between two different kinds of jitter.
The delay jitter, intuitively, measures how far off is the difference of delivery times of different
1 Note that our definition allows for 0-length intervals where more than B packets are in the system. This
formal difficulty can be overcome by assuming explicitly that each event (packet arrival or release) occurs in
a different time point. For clarity of exposition, we prefer this simplified model, although our results hold in
both models.
packets from the ideal time difference in a perfectly periodic sequence, where packets are
spaced exactly X a time units apart. Formally, given a times sequence
i=0 , we define
the delay jitter of oe to be
0i;kn
We shall also be concerned with the rate jitter of oe, which can be described intuitively as the
maximal difference between inter-arrival times, which is equivalent to the difference between
rates at different times. Formally, we define the rate jitter of oe to be
0i;j!n
The following simple property shows the relationship between delay and rate jitter.
Lemma 2.1 Let oe be a times sequence.
(1) The delay jitter of oe equals 0 if and only if the rate jitter of oe equals 0.
(2) If the delay jitter of oe is J, then the rate jitter of oe is at most 2J.
(3) For all ffl ? 0, and M , there exists a sequence oe ffl;M with rate jitter at most ffl and
delay jitter at least M .
Proof: Suppose that
i=0 .
1. The delay jitter of oe is 0 iff for all 0  i  n we have t a , which is true iff
the rate jitter of oe is 0.
2. If the delay jitter of oe is J , then for all 0
and by the triangle inequality we have that the rate jitter of oe is at
most 2J .
3. Let ffl Choose an even number n ?
i=0 be
defined inductively as follows. For
Clearly, the resulting oe is a times sequence
with average inter-arrival rate X a and rate jitter at most ffl 0  ffl. However, we have
that hence the delay jitter is at least nffl 0? M by choice of
n.
Our means for analyzing the performance of jitter control algorithms is competitive analysis
[1]. In our context, we shall measure the (delay or rate) jitter of the sequence produced
by an on-line algorithm against the best jitter attainable for that sequence. As expected,
finding the release times which minimize jitter may require knowledge of the complete arrival
sequence in advance, i.e., it can be computed only by an off-line algorithm. Our results are
expressed in terms of the performance of our on-line algorithms using buffer space B on as
compared to the best jitter attainable by an off-line algorithm using space B off , where usually
. We are interested in two parameters of the algorithms: the jitter (guaranteed
by our on-line algorithms as a function of the best possible off-line guarantee) and the buffer
size (used by the on-line algorithm, as a function of the buffer size used by an optimal off-line
algorithm).
3 Delay-Jitter Control
In this section we analyze the best achievable delay-jitter. We first present an efficient off-line
algorithm which attains the best possible delay jitter using a given buffer with space B.
We then proceed to the main result of this section, which is an on-line delay-jitter control
algorithm which attains the best jitter guarantee that can be attained by any (off-line)
algorithm which uses half the buffer space. Finally, we present a lower bound which shows
that any on-line algorithm whose jitter guarantees are a function of the jitter guarantees of
an off-line algorithm, must have at least twice the space used by the off-line algorithm.
3.1 Off-line Delay-Jitter Control
We start with the off-line case. Suppose we are given the complete sequence farrival(k)g n
of packet arrival times. We wish to find a sequence of release times fsend off (k)g n
k=0 which
minimizes the delay jitter, using no more than B buffer space. The off-line algorithm is
defined as follows.
Algorithm A: off-line delay-jitter control.
1. For each 0  k  n, define the interval
where we define
2. Find a minimal interval M which intersects all intervals E k .
3. For each packet k, let
Theorem 3.1 The sequence fsend off (k)g n
k=0 is a non-deceasing, B-feasible sequence with
minimal delay jitter.
Proof: It is straightforward to see from the definitions that send off
[arrival(k); arrival(k +B)] and hence the resulting sequence is B-feasible. Proving FIFOness
is done as follows. By definitions, it is sufficient to prove that P k  P k+1 +X a . To see this,
first note that by definition,
We distinguish between two cases now. If min(M)
Eq. (2) we have that P k+1  P k , and we are done. The second case is that min(M) !
In this case Eq. (2) implies that
and the proof of correctness is complete. The optimality of the solution follows immediately
from the minimality of M .
3.2 On-line Delay-Jitter Control Algorithm
We now turn to our main result for delay-jitter control: an on-line algorithm using 2B buffer
space, which guarantees delay-jitter bounded by the best jitter achievable by an off-line
algorithm using B space. The algorithm is simple: first the buffer is loaded with B packets,
and when the (B+1)-st packet arrives, the algorithm releases the first buffered packet. From
this time on, the algorithm tries to release packet k after kX a time. Formally, the algorithm
is defined as follows.
Algorithm B: on-line delay-jitter control. Define send

on a for all
n. The release sequence is defined by
send on
send

on (k); if arrival(k)  send

on

on

on
Clearly, Algorithm B is an on-line algorithm. We prove its jitter-control property.
Theorem 3.2 If for a given arrival sequence, an off-line algorithm using space B can attain
delay jitter J , then the release sequence generated by Algorithm B has delay-jitter at most J
using no more than 2B buffer space.
Proof: Obviously, the buffer space used by Algorithm B is at most 2B. The bound on the
delay-jitter follows from Lemma 3.4 and Lemma 3.6 proved below.
time
packet
number

Figure

2: An example for oriented jitter bounds. A point at coordinates (x; y) denotes that
packet y is released at time x. The slope of the dashed lines is 1=X a .
The following definition is useful in the analysis (see Fig. 2).
Definition 3.1 Let
k=0 be a time sequence. The oriented jitter bounds for packet k
are
0in
a g
0in
a g
Intuitvely, J oe (k) says by how much packet k is late compared to the earliest packet, and
J oe (k) says by how much k is premature comapred to the latest packet. We have the following
immediate properties for oriented jitter bounds.
Lemma 3.3 Let
k=0 be a time sequence with average inter-arrival times X a and
delay jitter J. Then
(1) For all k, J(k)  0 and J(k)  0.
(2) For all k,
(3) There exist k and k 0 such that
Proof:
1. Follows by choosing 3.1.
2. Let i be such that j. Rearranging, we have that
Assume w.l.o.g. that t i 0
. From the
definition it follows that t i 0
g.
Therefore,
0in
and
0in
Summing Eqs. (3,4), the result follows.
3. Follows by choosing Eqs. (3,4), respectively.
The following lemma shows that the deviation of the actual release time generated by
Algorithm B from the ideal 0-jitter sequence of fsend
on (k)g k is bounded. Somewhat surpris-
ingly, it is bounded by the oriented jitter bounds of two specific packets in any B-feasible
sequence.
Lemma 3.4 Let
k=0 be any B-feasible sequence for a given arrival sequence.
Then for all 0  k  n, we have \GammaJ oe (0)  send

on
Proof: We proceed by case analysis. If send on

on (k) then we are done by Lemma
3.3 (1). If send on (k) ? send

on (k), then by the specification of Algorithm B, we have that
send on arrival(k). In this case the lemma is proved by the following inequality.
send on
send off (k)
by definition of J oe (0)
send

on since send

on (0)  send off (0)

on
The last case to consider is send on

on (k). In this case, by the specification of
Algorithm B, we have that send on 2B). The lemma in this case is proved
by the following inequality.
send on
send off (k +B) by B-feasibility of off-line
by definition of J oe (B)
send

on

on (0)  send off (B)

on
The reader may note that since Lemma 3.3 (1,2) implies that J oe (0); J oe (0)  J oe , Lemma
3.4 can be used to easily derive a bound of 2J oe on the delay-jitter attained by Algorithm
B. Proving the promised bound of J oe requires a more refined analysis of the oriented jitter
bounds. To facilitate it, we now introduce the following concept.
Definition 3.2 Let
k=0 be a times sequence. Let t  t k . The times sequence oe
perturbed at k to t is
Intuitively, is the sequence obtained by assigning release time t to packet k, and
changing the times of other packets to preserve the FIFO order (see Fig. 3 for an example):
if packet k is to be released earlier than t k , then some packets before k may be moved as
well; and if packet k is to be released later than t k , then some packets after k may be moved.
The following properties for perturbed sequences are a direct consequence of the definition

k=0 be a times sequence, let k be any packet, and let t be any time
point.
packet
number
time
packet
number
time

Figure

3: An example of perturbation. Left: A sequence oe. Right: oe(5 : t). Note that in
were moved with respect to oe.
Proof: The simplest way to verify these claims is geometrical: Consider Figure 3, which
corresponds to the case of t Assertion (B1) says that if point k is not
moved left to the left diagonal line, then all points remain between the two diagonal lines,
and that there are points which lie on the diagonal lines. Assertion (B2) states that the
horizontal distance between point k and left diagonal line strictly decreases, and Assertion
states that for points below point k, the horizontal distance to the left diagonal line
does not increase. The case of t analogous.
To prove Theorem 3.2, we prove an interesting property of oriented jitter bounds in
optimal sequences. Intuitively, the lemma below says the following. Fix an arrival sequence,
and consider all optimal release sequences using B buffer space. Fix any two packets at
most B apart. Then it cannot be the case that in all optimal release sequences both the first
packet is too early and the second packet is too late. Formally, we have the following.
Lemma 3.6 Let J be the minimal delay jitter for a given arrival sequence using space B,
and let 0  i  j  n be packets such that j  i +B. Then there exists a B-feasible sequence
oe for the given arrival sequence with delay jitter J such that J oe (i)
Note that Lemma 3.6 with combined with Lemma 3.4, completes the proof
of Theorem 3.2. We shall use the general statement in Section 4.
Proof: Let oe be an optimal release sequence attaining jitter J for the given arrival se-
quence, in which J oe (i) + J oe (j) is minimal among all optimal sequences. First, note that if
either J oe then we are done since by Lemma 3.3 (1,2) we have that
J oe (i); J oe (j)  J . So assume from now on that J oe (i) ? 0 and J oe (j) ? 0. We claim that
in this case, t are released together (and hence all packets
are released together). We prove this claim by contradiction: suppose that t
Then it must be the case that either (i) t i ! arrival(j) or (ii) t j ? arrival(j), or both (i)
and (ii) hold. If case (i) holds, let t
and consider the
perturbed sequence oe(i : t) in which packet i is released at time t. By choice of t, we have
that (i). The perturbed sequence oe(i : t) has the following properties.
is B-feasible, since it may differ from oe at most by packets These
packets are held a little longer in oe(i : but they are released at time t ! arrival(j)
arrival(i +B).
The claim now follows for case (i), since Properties (1,2) imply that oe(i : t) is a sequence
using B buffer space which attains jitter J , but Properties (3,4) contradict the assumed
minimality of J oe (i) (j). A similar argument shows that if case (ii) holds, then for
arrival(j)g, the perturbed sequence oe(j : t) contradicts the minimality
of J oe (i)
Thus we have proved that for an optimal sequence, either J oe
which cases the lemma is proved), or else, for a sequence minimizing J oe (i) must
be the case that t . We now proceed to bound J oe (i) using the fact that t
First, note that since by definition there exists a packet k 1 such that t k 1
(j), and since by definition we get from the fact that
Similarly, we have that
Adding Equations (5,6), we get that
we conclude that
as required.
3.3 A Lower Bound for On-line Delay-Jitter Control Algorithms
We close this section with a lower bound for on-line delay-jitter control algorithms. The
following theorem says that any on-line algorithm using less than 2B buffer space pays
heavily in terms of delay jitter when compared to an off-line algorithm using space B.
Theorem 3.7 Let 1  ' ! B. There exist arrival sequences for which an off-line algorithm
using space B gets jitter 0, and any on-line algorithm using 2B \Gamma ' buffer space gets delay-jitter
at least 'X a . Moreover, there exist arrival sequences for which an off-line algorithm
using space B gets 0-jitter, and no on-line algorithm using less than B buffer space can
guarantee any finite delay jitter.
Proof: Consider the following scenario. At time 0, packets arrive, and at time
arrive. First, note that there is an off-line algorithm attaining 0
jitter by releasing each packet k at time k \Delta X a . Consider now any on-line algorithm Z. We
first claim that Z cannot release packet 0 before packet B arrives: otherwise, packet B may
arrive arbitrarily far in the future, making the delay jitter of the on-line algorithm arbitrarily
large. Hence, at time B \Delta X a , when B+1 new packets arrive, algorithm Z still stores the first
packets, and since it has buffer space 2B \Gamma ' by assumption, it is forced to release at least
immediately. Since the delays of packets 0 and ' are equal, it follows from the
definition of delay-jitter that the delay-jitter of the release sequence is at least 'X a .
For the case of an on-line algorithm with less than B space, consider the scenario where
a batch of B packet arrive together at time 0, and then a batch of B more packets arrive at
time T for some very large T . Since the on-line algorithm has to release packet 0 at time 0,
we have that its delay jitter is at least T=(B \Gamma 1), which can be arbitrarily large.
4 Distributed Delay-Jitter Control
In Section 3 we have considered a single delay-jitter regulator. In this section we prove an
interesting property of composing many delay-jitter regulators employing our Algorithm B.
Specifically, we consider a path of m links connecting nodes v is the
source and v m is the destination. We make the simplifying assumption that the propagation
delay in each link is deterministic. We denote the event of the arrival of packet k at node j
by arrival(k; j), and the release of packet k from node v j by send(k; j). The input stream,
generated by the source, is fsend(k; 0)g k (or farrival(k; 1)g k ), and the output stream is
fsend(k; m)g k . Each node has 2B=m buffer space, and for simplicity we assume that m
divides B. The distributed algorithm is the following.
Algorithm BD: distributed on-line delay-jitter control. For each 1  j  m, node
buffer space 2B=m. Specifically, node j sets send

on (k;
a , and it releases packet k as close as possible to send

on (k; j) subject to
2B=m-feasibility (see Algorithm B).
We prove that the jitter control capability of Algorithm BD is the same as the jitter
control capability of a centralized jitter control algorithm with B total buffer space, under a
certain condition for the beginning of the sequence (to be explained shortly). Put differently,
one does not lose jitter control capability by dividing the buffer space along the path. The
precise result is given in the theorem below.
Theorem 4.1 Suppose that for a given arrival sequence
k=0 , there exists
a centralized off-line algorithm attaining jitter J using space B, with packet 0 released before
time arrival(B=m). Then if oe is the release sequence of node v 0 , the release sequence
fsend on (k; m)g k generated by Algorithm BD at node v m has delay jitter at most J.
Intuitively, the additional condition is that there is a way to release the first packet
relatively early by a centralized optimal algorithm. This condition suffices to compensate for
the distributed nature of Algorithm BD. The condition is also necessary for the algorithm to
are input into the system at the start of the algorithm, then an off-line
algorithm can still wait arbitrarily long before starting to release packets, while Algorithm
BD is bound to start releasing packets even if only 2B
The proof is essentially adapting the proofs of Algorithm B in Section 3 to the distributed
setting. We highlight the distinguishing points.
Let the propagation delay over link (v j
the total
delay of links on the path.
The first lemma below bounds the desired release times of all packets at one node in
terms of the desired release times in upstream nodes.
Lemma 4.2 For all nodes 1  j  i  m and all packets k,
send

on (k;

on (k; i)  send

on
Proof: Consider the lower bound first. By the algorithm, we have that for all ', send

on (0;
send on (0; '). Since for all ' ? 1, send

on (0; ')  send on (0; we obtain by induction
on

on (k; i)  send

on (k;
proving the lower bound.
We now prove the upper bound. First, we claim that for all 1  i  m,
send on (k; ')  send

on (k; ') for 0  k
Eq. (7) follows from the fact that by the specification of Algorithm B, a node starts releasing
packets only if all first B
are in its buffer, and therefore none of the first B
packets is released too late in any node. We now prove the upper bound by induction on
j. The base case, trivial. For the inductive step, fix j and consider i
have
send

on
a by algorithm
send

on (0; i)
m )X a by (7)
send

on (0;
)X a by induction

on (k;
rearranging

on
For the case of underflow, we argue that if a packet is "late" in the output node v n , then
it was late in all nodes on its way.
Lemma 4.3 If send on (k; m) ? send

on (k; m), then send on (k; m)
Proof: First, we show that for any node v j , if send on (k;

on (k; j), then send on (k;

on 1). This is true since by the specification of Algorithm B, at time
send

on (k; j) the buffer at node j is empty, and hence node v j \Gamma1 has not sent packet k by time
send

on (k;

on

on (k; this implies that send on (k;
send

on 1). Therefore, for all nodes v j , we have that send on (k; and by
summation we obtain that send on (k; m) = send on (k;
For the case of overflow, we show the analogous property: if there is an overflow in the
output node, then it is the result of a "chain reaction" of overflows in all nodes.
Lemma 4.4 If send on (k; m) ! send

on (k; m), then send on (k; m)
Proof: We prove that if send on (k; i) ! send

on (k; i) then send on

send on
by the bound on the buffer size
send

on (k; i) \Gamma d i by our assumption
send

on
send

In other words, if packet k is overflowing at node m, then packet k
m is overflowing
in node i, for each 1  i  m. Hence for each i, we have send on
. The lemma follows.
The lemmas above are used in the proof of the following variant of Lemma 3.4.
Lemma 4.5 Let
k=0 be any B-feasible sequence for a given arrival sequence
such that send off (0)  arrival(B=m; 1). Then for all 0  k  m, we have \GammaJ oe (0)
send

on (k; m) \Gamma send on (k; m)  J oe (B=m).
Proof: If send

on (k; m) = send on (k; m) we are done by Lemma 3.3 (1). If send on (k; m) ?
send

on (k; m), then
send on (k; m) = send on (k; 0) +D by Lemma 4.3
send off (k) +D since send on (k;
send

on (0; since send off (0)  arrival(
send

on (0; m)

on (k; m)
If send on (k; m) ! send

on (k; m), then
send on (k; m)
send off (k +B) +D since off-line has B space
send off ( B
arrival(
send

on (0;

send

on
Theorem 4.1 follows from Lemma 4.5, when combined with Lemma 3.6 (which is independent
of the on-line algorithm), with
5 Rate-Jitter Control
In this section we consider the problem of minimizing the rate-jitter, i.e., how to keep the
rate at which packets are released within the tightest possible bounds. We shall use the
equivalent concept of minimizing the difference between inter-departure times. We present
an on-line algorithm for rate-jitter control using space 2B compare it to an off-line
algorithm using space B and guaranteeing jitter J . Our algorithm guarantees rate jitter
at most J constant c. We also show how to obtain rate jitter which
is a multiplicative factor from optimal, with a simple modification of the algorithm. The
algorithm can work without knowledge of the exact average inter-arrival time: in this case,
jitter guarantees will come into effect after an initial period in which packets may be released
too slowly. We also show that without doubling the space, no guarantees in terms of the
optimal rate-jitter can be made. As an aside, we remark that off-line rate-jitter control can
be solved optimally using linear-programming technique.
5.1 On-line Rate-Jitter Control Algorithm
We now turn to describe the main result for this section: an on-line algorithm for rate-jitter
control. The algorithm is specified with the following parameters:
ffl B, the buffer size of an off-line algorithm, i.e. B
space parameter for the on-line algorithm, such that B on
ffl I min ; I bounds on the minimum and maximum inter-departure time of an off-line
algorithm.
ffl X a , the average inter-departure time in the input (and also the output) sequence.
The parameters I min and I max can be thought of as requirements: these should be the worst
rate jitter bounds the application is willing to tolerate. The goal of a rate-jitter control
algorithm is to minimize the rate jitter, subject to the assumption that space B is sufficient
(for an off-line algorithm) to bound the inter-departure times in the range [I min ; I max ]. A
trivial choice for I min and I max is X min and X max , which are the minimal and maximal inter
arrival times in the input sequence. However, using tighter I min and I max , one may get a much
stronger guarantee. The jitter guarantees will be expressed in terms of B; h; I
and J , the best rate jitter for the given arrival sequence attainable by an off-line algorithm
using space B.
Note that for an on-line algorithm, even achieving rate jitter I max \GammaI min may be non-trivial.
These are bounds on the performance of an off-line algorithm, whose precise specification
may depend on events arbitrarily far in the future.
The basic idea in our algorithm is that the next release time is a monotonically decreasing
function of the current number of packets in the buffer. In other words, the more packets
there are in the buffer, the lower the inter-departure time between the packets (and thus the
higher the release rate).
Algorithm C: on-line rate-jitter control. The algorithm uses B on
space. With each possible number 0  j  2B + h of packets in the buffer, we associate an
time denoted IDT(j), defined as follows. Let
I
I
I
Note that IDT(j) is a monotonically decreasing function in j. The algorithm starts with
a buffer loading stage, in which packets are only accumulated (and not released) until the
first time that the number j of packets in the buffer satisfies IDT(j)  X a . Let
a g, and let T   denote the first time in which the number of packets in
the buffer reaches S. At time T   , the loading stage is over: the first packet is released
and the following rule governs the remainder of the execution of the algorithm. A variable
last departure is maintained, whose value is the time at which the last packet was sent. If
at time t, we have t  last departure+IDT(j), where j is the number of packets currently
in the buffer, then we deliver a packet and update last departure.
The rate-jitter bound of Algorithm C is given in the following theorem.
Theorem 5.1 Let J be the best rate-jitter attainable (for an off-line algorithm) using buffer
space B for a given arrival sequence. Then the maximal rate-jitter in the release sequence
generated by Algorithm C is at most J
h , and never more than I
The idea in the proof of Theorem 5.1 is that the number of packets in the buffer is never
more than slots away from the slots which correspond to rates generated by an
optimal off-line algorithm. We now formally analyze Algorithm C. Fix an optimal execution
of the off-line algorithm. Let us denote the maximum and minimum inter-departure times
of the off-line execution by Y max and Y min , respectively. (Hence the jitter attained by the
off-line algorithm is Y these quantities, we also define the following terms.
I
I
Note that L  S  U . We shall also use the following shorthand notation. Let B on (t) and
denote the number of packets stored in time t in the buffers of the Algorithm C and of
the off-line algorithm, respectively, and let i.e., how many packets
does the Algorithm C has more than the off-line algorithm at time t. We use extensively the
following trivial property of the difference.
Lemma 5.2 For all t, \GammaB  diff(t)  B on (t).
Proof: Immediate from the fact that 0  B off (t)  B.
Let S on the number of packets sent by Algorithm C in the time interval
analogously for the off-line algorithm. The following lemma
states that the difference is modified according only to the difference in the packets released.
Lemma 5.3 For any two time points
Proof: Consider the events in the time interval arrival increases the number
of stored packets for both the off-line and Algorithm C, and hence does not change their
difference. It follows that diff(t 2 exactly the difference in the number of packets
sent by the two algorithms in the given interval.
The significance of Lemma 5.3 is in that it allows us to ignore packet arrivals when
analyzing the space requirement of an algorithm: all we need is to consider the difference
from the space requirement of the off-line algorithm. The following lemma, which bounds
the minimal inter-departure time of Algorithm C, is an example for that.
Lemma 5.4 For all times t, diff(t)  U + 1.
Proof: Let t be any point in time. If B on (t)  U + 1, the lemma follows immediately. So
assume that B on (t) ? U be a point such that B on (t 0 )  U and B on (t 0 )  U
for all t Such a point exists since B on (T   Consider the time interval
t]: in this interval, at most
Y min
were released by the off-line algorithm,
while Algorithm C has released at least
I U
Y min
, and hence S on
Since by Lemma 5.2 we have that diff(t 0 )  U , the result follows from Lemma 5.3.
Similarly, we bound the difference from below.
Lemma 5.5 For all times t ? T   , diff(t)
Proof: Let t ? T   be a point in time. The case of B on (t)
be a point such that B on (t 0 )  L and B on (t 0 )  L for all
t]. The point t 0 must exist since B on (T   L. For the time interval
we have that S off
, and S on
I L
B, the result follows from Lemma 5.3.
We now prove Theorem 5.1.
Proof of Theorem 5.1: By Lemma 5.4, at all times t, B on (t)  hence the
minimal inter-departure time of Algorithm C is smaller than Y min by less than (B+2) Imax \GammaI min
h .
By Lemma 5.5, for all times t ? T   , the maximal inter-departure time of Algorithm C is
larger than Y max by less than (B
h . Since since no packets
is released before time T   , the theorem follows.
It is worthwhile noting that doubling the space is mandatory for on-line rate-jitter control
(as well as for delay-jitter control), as the following theorem implies.
Theorem 5.6 Let 1  ' ! B. There exist arrival sequences for which an off-line algorithm
using space B gets 0-jitter, and any on-line algorithm using 2B \Gamma ' buffer space gets rate-jitter
at least X a
The proof of Theorem 5.6 is similar to the proof of Theorem 3.7, and we therefore omit it.
5.2 Adapting to Unknown X a
We can avoid the need of knowing X a in advance, if we are willing to tolerate slow rate in
an initial segment of the online algorithm. This is done by changing the specification of
the loading stage of Algorithm C to terminate when the buffer contains B packets (which
corresponds to inter-arrival time of I max , as opposed to inter-arrival time of X a in the original
specification). Thereafter, the algorithm starts releasing packets according to the specification
of IDT. Call the resulting algorithm C \Gamma . Below, we bound the time which elapses in
an execution of C \Gamma until the buffer size will reach the value of L. Clearly, from that point
onward, all guarantees made in Theorem 5.1 hold true for Algorithm C \Gamma as well.
Lemma 5.7 Consider an execution of Algorithm C \Gamma . Let T   be the time where the initial
loading ends, and let T + be the first time such that B on (T
Proof: For to be the first time after T   where B on (t i )
Consider a time interval its length by  i . Denote the number of packets
arriving in the interval by A i . Consider the off-line algorithm: For all 1  i
have that
Consider now the execution of Algorithm in the time interval the inter-departure
time is at least Y therefore S on
Ymax+iffi . Using Eq. (8)
and since B on (t by definition, we have
i.e.,
\GammaY
Summing over noting that
and that \GammaB
5.3 Multiplicative Rate Jitter
For some applications, it may be useful to define jitter as the ratio between the maximal
and minimal inter-arrival times. We call this measure the multiplicative rate jitter, or m-rate
jitter for short. It is easy to adapt Algorithm C to the case where we are interested in the
m-rate jitter. All that is needed is to define
I
I
I
for . In this case we obtain the following result, using the same proof
technique as for Theorem 5.1.
Theorem 5.8 Let J be the best m-rate-jitter attainable (for an off-line algorithm) using
buffer space B for a given arrival sequence. Then the maximal m-rate-jitter in the release
sequence generated by Algorithm C using function IDTm is at most J \Delta
h .
6 Conclusion
In this paper we have studied jitter control algorithms, measured in terms of guarantees
relative to the best possible by an off-line algorithm. Our results for delay jitter show that
the simple algorithm of filling half the buffer has a very strong relative property. For rate
jitter, we proposed a simple algorithm where the release rate is proportional to the fill level of
the buffer, and showed that its relative guarantees are quite strong as well. We have studied
a very simple distributed model for jitter control. We leave for further work analyzing
more realistic models of systems, including multiple streams and more interesting network
topology.



--R

Online Computation and Competitive Analysis.
Client requirements for real-time communication services


ATM Networks: Concepts
Rate control servers for very high-speed networks
Competitive snoopy caching.
An Engineering Approach to Computer Networking.
Isochronous applications do not require jitter-controlled networks
Amortized efficiency of list update and paging rules.
Computer Networks.
The ATM Forum Technical Committee.
Guaranteeing delay jitter bounds in packet switching networks.
Charcterizing traffic behavior and providing end-to-end service guarantees within ATM networks

Service disciplines for guaranteed performance service in packet-switched networks

Comparison of rate-based services disciplines
A New Architecture for Packet Switched Network Protocols.
--TR
Amortized efficiency of list update and paging rules
A stop-and-go queueing framework for congestion management
Comparison of rate-based service disciplines
On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements
ATM networks (2nd ed.)
Leave-in-Time
Computer networks (3rd ed.)
An engineering approach to computer networking
Online computation and competitive analysis
Characterizing Traffic Behavior and Providing End-to-End Service Guarantees within ATM Networks

--CTR
Khuller, Problems column, ACM Transactions on Algorithms (TALG), v.2 n.1, p.130-134, January 2006
Pal , Mainak Chatterjee , Sajal K. Das, A two-level resource management scheme in wireless networks based on user-satisfaction, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.4, October 2005
Yiping Gong , Bin Liu , Wenjie Li, On the performance of input-queued cell-based switches with two priority classes, Proceedings of the 15th international conference on Computer communication, p.507-514, August 12-14, 2002, Mumbai, Maharashtra, India
buffer overflow and underflow;competitive analysis;streaming connections;jitter control;quality of service networks