ADVERSARIAL QUEUING IN PACKET ROUTING
by
Lakshmi Anantharamu
B.S., Electrical Engineering, National Inst of Engineering
University of Mysore, India
A thesis submitted to the
University of Colorado at Denver
and Health Sciences Center
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science and Engineering
2006 .
This thesis for the Master of Science
degree by
Lakshmi Anantharamu
has been approved
by
Bogdan S. Chlebus
Tom Altman
Date
Lakshmi Anantharamu (M.S., Computer Science and Engineering)
Adversarial Queuing in packet routing
Thesis directed by Associate Professor Bogdan S. Chlebus
' ABSTRACT
We consider an overview of adversarial queuing in packet routing in communi
cation networks, when the packets are injected continuously by the adversary. In
a more traditional stochastic approach, probabilistic assumptions are made about
the injection rate of the packets. In an adversarial model there are no probabilistic
assumptions, but the number of packets injected by an adversary that requires an
edge is restricted within a window or time interval.
The network is abstracted as a graph. A contention resolution protocol is a
scheduling policy that determines which packet has priority, when there is more
than one packet requiring to traverse an edge. Given a network, a contention
resolution protocol and such an adversary, the fundamental question is when is
such a setting stable?
The injection rate cannot be more than 1 since only one packet can traverse an
edge at a time. We review the stability results of various networks and scheduling
policies at injection rate 1. Even though some of the networks and scheduling
policies are not stable at injection rate 1, they are stable at injection rates less
than 1. Such stability is called universal stability. We review a number of such
universal stability results for various networks and scheduling policies.
This abstract accurately represents the content of the candidate thesis. I rec
ommend its publication.
Signed
Bogdan S. Chlebus
CONTENTS
Tables..................................................................... vi
Chapter
1. Introduction................................................................ 1
1.1 Communication Network..................................................... 1
1.2 Packets .................................................................. 2
1.3 Scheduling policies..................................................... 2
1.4 Stability................................................................. 3
2. Adversarial Model........................................................... 4
2.1 Window defined adversary.................................................. 4
2.1.1 Formal model for window defined adversary........................... 5
2.2 All intervals defined adversary........................................... 5
2.2.1 Formal model for all intervals defined adversary.................... 6
2.3 Stability................................................................. 7
2.3.1 Stability of a network ................................................ 7
2.3.2 Stability of a protocol................................................ 7
2.3.3 Universal stability of a network..................................... 7
2.3.4 Universal stability of a protocol.................................... 7
2.3.5 Relationship between maximum queue size and maximum end to end
delay.................................................................. 8
3. Stability results of networks and protocols................................. 9
3.1 Stability results for DAG................................................. 9
3.2 Stability results for ring............................................... 10
3.2.1 Instability of LIS and FIFO............................................ 10
3.2.2 Stability of FTG............................................... 12
4. Universal stability results of networks and protocols................... 15
IV
4.1 Universal stability of networks....................................... 15
4.1.1 Universal stability of ring...................................... 15
4.2 Universal stability of protocols...................................... 19
4.2.1 Universal stability of SIS....................................... 19
4.3 Upper bounds on queue size and end to end delay of greedy protocols 21
5. Other results in Adversarial queuing theory............................. 22
6. Conclusion.............................................................. 23
References................................................................. 25
v
LIST OF TABLES
Table
4.1 Universal stability of greedy protocols .......................... 19
4.2 Upper bounds on queue size and end to end delay for some greedy
protocols ........................................................ 21
vi
1. Introduction
The goal is to review the analysis of stability and universal stability of net
works and scheduling policies in terms of packet queuing in an Adversarial model,
where the adversary is injecting packets dynamically. The stability and bounds for
various networks and protocols do not depend on any probabilistic assumptions.
1.1 Communication Network
A communication network is a routing network which is represented as a di
rected graph. Each Computing unit is represented as a node in the graph. Com
puting units communicate by exchanging messages which are encapsulated as
packets. Each node has a buffer to hold packets until they are transmitted. There
are two models of communication.
Synchronous
Asynchronous
Here synchronous communication in the network is considered, where time
proceeds in discrete steps or rounds.
Network: A network is abstracted as a graph and some of the different repre
sentations of the network are
DAG
Ring
Mesh
Hypercube
Butterfly
1
1.2 Packets
Packet: A packet is an atomic entity that is at a node called the source and
needs to travel along a path in the network to reach a destination node. The
packet encapsulates the message that is being sent from source to destination.
When there is a contention between multiple packets to traverse the same edge,
then packets are stored at the node buffer. This represents the queue at the node.
Packet routing : A packet is sent from source to destination node. A packet
is said to be absorbed once it reaches the destination. During each step, a packet
may be sent from its current node along one of the outgoing edges from that node.
At most one packet may travel along any edge of the network in a step. If the
path of traversal of a packet is fixed at the time of injection, then such a routing
is called nonadaptive routing. If the path that the packet takes from source to
destination is not fixed then it is called adaptive routing.
Packet queuing : Any packets that wish to travel along an edge e at a particular
time step but are not sent wait in a queue for edge e.
Delay of a packet : The number of time steps that a packet waits to traverse
an edge is called the delay of the packet.
1.3 Scheduling policies
A scheduling policy specifies, for each edge e and each time step, which
packet (amongst those waiting) is to be moved along edge e. A greedy scheduling
policy(called a workconserving policy in the terminology of queuing theory) al
ways specifies some packet to move along edge e if there are packets waiting to
use edge e. Here are some greedy scheduling policies.
FIFO (FirstInFirstOut). This is also called FCFS (FirstComeFirst
Served).
LIFO (LastInFirstOut). A packet that was injected last is given priority.
LIS (LongestInSystem). A packet originates at a specified time, and pri
ority is given to the packet that has been in the network for the longest
amount of time.
2
NIS (NewestInSystem). Similar to LIS but now priority is given to the
packet that has spent the least amount of time in the network.
SIS (ShortestInSystem). Gives precedence to the packet most recently
injected.
NTS (NearestToSource). Gives precedence to the packet whose distance
to source is minimal.
FFS (FarthestFromSource). Gives precedence to the packet whose distance
to source is maximal
FTG (FurthestToGo). Each packet has a prescribed path, and priority
is given to the packet which has the largest number of edges still to be
traversed.
NTG (NearestToGo). Similar to FTG but now priority is given to the
packet that has the smallest number of edges still to be traversed.
1.4 Stability
A network is stable for a given routing protocol and adversary when the queues
at the nodes are bounded at all times. It is defined more formally and in detail in
the coming chapters.
3
2. Adversarial Model
As opposed to probabilistic assumptions in stochastic adversary in the ad
versarial model an adversary injects packets continuously in the system. The
adversary is defined as a ratep adversary and there are two different ways of
defining it.
Window defined adversary: represented as (w, p) adversary.
All intervals defined adversary: represented as (b, p) adversary
2.1 Window defined adversary
The window defined adversarial model was developed in paper [3]. A routing
network is modeled as a directed graph and time proceeds in discrete steps or
rounds. An Adversary generates a set of requests at each time step. A request
is a path specifying the route followed by a packet. It is said that the adversary
injects a set of packets when it generates a set of requested paths. The path could
be fixed at the time of injection which is nonadaptive routing. Adaptive routing
is considered in paper [4].
An unrestricted adversary can demand more bandwidth than available by
flooding the network. So a restriction is introduced. Let w be an arbitrary posi
tive integer, e any edge and and t any sequence of w consecutive time steps. Let
N(t, e) be the number of paths injected by the adversary during time interval t
that traverse edge e. For any p > 0, a (w, p) adversary that injects paths as per
the following load condition is defined: for every sequence r of w consecutive time
steps and for every edge e, N(r,e)/w < p. It is said that such a (w,p) adver
sary injects packets at rate p with window size w. A rate p adversary is a (w, p)
adversary for some w. If the rate p were greater than one, an adversary would
congest some edge (since the service rate of every edge is assumed to be 1) and
the network would be unstable. Hence, it is assumed that p < 1.
2.1.1 Formal model for window defined adversary
4
Here are all the definitions for the formal model of a window defined adversary.
Definition of a packet : A Packet P is a triple (ID,p, t) where ID is some
unique identifier, p is the path from the source to the destination and i is the time
the packet was injected into the network.
State definition : The Statet(P) of a packet P at time t is the vector
(P,I,ti,ti), where U is the number of time steps in which the packet has tra
versed an edge in itSs path and tj is the time of jth such traversal.
Configuration: For a network G at time t the configuration configt(G) is de
fined as configt(G) = {statet(Pk)\Pk is a packet that is present in the network at
time t}. The configuration implicitly specifies the states of packets in each edge
queue of the network. The initial configuration of the network is configo{G) at
step t = 0.
Now to formally define a deterministic adversary A as a function:
OO
.4: Lb x rij=0 configt(G)\ > {Pk \ Pk is a new packet}
3=o
that is A(t, nÂ£=0 configt(G)) specifies the new packets that the adversary A injects
into the network at time t and it does so based on the entire history of the routing
up to this point of time.
A network system is defined as the tuple (G,Y,T), where G is the graph, Y is
deterministic rate 1 adversary and T is any scheduling policy.
2.2 All intervals defined adversary
An adversary for all intervals and not just the predefined window size was
defined in [2]. But these two ways of defining the adversary is essentially the
same.
In the model of interval defined adversary, bursty injection patterns axe allowed
by introducing a component for burstiness as follows: The rate of an adversary is
specified by a pair (b,r) where b > 1 is a natural number and 0 < r > 1. The
restriction on the adversary is : of the packets that the adversary injects in any
interval I, at most r \ I \ +b can have paths that contain any one edge. Because
of the burstiness factor an adversary can inject a large number of packets that
5
all request the same edge as long as there are no more than r \ I \ +b packets
requesting the same edge over interval I.
This model of intervals defined bounded adversary is derived from the bucket
based techniques used for shaping of traffic in packet switched networks. To not
to restrict to session oriented systems, the adversary requirements is defined in
such a way that each edge has an associated bucket with it.
2.2.1 Formal model for all intervals defined adversary
To formalize the model that will be used to ask questions and find answers here
are a few definitions:
G: The network is modeled as a graph G.
A: A is an adversary that injects packets in the system.
V: V is a protocol that moves the packets across edges.
(G, A, V) is a system where the timeevolution of G is induced by adversary A
and protocol V.
Timeevolution of G: Configuration Ct : It is the current configuration of the
system at time step t. This is a collection of sets {S'* : e e G}, such that Si is the
set of packets waiting in queue for e at the end of step t. From the configuration
Cl we obtain the configuration Ct+1 for the next time step as follows:
1. Add new packets to some sets Si each of which has an assigned path in G.
2. For each nonempty set Si, delete a single packet p G Si as specified by a
contention resolution protocol and insert it into set where f is the edge
following e on its assigned path. If e is the last edge on the path of p, then
p is not inserted into any set.
A timeevolution of G, of rate (b,r) is simply a sequence of such configurations
C1, G2,..., such that for all edges e and all intervals I, no more than r  I  +b
packets are introduced during I with an assigned path containing e. Informally
each time step consists of three phases as follows:
1. Packets are injected by A.
2. Packets are moved by V.
6
3. Packets that reach their destinations in Phase 2 are absorbed.
2.3 Stability
Here are the definitions of stability and universal stability of network and
protocol.
2.3.1 Stability of a network
A network system (G,Y,T) is stable, if for every initial configuration Cq(G)
there is a constant C (which may depend on the size of the network G, the initial
configuration and the rate and window parameters of the adversary class Y) such
that for every adversary A in the class of adversaries Y, when the network system
is executed with initial configuration Co(G) against adversary A (i.e., is executed
using the deterministic adversary A to generate packets and the scheduling policy
T to route packets), the maximum number of packets in any queue is bounded by
C.
2.3.2 Stability of a protocol
A protocol V is said to be stable on a network Q against an adversary A when
there is a constant C (which may depend on Q and A) such that, starting from an
empty configuration, the number of packets in the system at all times is bounded
by C.
2.3.3 Universal stability of a network
A network G is said to be universally stable if every greedy protocol is stable
against every adversary of rate less than 1 on G.
2.3.4 Universal stability of a protocol
A protocol V is universally stable if it is stable against every adversary of rate
less than 1, on every network.
Basic Algorithmic question: Universal stability is a very basic algorithmic
problem for graphs. The very basic algorithmic question that is being tried to an
swer is: When is a given contentionresolution protocol stable in a given network,
against a given adversary?
Prom a practical standpoint stability is not enough to evaluate performance of
various networks and scheduling policies. To evaluate the performance of stable
systems we need two more parameters as follows
7
Maximum queue size required.
The size of a queue is the number of packets waiting to cross the edge.
Maximum end to end delay any packet can experience.
The delay experienced by a packet is the time between injection of the packet
and the absorption of the packet.
2.3.5 Relationship between maximum queue size and maximum end
to end delay
Theorem 2.3.1 Let (G, A, V) be a system, where G is a graph with m edges, V
is any greedy protocol and A is an adversary of rate (b, 1 e), 0 < Â£ < 1. Suppose
there are never more than k packets in any queue, where mk > b. Then any
packet that is injected with a path of length d will be absorbed in at most
steps. Conversely, if the maximum delay experienced by any packet is at most s,
then there are never more than s packets in any queue.
Proof: This proof is done by contradiction. Let the maximum number of packets
in any queue q at any time t = k.
So total number of packets in the system = mk
Assume: Queue q at any time t becomes empty sometime in the next steps.
For if not then a packet must leave q on each of the next steps.
But there are only mk packets in the system at time t and the total number of
packets that can arrive at q in the next steps is given by (by the definition
of the bounded adversary)
. 2mk , 2mk , , 2mkd
(1 Â£)h b =2mk + b <mk
Â£ Â£ Â£
This is more than mk which is the maximum number of packets that are in the
system (k being the maximum queue size). This contradicts the assumption that
a packet leaves q in every time step.
From this above contradiction it is proved that a packet crosses at least one edge
in steps. Hence if a packet must cross d edges, it happens in time steps.
Now suppose that the maximum packet delay is at most s. If any queue has
more than s packets, then the last packet to leave q will experience a delay more
than s, which is a contradiction.
8
3. Stability results of networks and protocols
Networks are abstracted as graphs. Let G represent such a graph. Here are
some of the results for DAG and ring for rate < 1. A window defined adversary
is used for all the results. For further details on these please refer to [3].
3.1 Stability results for DAG
Every DAG is universally stable for rate 1 deterministic adversaries. If G is
a DAG, and Y is the class of deterministic rate 1 adversaries, then (G, Y, T) is
stable for every greedy queuing discipline T.
Theorem 3.1.1 Let G denote an arbitrary directed acyclic graph, T an arbitrary
greedy protocol, and Y the class of deterministic rate 1 adversaries. Then (G, Y, T)
is stable.
Proof: Let G be the DAG and e be any edge of G. Let At(e) denote the number
of packets that have arrived by time t in G and are eventually destined to cross
edge e, but are not yet absorbed Let Qt(e) denote the queue at edge e at time
t. Let w be the window size and let the injection rate of A be 1. For any edge e,
there exists a window w such that between (t w, t] only w packets destined to
cross edge e can be injected in G.
Define a function \t;() inductively on the edges as follows: For an edge e,
suppose fl, . fk are edges entering the tail of e. (Notice there may be no such
elements and then we just take k to be zero.)
k
F(e) = max{2w, Qo(e)} + Â£*(/<) (3.1.0.1)
1=1
Now claim that for all t = l w > 0 and all e E G we have
At(e) < W(e) (3.1.0.2)
Note that for any time t' such that t w < t, A!t{e) < AtW(e) + w. The
9
theorem will then follow, since T(e) gives an absolute upper bound on the
number of packets in the system, in terms of the initial configuration.
The proof of this claim proceeds by induction on l. The claim clearly holds when
l = 0. Now let t = Iw fori > 1. Suppose e is an edge whose tail is entered by
edges fl, . fk. We consider two cases.
Case 1. AtW(e) < w + SL1^(/j). In this case, we use the fact that in w
time steps the number of new packets inserted that wish to cross the edge tj is at
most w. Thus, in this case
k
At(e) < AtW(e) + w < 2w + Â£*(
i=l
Case 2. At~w(e) > w + By the inductive assertion we have that
Atw{fi) < $(/*)..But notice that At_w(e) is at most Qtw(e) + J2i=i Aw(fi)
Thus, we have
k k k
Qtwifi) Atui(fi) ^ ^ AtW(fi) W T Â£*)Â£ Atw(fi) w
i=l i=1 i=1
In other words, the number of packets queued at edge e must be at least w at the
beginning of time step t w. Thus, in the next w time steps, at least one packet
crosses the edge e in every step. But the number of packets inserted which wish
to cross this edge may go up by at most w in w time steps. Thus, in this case
also, we have At{e) < AtW(e) < ^(e).
The upper bound on the number of packets in the system that follows from this
proof is exponential in the number of edges of G.
3.2 Stability results for ring
Here are the stability results for ring.
3.2.1 Instability of LIS and FIFO
LIS and FIFO are not stable for a ring against an adversary with injection rate
1. In LIS priority is given to packet that has been in the system the longest and
in FIFO priority is given to packet based on FirstComeFirstServed. To prove
instability we have to show that the queue grows unbounded for some execution
of the protocol. Here is the proof for both LIS and FIFO for a ring.
10
Theorem 3.2.1 There is a deterministic adversary A (respectively, an adversary
A!) that injects single paths onto the ring at rate 1, such that A (respectively, A')
will force the scheduling rule LIS (respectively, the scheduling rule FIFO) to have
unbounded size queues.
Proof: First describe the adversary A for LIS. For simplicity of presentation,
assume that each path requested by A will be a self loop, a path that traverses
all the edges of the ring in sequence. It is not difficult to refine this argument so
that the adversary injects shorter paths. A works as follows:
For k = 1, 2, 3, . .
Inject kn selfloops in sequence at node 1.
Inject kn selfloops in sequence at node 0.
It is easy to verily by induction on k > 1 that at the end of iteration k of this
process, there will be one packet at node 1 (destined for node 0) and kn1 packets
queued at node 0 (also destined for node 0). Thus the number of packets becomes
unbounded. The adversary for the FIFO case is similar but a bit more complicated.
To simplify the presentation, the proof of this case is done by contradiction. Say
there is an absolute bound M such that the number of packets in the system is
bounded by M for every adversary. Let us first show how to construct an adversary
that contradicts this bound M. The adversary, A first does an initial phase 0 and
then works in phases indexed by k as follows:
For k 1,2, 3,...
Inject (M + 1 )n selfloops in sequence at node k(modn).
The invariant that will be established is that at the end of phase k all packets in
the network are destined for node k with one packet at each queue other than the
queue on the edge from k > k + 1, which has Qk packets in its queue where the
Q'ks form a monotone increasing sequence in k. Thus, by the end of M phases we
derive a contradiction.
Assume an empty initial configuration. For phase 0, the adversary simply
injects n self loops at node 0. Thus the invariant is initially satisfied for k = 0
with Qo = 1. Assume that the invariant is true at the end of phase k 1. We make
some observations on the transient behavior in phase k.We start by observing that
11
once the invariant is established for some time step during phase k, it continues
to hold in all subsequent time steps in phase k. Next notice that throughout this
phase there is at most one packet queued in every queue other than queues k and
k 1. The number of packets queued at k 1 is monotone nonincreasing and the
number of packets queued at k is monotone nondecreasing. Furthermore, since
the queues at nodes k and k 1 are of length at most M, no packet waits at any
queue for more than M time steps. Thus, after at most Mn time steps in phase k,
every packet injected in phase 0 to k 1 has reached its destination. In at most n
more time steps, we reach the invariant that all the queues other than k 1 and
k have exactly one packet in their queue. To conclude, we need to show that the
queue at node k 1 does eventually drain down to having 0 and then 1 packet;
and that the queue size at k at the end of phase k is strictly larger than the queue
size at k 1 at the beginning of this phase.
To verify the first part, notice that the queue size at node k 1 (which consists
of both phase k 1 packets destined for node k 1 as well as phase k packets
destined for node k) is upper bounded by the number of packets in the system
with destination k 1. This observation is easily verified by induction on time.
Moreover, since the queue size goes down every time a packet with destination
k 1 reaches its destination, the queue becomes empty (for one time step). Finally,
we need to verify that Qk, the number of packets at queue k at the end of phase
k, is greater than Qki Assume otherwise. Then, this implies that the total
work remaining in the system has not increased. But this can not be the case,
since there is at least one queue, namely at node k 1, that was idle for one time
step (immediately after the last packet destined for k 1 reached its destination)
during phase k. Since n units of work are added at each time step, the only way
the workload does not go up is if every queue remains nonidle in every time step
in phase k. This concludes the proof for the bound M.
In order to show that there is (one) adversary that defeats every bound M,
simply keep changing the goal of the adversary so that after it defeats a given M,
it resets all queues to be empty (by not doing any injections) and then proceeds
to defeat M + 1, etc.
3.2.2 Stability of FTG
FTG protocol is stable for the ring in contrast to the LIS and FIFO instability
result for a deterministic adversary at injection rate 1.
12
First define a quantity A(i, j, t) for 0 < i, j < n 1. All arithmetic on node
names is mod n. The quantity A(i, j, t) denotes the number of packets at time t
in the queues in nodes i,i + 1,j (inclusive) which need to cross the edge from
node i 1 to node i. We assume that this quantity is measured at the end of time
step t (i.e., at time step t, packets are inserted, then moved, after which the value
of A is determined). Let A be a deterministic (w,p) adversary with p = 1. We
next define an appropriate potential function <&(, t) = max{<&i(i, t),w + n 1},
where <&i(i,t) = max{A(i, k, t) + (i + n 1 k) i < k < i + n 1}. The crux of
the argument is the following lemma:
Lemma 3.2.1 Let Abe a (w, p) adversary with p=l. Then for all t > 0, (i, t+
w) <
Proof: Clearly the only way A(i, j, t) can increase is due to the insertion of
packets and can only go up by one per insertion of a packet that needs to cross edge
(i 1, i). (Note that by assuming simple paths any packet entering the queue at
node i from the queue at i 1 will not need to traverse the edge (i 1, i) again, and
thus is not counted in A(i, j,t).) Thus, after the w time steps t + l,t + 2,...,t + w,
no A(i, j, t) can increase by more than w and hence (i, t) will increase by at most
w due to all the packet insertions during these steps.
Theorem 3.2.2 Let G denote the nnode cycle and Y the class of rate 1 de
terministic adversaries (say with window size w). Define Qa(G) to be the total
number of packets initially in the network (i.e., the sum of all edge queue sizes)
and let Qq = max{Qo(G),w}. Then (G, Y, FTG) is stable and furthermore there
are never more than n(Q0 1) + vj packets in the system.
Proof: For all k, A(i, k, 0) < Qo, and so 0) = max{A(i,k,0) + (i + n
1 k) : i < k < i + n 1} is at most Qo+i + n 1 i = Qo + n 1, since the
(i + n 1 k) term is maximized with k i. Also, w + n 1 < Q0 + n 1, by
definition of Q0. Thus, i(i, 0), w + n 1) < Qq + n 1.
Consider any time t = mw for m a nonnegative integer. By Lemma 3.2.1, we
have 4>(i, mw) < f(i, 0) < Q0+n1. Hence A(i, i1, mw) + (i+nl (i1)) =
A(i, i 1, mw) + n < tf>(i, mw) < Q0 + n l. Subtracting n from both sides we
get A(i,i l,mw) < Q0 l.
13
The total number of packets in the system at time t = mw can then be upper
bounded by ^(M1> mw), which will be no greater than n(Q0 1). Finally,
for any time t with mw < t < (m + 1 )w, we have A{i,i 1 ,t) < w
14
+
4. Universal stability results of networks and protocols
Universal stability of various networks and protocols are considered when rate
is < 1. For all the results here an all interval adversary is used. For further details
on any of these please refer to [2]
4.1 Universal stability of networks
Here are some of the universal stability results for ring.
4.1.1 Universal stability of ring
Any greedy queuing protocol V is stable against any adversary A of rate (b, 1
e) for a nnode ring G.
Proof: The proof is by contradiction. A queue Q' for any edge e is fixed. Sup
pose there is a set S of Q' + 1 packets in the system at some time, all requiring
an edge e. Since there are no more than Q' packets requiring an edge e a contra
diction is obtained by proving that in the time interval between the injection of
first and last packets of S, one of the packets of S must have crossed edge e before
the last packet in S was injected.
Consider some packet p in the system (G, A, V) injected at step T0, at node vio.
Let packet p be destined for node n. Let T, > T0 be some time at which packet
p has not been absorbed. Let V{0, vio+s be the nodes through which p passes in
the interval [To, T,\. Let the edges be represented by ik and let ik = io + k. For
k = 0, ...s, let T). be the time at which p arrives at node Vik for the first time. This
also means that the packet p crosses the edge io + k 1, if k > O.Let Ts+i T'.
Lemma 4.1.1 For each k = 0, ...s, and each t E (Tk,Tk+1], some packet crosses
edge ik in step t.
Proof: The packet p crosses ik in step Tk+1, for 0 < k < s 1. At step
Tf = Ts+i p or some other packet crosses is. packet p waits at the tail of ik for
15
every t E (Tk,Tk+i\ Since the protocol is greedy some other packet crosses edge
%k in these time steps.
Let Pj>t be the number of packets at the end of step t that require edge j.
Lemma 4.1.2
Let t' < t. Then we have
Pj,t < Pj,v + (i c)(t t' + b z
z is the total number of packets that cross edge j in the interval (t',t\. Now
define Q as follows
Q maXjeG,te{To,T'}Pj,t
Now define the function f as f(j,T0) = Q + (b + l)(j io) and f(j,t) =
Q e(t T0) + (b + 1)(1 + j i0), for t > T0. f has the following properties
Lemma 4.1.3
1 /C/> t) = f{j, T0) e(Â£ T0) + b + 1, for t > T0.
2 f(j, t) = f{j, if e(t If), for t > if > T0
3. f{j + l,t) = f{j,t) + b + 1
Definition 1 The pair (j, t) is applicable if either
1. j = ik, forsomekandt E [To,Tfe+i], or
2. j > isandt E [T0,T']
Lemma 4.1.4 If (j,t) is applicable and (j 1 ,t) is not then j ik for some k
and t E (Tk, Tk+1]
Lemma 4.1.5 For all applicable pairs (j,t) we have Pjjt < f{j,t).
16
Proof: The proof is by induction on j > i0 and by induction on t for fixed j.
Proof for fixed j: If (j, t0 is applicable, then f(j, to > Q. By assumption we
have Pj;t < Q, for all t Â£ (To, 7}].
Consider any applicable pair (j,t) with t > T0. A packet has crossed edge j in
the consecutive steps between t and T0. Then by Lemmas 2 and 3 and induction
hypothesis we will have
Pj,t < Pj,T0 + (l e)(t T0)+ b (t T0)
= PjTo   T0) + 6
< f(j, t)
Otherwise there is some step tl Â£ (T0, t] in which no packet crosses edge j. Take
the most recent such step preceding t. The pair (j, t1) is applicable. Then the pair
j 1 ,t') is also applicable by Lemma 5 and 1. And so is the pair j 1 ,t' 1).
The queue Vj is empty at the end of step t! 1. Hence we have > Pj,t>1
Now apply Lemmas 2 and 3 and the induction hypothesis and we have
Pj,t 5: Pj,t'i + (1 c) (t t' + 1) + b (t t')
Pji,t'\ + b + 1 e(t t' + 1)
5: f(j ~ 1) t' 1) + b + 1 e(t t' + 1)
= f{3,t'l)e{tt' + l)
Proof: Proof of the two main results :
Theorem 4.1.1 (G, A, V) is stable, and there are never more than (b + 1 )n/e
packets in the system that require any given edge.
Set Q' = (6 + l)n/e.Suppose the theorem is not true. Let T' be the first time that
there are Q' +1 packets in the system that requires an edge n. Let To be the time
17
at which the first of these packets were injected. Q < Q'. In interval [T0, T'\ at
most
{T' To + 1)(1 e) + b
packets requiring any edge can be injected. So we have
Q' < (T' T0 + 1)(1 e) + b
Hence we have
T' T0 >  1 > Q'
1 e
By assumption we have Q' < Pn,T' and by Lemma 6 we have Pn,T' < /(n, T').
But T'T0> Q'.
So we have
Q' ^ /(^j T') Q ~ e(T7 To) + (b + 1)(1 + n io) < Q' eQ1 + (b + 1 )n Q1,
which is a contradiction.
Theorem 4.1.2 The maximum number of steps that a packet spends in the sys
tem before it gets absorbed is 0{bne~2).
Proof: Let a packet p be injected at time T0. Let the origin be io and let the
destination of packet p be n. Let T' be a time when packet p is still in the system
and so is not absorbed yet. Let T' = To + (6+l)ri(e1 + e~2). Then by the previous
theorem and Lemma 6 we will have Q (b + l)n/e So we have
Pn,T' < f(n,T')
= Q e{T' Tq) + (b + 1)(1 + n io)
= e~l{b + 1 )n e(b + l)u(e_1 + e2) + (b + 1)(1 + n i0)
<0
18
which is a contradiction.
4.2 Universal stability of protocols
A protocol V is universally stable if it is stable against every adversary of rate
less than 1, on every network.
The results on universal stability are from paper [2]. Four of the natural
protocols that are universally stable are FTG, NTS, LIS and SIS. But FTG, NTS
and SIS can require queues and delays of exponential size in the worst case. The
greedy protocols that are universally unstable are FIFO, LIFO, NTG and FFS.
Here is a table which shows the protocols that are universally stable and unstable.
Table 4.1: Universal stability of greedy protocols
Protocol Universally stable?
FirstInFirstOut (FIFO) NO
LastInFirstOut (LIFO) NO
NearestToGo (NTG) NO
FarthestFromSource (FFS) NO
FarthestToGo (FTG) YES
NearestToSource (NTS) YES
LoiigestInSystem (LIS) YES
ShortestInSystem (SIS) YES
4.2.1 Universal stability of SIS
ShortestinSystem (SIS) is a protocol, which at every queue gives priority to
the packet that was injected most recently. SIS is universally stable. Let G be a
directed network and A some bounded adversary of rate (6, 1 e), with e > 0.
The proof first includes the following two lemmas.
Lemma 4.2.1 Let p be a packet waiting at edge e at time t. Suppose there are
k 1 other packets in the system requiring e that have priority over p. Then p
will cross e in the next (k + b)/e steps.
Proof: Assume p does not cross e in the next (k + b)/s steps. Then some other
distinct package crosses the edge e in the (k + b) je steps. But any packet that
crosses the edge e must be either one of these two that has priority over p
19
1. One of the k 1 packets existing at time t.
2. One of the (at most) (1 e)(k + b)/e + b packets requiring e that were
injected during this time.
So the total number of packets that have priority over p during this time is
(k 1) + (1 e)(k + b)/e + b = (k + b)/e 1 < (k + b)/e, which is a
contradiction.
Now define the numbers k\, k2... by the recurrence ki = b, kj+1 = .
Lemma 4.2.2 When a packet p arrives at the queue of the jth edge Cj on its path
there are at most kj 1 packets requiring any edge e in the path of p with priority
over p.
Proof: The proof is by induction as follows.
The claim holds for j = 1: For any edge e, the only packets that could have
priority over p are the other 6 1 packets (at most) that injected along with p.
Assume the claim holds for some j: By the above lemma, p will arrive at the
tail of ej+i in at most another (kj + b)/e steps, during which time at most another
(1 e)(kj + b)/e + b packets requiring any edge e with priority over p arrive. So
when p arrives at the tail of e^+i, at most
kj
e)(fcj + b) + b
e
kj+i
1
packets requiring edge e that have priority over p. Hence the claim holds.
Theorem 4.2.1 The system (G, A, SIS) is stable, no queue ever contains more
than kd packets, and no packet spends more than (db + Yli=i ki)/Â£ steps in the
system, where d is the length of the longest simple directed path in G.
Proof: First assume there are k^ + 1 packets at some point all requiring the
same edge. Then one of those with the lowest priority contradicts the claim of the
above lemma.
20
Combining both the lemmas above, a packet p takes at most (fcj + b)/e steps to
cross the jth edge in its path, once it is in queue for this edge. The delay bound
follows.
4.3 Upper bounds on queue size and end to end delay of greedy
protocols
Here is a table that shows the upper bounds on queue sizes and end to end
delay for greedy protocols that are universally stable. The details and the proof
can be found in paper [2].
Table 4.2: Upper bounds on queue size and end to end delay for some greedy
protocols
Protocol Queue size Delay
FarthestToGo (FTG) Oibm^/e) 0(bmd~l/e)
NearestToSource (NTS) 0{bmd~1 / e) 0{bmd~l /1)
LongestInSystem (LIS) 0(b/ed) 0(db/ed)
ShortestInSystem (SIS) 0(b/ed) 0(b/ed)
21
5. Other results in Adversarial queuing theory
Some of the other questions in an adversarial model have been explored in
papers [5], [4] and [1]. In paper [5] the results include universal stability of directed
graphs. In paper [4] universal stability of undirected graphs has been proved. One
of the interesting results in this paper is the universal stability of a connected
undirected graph if and only if it has at most two edges.
In paper [4] adaptive routing is also considered. In an adaptive routing the
path that is taken by the packet from the source to the destination is not fixed at
the time of injection. For adaptive adversarial queuing networks the load condition
has been formulated differently. A stable policy has been constructed whenever
this load condition is met.
22
6. Conclusion
We reviewed adversarial queuing in packet routing for communication net
works. An adversarial model seems to be more attractive than a stochastic one,
since the injection rates are deterministic and there are no probabilistic assump
tions. We reviewed several stability and universal stability results for various
networks and contentionresolution protocols in an adversarial setting. Here is a
summary of some of the results.
Stability results:
1. DAG is stable for any contentionresolution protocol and an adversary of
rate < 1."
2. Ring Here are some of the protocols that are stable and unstable for a ring
and an adversary of rate < 1.
(a) Stable protocol FTG.
(b) Unstable protocols LIS and FIFO.
Universal stability results:
1. Ring is stable for any contentionresolution protocol and an adversary of
rate < 1.
2. Protocols that are stable for any network and an adversary of rate < 1.
(a) FTG
(b) LIS
(c) NTS
(d) SIS
3. Protocols that are unstable for any network and an adversary of rate < 1.
23
(a) FIFO
(b) LIFO
(c) NTF
(d) FFS
Open questions: Here are some of the open questions.
1. In our review of protocols FIFO, LIFO, NTF and FFS, we have seen that
they are unstable for rate < 1. But does any or all of these become polyno
mially bounded when the injection rate is made small enough?
2. The universal stability results reviewed have exponential bounds. Is there a
protocol with polynomiallybounded queues and endtoend delays?
3. Most of the results we have reviewed are for nonadaptive routing, where the
path that is traversed by a packet is fixed. In adaptive routing an adversary
does not specify the path. The scheduler is free to choose the path it routes
a packet. What are all the stability results in adaptive routing?
24
REFERENCES
[1] William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, Adi Rosen: Dynamic
routing on networks with fixedsize buffers, Symposium on Discrete Algo
rithms 2003, 771780.
[2] Matthew Andrews, Baruch Awerbuch, Antonio Fernandez, Frank Thomson
Leighton, Zhiyong Liu, Jon M. Kleinberg, Universalstability results and per
formance bounds for greedy contentionresolution protocols, Journal of the
ACM, 48(2001) 3969. (2001).
[3] Allan Borodin, Jon M. Kleinberg, Prabhakar Raghavan, Madhu Sudan, David
P. Williamson: Adversarial queuing theory, Journal of the ACM, 48(2001) 13
38.
[4] David Gamarnik, Stability of Adaptive and Nonadaptive Packet Routing
Policies in Adversarial Queueing Networks, SIAM Journal on Computing,
32(2003): 371385.
[5] Ashish Goel, Stability of Networks and Protocols in the Adversarial Queueing
Model for Packet Routing, Networks, 37(2001) 219224.
25
