Distributed scheduling policies in networks of
input-queued packet switches
Claus Bauer, Dolby Laboratories, San Francisco, CA
cb@dolby.com
Abstract— Scheduling algorithms for input-queued packet
switches have been widely researched. It has been shownthat various classes of scheduling algorithms provide guarantees on stability and on average delay for single switches.
However, recent research has demonstrated that most ofthese scheduling algorithms do not guarantee stability for
networks of switches.
Most of the research that treats networks of switches proposes switching policies that require coordination among thesingle switches. The problem to find distributed schedulingpolicies that guarantee the stability of a network of switches
has so far only been investigated for a policy based on acomputationally very complex maximum weight matchingalgorithm.
In this paper, we investigate distributed scheduling algorithms of low complexity that belong to the classes of maximal
weight matching algorithms, p-maximal weight matching algorithms for switch architectures based on a space-divisionmultiplexing extension, and MNCM algorithms. For thesescheduling algorithms, we prove the stability of networks of
input-queued switches where all switches deploy the samescheduling policy. We also show that networks of inputqueued switches in which specific classes of different switching policies are deployed simultaneously at different switches
are stable.

I. Introduction and Motivation
The increase in internet traffic and the progress in opticaltransmission technologies create a need for fast switching
technologies in the internet core. Research on switch architectures and scheduling algorithms has mostly focusedon input-queued (IQ) and combined input output-queued(CIOQ) switches. A typical CIOQ switch is shown in figure 1. To avoid head-of-line blocking, a typical N xN CIOQ
switch has N virtual output queues V OQi,j , 1 ≤ j ≤ N
at each input i. Packets that arrive at input i and are destined for output j and not forwarded immediately upon
their arrival, are buffered in V OQi,j . The switching core
works with a speedup of S, S ≥ 1, i.e., it works at a speed
S times faster than the speed of the input and the output
links. If S > 1, packets are also buffered at the outputs.
The switching core is typically modeled as a crossbar, suchthat not more than one packet can be sent simultaneously
from the same input or to the same output.
The choice of the scheduling algorithm is a major design criteria for switches. The problem of finding an optimal switch configuration for a specific switch state canbe modeled as the problem of finding a maximum weightmatching of a bipartite N × N graph. In [12] and [14], it
has been shown that for a speedup of S = 1, a maximum
weight matching algorithm can guarantee the stability ofa single switch if the weights are chosen proportionally tothe lengths of the VOQs. However, the implementation
ACM SIGCOMM Computer Communications Review

83

VOQ1,1

Switching core

Output 1

Input 1

VOQ1,N

VOQN,1

Output N

Input N

VOQN,N

Fig. 1. Architecture of an input-queued switchof maximum weight algorithms is impractical as they require the solution of an optimization problem that is basedon the Hungarian method and has a known complexity ofO(N 3 ) (see [17]).
Therefore, various kinds of computationally less complex
scheduling algorithms have been investigated. In particular, the class of maximal weight matching algorithms has
been widely investigated ([6], [10], [11], [15]). It has beenshown in [7] that under the assumption of admissible traffic,
every maximal weight matching algorithm deployed with aspeedup of 2 guarantees the stability of the switch. In an
improvement on the work in [7], it was shown in [4] and [5]that a switch that deploys any maximal weight matchingalgorithm is stable even with a speedup S that is slightly
smaller than 2.
However, in view of the steady increase in optical transmission speed, even a moderate speedup of 2 or less - asrequired for the stability of maximal weight matching algorithms - becomes increasingly difficult to implement. To
overcome this difficulty, in [18], a CIOQ switch with aspace-division multiplexing expansion has been proposed.
In contrast to the crossbar model of a switch that assumes
the existence of only one connection between each input
and output pair, this model allows more than one connection per input - output pair. It is shown in [18] that aswitch that provides two connections between each input
and output pair and deploys a 2-maximal weight matching algorithm with a speedup of S = 1 guarantees 100%
throughput of the switch.
In [16], a new class of maximal weight matching algorithms called the class of maximum node containing matching (MNCM) algorithms, is introduced. It is shown inVolume 34, Number 3: July 2004

[16] that MNCM algorithms provide 100% throughput fora switch with a speedup of S = 1. The gain in speedup
compared to the traditional maximal weight matching algorithms discussed above comes at the cost of a higher
computational complexity. Whereas traditional maximal
weight matching algorithms have a complexity of O(N 2 ),the MNCM algorithms are based on the solution of a maximum size problem which has a complexity of O(N 2.5 ).
It was shown in [3] that in a specific network of inputqueued switches that is not overloaded, a maximum weightmatching policy as defined in [12] that is implemented independently at each switch does not guarantee stability. The
authors give a specific example where under non-overloaded
conditions the number of packets buffered at specific V OQs
at some switches in the network grows unlimited. This result showed that the previous work on maximum weightmatching algorithms in isolated switches is of limited practical value in networks of switches. Following the ideas in[3], it can also be shown that networks of switches that deploy maximal weight matching, p-maximal weight matching and MNCM algorithms can become instable in nonoverloaded networks.
In [1] and [3], switching policies that guarantee the stability of all switches within a network, but require coordination and cooperation among the switches within the
network, are presented. In [3], the LIN policy is proposed,
which assumes that all switches in the network always know
the actual traffic patterns all other switches. In [1], a stable
scheduling policy that requires the exchange of state information only among adjacent switches is illustrated. Bothpolicies require signaling traffic for the communication between the switches.
In [2], for the first time a distributed switching policy was
proposed that guarantees 100% throughput in a network of
input-queued switches. Each switch makes its schedulingdecision independently of the other switches and no additional signaling traffic between the switches is required.
The scheduling algorithm is a maximum weight matchingalgorithm with specific weights.
Due to the impracticality of maximum weight matchingalgorithms described above, it is of interest to understand
if distributed scheduling algorithms of low complexity thatguarantee 100% throughput in a network of input-queued
switches exist. This paper shows for the first time the existence of distributed switching policies of low complexitythat are based on maximal weight matching algorithms,
p-maximal weight matching algorithms and MNCM algorithms and that guarantee 100% throughput when all
switches in the network deploy the same switching policy. In addition, we prove that a network of input-queued
switches where each switch deploys any of these policies
or a maximum weight matching policy as proposed in [2],also guarantees a 100% throughput. We use the theory of
the Lyapunov function ([12], [9], [14]) and the fluid model
methodologies ([7], [8]) to establish our results. Our proofs
make use of new equations that describe the behavior of
maximal weight matching and p-maximal weight matchingalgorithms.
ACM SIGCOMM Computer Communications Review

84

The rest of the paper is organized as follows. Section II introduces the terminology to model networks ofqueues and networks of switches. In section III, we define
three types of scheduling policies and develop mathematical models to describe their behavior. For each policy,
we present stability results for networks of input-queued
switches. Finally, we show the stability of networks where
different policies are deployed simultaneously at different
switches. The proofs of the theorems are given in the appendix. We conclude in section IV.
II. Terminology and Model
A. Model of a network of queues
In this section, we follow an approach in [2] to describe
our model of a queueing system. We assume a system
of J physical queues q̃ j , 1 ≤ j ≤ J of infinite capacity.
Each physical queue consists of one or more logical queues,
where each logical queue corresponds to a certain class ofcustomers within the physical queue. Whenever a packet
moves from one physical queue to another, it changes classand therefore also changes logical queue. We denote a logical queue by q k , 1 ≤ k ≤ K, where K ≥ J. A packet enters
the network via an edge switch, travels through a number of switches and leaves the network via another edge
switch. We define a function L(k) = j that defines thephysical queue q̃ j at which packets belonging to the logicalqueue q k are buffered. The inverse function L−1 (j) returns
the logical queues q k that belong to the physical queue q̃ j .
Throughout this paper, the time t is described via a discrete, slotted time model. Packets are supposed to be of
fixed size and a timeslot is the time needed by a packet toarrive completely at an input link.
We define a row vector Xn = (x1n , ..., xKn ), where the kth vector xkn represents the number of packets buffered in
the logical queue q k at the beginning of the n-th timeslot.
k
We define En = (e1n , ..., eKn ), where en equals the number ofkarrivals at the logical queue q in the n-th timeslot. Analok
gously, we define Dn = (d1n , ..., dKn ), where dn expresses theknumber of departed packets from q in the n-th timeslot.
We assume that packets arrive at a queue at the beginningof a timeslot and depart from a queue at the end of a timeslot. Thus, we can describe the dynamics of the system asfollows:
Xn+1 = Xn + En − Dn .

(1)

Packets that arrive at a logical queue q k either arrive fromoutside the system or are forwarded from a queue within
the system. Thus, we can write:
En = An + Tn ,(2)where An = (a1n , ..., aKn ) denotes the arrivals from outside
the system and Tn = (t1n , ..., tKn ) denotes the arrivals frominside the system.
We further define a routing matrix R = [ri,j ], 1 ≤ i, j ≤ K,
where ri,j is the fraction of customers that depart fromthe logical queue q i and are destined for the logical queue
q j . Assuming a deterministic routing policy, there holds,
Volume 34, Number 3: July 2004

ri,j ∈ {0, 1},PPri,j ≤ 1,

1≤i≤Ki

ri,j ≤ 1. We set ri,j 6= 0,

1≤j≤K

if q j follows q along the route. Noting that Tn = Dn R andwriting I for the identity diagonal matrix, we find from (1)and (2):
Xn+1 = Xn + An − Dn (I − R).

(3)

We assume that the external arrival processes are stationary and satisfy the Strong Law of Large Numbers. Thus,
n
P

lim

n→∞

Ai

i=1

n

=Λ

w.p.1,(4)

where E[An ] = Λ = (λ1 , .., λK ) , ∀n ≥ 11 .
We now calculate the average workload of the logicalqueues q k which we denote by W = (w1 , ..., wK ). The expected traffic arriving from outside the system is by definition equal to Λ. The traffic that arrives at the logical queues
after having passed through m previous queues inside the
network is by the definition of the routing matrix R equal
to ΛRm . Noting that (I − R)−1 = I + R + R2 + ..., we findthat the overall average workload at the logical queues q kdenoted as is given by W = Λ(I − R)−1 .
Finally, we give a stability criteria for a network of queues
as proposed in [2].
Definition 1: A system of queues is rate stable ifXnlimn−→∞ n1X(Ei − Di ) = 0=
limn−→∞ ni=0
n−1

w.p.1.

(j)

If we apply this norm to the average workload vector W,
then the expression ||W ||maxL denotes the maximum average workload over all physical queues q̃ j . The necessary
condition for rate stability can now be formalized as follows:||W ||maxL < 1.

(6)

In the sequel, we will say that a system of networks thatsatisfies condition (6) and is rate stable achieves 100%
throughput.
1 Throughout

In this section, we apply the terminology of the previous
section to a network of IQ/CIOQ switches. A network of
IQ/CIOQ switches can be conceived as a queueing system
as defined in the previous section where the virtual output
queues are considered as the physical queues (The conceptof virtual output queues is explained in the introduction ofthis article). In this model we neglect the output queuesof the switches because instability can only occur at the
V OQs (see [2]).
We say that packets that enter the network via the input
of a given switch and leave the network via the output of agiven switch belong to the same flow. Packets belonging to
the same flow travel through the same sequence of physicalqueues and are mapped to the same logical queues at eachphysical queue, i.e. a flow can be mapped biunivocally toa series of logical queues.
We assume that each logical queue behaves as a FIFO
queue and assume a per-flow scheduling scheme which ismore complex than a per-virtual output queue schedulingscheme. In sections III B - F, we prove the main resultsof this paper for per-flow scheduling schemes. In [2], it has
been shown how per flow scheduling schemes can be used
to design per-virtual output queue scheduling schemes.
The network consists of B switches and each switch has
Nb , 1 ≤ b ≤ B, inputs and outputs. If the total numberof flows in the system is T , we do not have more thanNb2 physical queues and T Nb2 logical queues at switch b.
We can model
the whole network of switches as a sysP
T Nb2 logical queues. For the sake of simtem of
1≤b≤B

A necessary condition for the rate stability of a system ofqueues is that the average number of packets that arrive at
any physical queue q̃ j during a timeslot is less than 1. Inorder to formalize this criteria, we introduce the following
norm for a vector Z ∈ RK :Definition 2: For a vector Z ∈ RK , Z = (z 1 , .., z K ),and the function L−1 (k) as defined in this subsection, we
set:


 X

zk .
(5)
||Z||maxL = max
j=1,..,J 

−1
k∈L

B. Model of a network of switches

plicity, we suppose that Nb = N, ∀b, 1 ≤ b ≤ B and set
K = T N 2 B. Finally, we define QI (b, i) as the set of indexes
corresponding to the logical queues at the i-th input of theb-switch. Analogously, QO (b, i) denotes the set of indexes
corresponding to the logical queues directed to the i-th output of the b-switch. We further note that logical queues aredefined per switch, per virtual-output queue and per flow.
Thus, the index k of any logical queue in the network canbe uniquely expressed as k = T N 2 b + T N i + T j + l, 0 ≤b < B, 0 ≤ i, j < N, 0 ≤ l < T. We use these definitions
to adapt the norm ||Z||maxL to a network of switches that
handle multiple flows at their inputs.
Definition 3: Given a vector Z ∈ RK , Z = {z k , k =T N 2 b + T N i + T j + l, 0 ≤ b < B, 0 ≤ i, j < N, 0 ≤ l < T,
the norm ||Z||IO is defined as follows:


 X

X
||Z||IO = max|z m | ,|z m | .
b=1,..,B 
i=1,..,Nm∈QI (b,i)

m∈QO (b,i)

Because we assume a deterministic routing policy, thenecessary condition for rate stability given in (6) can now
be written for a network of switches as follows:
Definition 4: For a network of IQ/CIOQ switches, a
traffic and routing pattern W is admissible if and only if:||W ||IO = ||Λ(I − R)−1 || < 1.

the paper, we abbreviate ”with probability 1” by”w.p.1”.

ACM SIGCOMM Computer Communications Review

85

(7)

Without further mentioning, in the rest of this paper, weVolume 34, Number 3: July 2004

will only consider traffic and routing patterns that satisfy
the condition (7).
III. Stable local scheduling policies
In this section, we introduce three different local scheduling policies that guarantee 100% throughput in a network of IQ/CIOQ switches. We will initially present eachscheduling policy in a non-distributed, centralized way, i.e.
we will describe the scheduling algorithms as if it was ineach timeslot executed by a central network server. The
server calculates the configuration of all switches in the network by taking into account the actual state of each switch
and then sends each switch its specific configuration. In
section F , we will show how the individual scheduling policies can be implemented in a distributed fashion, i.e., ineach timeslot, each switch calculates its own configuration
taking into account only its own state.
A. Weight function
All scheduling policies introduced in this paper are
matching policies. Any matching policy is defined relative to a specific weight. For the definition of the weights,
we will make use of a family of real positive functions
fk (x) : N → R, 1 ≤ k ≤ K, that satisfy the following
property:
lim

n→∞

k

1
fk (n)= kw
n

We define d (n) =P

w.p.1.

(8)dkm as the cumulative number ofm≤nkservices at queue q up to time n. Here, we assume thatall switches start service at the same time m = 0 and all
switches continuously work until time n. For a given positive constant C, we define the weight of the queue q k attime n as
φknk= n − fk (d (n)) + C.

(9)This choice of the weights is motivated by the fact that
it will allow us to derive the relation (36), which in turnimplies the rate stability (see definition 1) for the theorems
2, 4, 5 and 7 below. We set Φn = (φ1n , .., φKn ).
We see that for a fixed function f (·) that satisfies therelation (8), there exists a constant C > 0 such thatkkd∀n, n ≥ 0, there holds f (dn ) ≤ wnk − C. Further, because
the accumulative departure rate at each logical queue q kcannot be more than the accumulative arrival rate, therek≤ n. Combining these two estimates, weholds lim d w(n)kn→∞see that for any function f (·) that satisfies the condition(8), one can always find a C > 0 such that the weights φkn
are positive ∀n, n ≥ 0, ∀k, 1 ≤ k ≤ K. This fact is important in view of the theorems 1 - 5 below, which all require
the weights φkn to be strictly positive.
In [2], an example for fk (n) is given. The cumulative
function of external
q k is given
P k arrivals for the logical queuek −1kam . The inverse function [a ] (p) maps
by a (n) =the packet number p to the arrival slot. Setting C = 0 and
fk (p) = [ak ]−1 (p), the weight φkn = n − [ak ]−1 (p) denotes
the age of the p-th packet at time n. At its departure time
kn, the age of the p-th packet is n − [ak ]−1 (dn ).

B. Maximal weight matching algorithms
In this section, we propose a maximal weight matchingscheduling policy for a network of switches with a speedupof S > H.
For this purpose, we introduce some additional terminology. In this section, we call a timeslot as defined earlier anexternal timeslot defined as the time needed by a packet
to arrive completely at an incoming link. As the switching core works at a speedup S ≥ 1, an internal timeslot
is defined as the time needed to transfer a packet throughthe switching core from an input to an output. Thus, theexternal timeslot from time t to t + 1 consists of the S internal timeslots [t + (k − 1)/S, t + k/S], 1 ≤ k ≤ S. For
the sake of simplicity, we always assume that S is an integer. The proofs of the theorems in this paper can be easily
generalized for non-integer S. For any rational S, insteadof considering the dynamics of the switch over one external timeslot as done in the proofs related to this chapter,the dynamics of the switch over gS external timeslots suchthat gS is an integer would have to be considered. If S is
non-rational, all proofs in this paper hold by replacing S bya arbitrarily close, smaller rational number. We supposethat packets arrive at the beginning of an external timeslot t and are transferred instantly at the end of an internal
timeslot.
As the switching core is modeled as a crossbar, in every
internal timeslot at most one packet can be sent from thesame input or to the same output, i.e.
||Dn ||IO ≤ S,

∀n ≥ 1.

(10)

Further, for a given input i and a given output j at agiven switch b, we define the set of all logical queues thateither belong to the input i or that are directed to the
output j. We set ∀b, i, j, 1 ≤ b ≤ B, 1 ≤ i, j ≤ N,[
Sb,i,j := m : 1 ≤ m ≤ K, m ∈ QI (b, i) QO (b, j) .
For each set Sb,i,j , we sum the average arrival rates for all
logical queues that belong to Sb,i,j , and define the maximum of these summations as H :
X
wm .
(11)
H =
max
1≤b≤B
1≤i,j≤N m∈Sb,i,j

From (7), we see H < 2.
We now give a formal definition of a maximal weightmatching algorithm: For a set of positive weights P k , 1 ≤k ≤ K, where P k is the weight assigned to the logical queueq k , a maximal weight matching algorithm is defined as follows:m≤n

ACM SIGCOMM Computer Communications Review

86

Volume 34, Number 3: July 2004

1. Initially, all logical queues q k , 1 ≤ k ≤ K, are consideredpotential choices for a cell transfer.
2. The logical queue with the largest weight, say q k0 is
chosen for a cell transfer and ties are broken randomly. We
assume without loss of generality that k0 ∈ QI (b1 , i1 ) andk0 ∈ QO (b1 , j1 ).
3. All logical queues q k with k ∈ Sb1 ,i1 j1 are removed.
4. If all q k are removed, the algorithm terminates. Else go
to step 2.
We now develop an inequality that describes the dynamics of a maximal weight matching algorithm. This inequality will be used to prove the stability of a specificmaximal weight matching scheduling policy in theorem 2.
We define the weights of the algorithm as a function of
the actual timeslot n as follows: Pn = (Pn1 , ..., PnK ) are
the weights at the beginning of the n-th external timeslot.
kPn,s, 1 ≤ s ≤ S, is the weight of the logical queue q k at
the beginning of the s-th internal timeslot of the n-th external timeslot. Thus, Pn = Pn,1 , ∀ n ≥ 0. We also define
the departure vector of the s-th internal timeslot of then-th external timeslot as Dn,s = (d1n,s , ..., dKn,s ) such thatS
P
Dn,s , and
Dn =
s=1

weight, say Pnk2 with k2 ∈ Sb2 ,i2 ,j2 is chosen. Thus,X
Pnk2 H ≥ Pnk2
wmm∈Sb ,i ,j
2 2 2
m6∈Sb ,i ,j
1 1 1

(12)

∀n ≥ 1, ∀1 ≤ s ≤ S. Now, we establish a lower bound forthe weight of a matching calculated by a maximal weightmatching algorithm during an external timeslot. In particular, we show that the weight of a matching calculated
in an external timeslot is 1/H-times larger than the sumof the products of the average arrival rate wk of a logicalksummedqueue q k multiplied with the actual weight Pn,sover all logical queues and all internal timeslot of the considered external timeslot.
Theorem 1: For a network of IQ/CIOQ switches thatapplies a maximal weight matching algorithm for positive
weights P k > 0, 1 ≤ k ≤ K, and a speedup-up of S, there
holds for any timeslot n
1 XX k k XX k k
Pn,s w ≤Pn,s dn,s .
H s=1
s=1
S

K

K

k=1

k=1

S

Proof: We first analyze a maximal weight matching algorithm in the first internal timeslot. In its first iteration,
the algorithm selects the queue with the largest weight,
say Pnk1 with k1 ∈ Sb1 ,i1 ,j1 , for transfer. Thus, using thatP k > 0, we see from (11):
Pnk1 HX≥ Pnk1wmm∈Sb1 ,i1 ,j1≥X

Pnm wm .

m∈Sb1 ,i1 ,j1

All logical queues q k with k ∈ Sb1 ,i1 ,j1 are removed. In
the second iteration, the remaining queue with the largest
ACM SIGCOMM Computer Communications Review

87

Pnm wm .

(13)

m∈Sb ,i ,j
2 2 2
m6∈Sb ,i ,j
1 1 1

The matching algorithm stops after h, h ≤ BN iterations
when none or only empty queues remain. For each of theseh iterations, an inequality analogous to (13) holds. If any
empty queues remain, we hypothetically continue to run
the algorithm (BN − h) times and produce valid inequalities as in (13) where both sides are equal to zero. We
note that dkn = 1 only for the logical queues qk chosen fortransmission. Thus, summing over all BN inequalities, we
obtainBN
X

Pnkm =

m=1

BNX

Pnkm dkn =

m=1

K
X

1 X k kPn w . (14)HK

Pnk dkn ≥

k=1

k=1

Applying this analysis to all S internal timeslots, we obtainfrom (14)K
S X
X||Dn,s ||IO ≤ 1,X≥

1 XX k k
Pn,s w .
H s=1
S

k
Pn,s
dkn,s ≥

s=1 k=1K2

k=1

We state the next corollary as an immediate consequenceof theorem 1:
Corollary 1 For any input buffered switch that applies amaximal weight matching algorithm and a speedup-up of S,kk− Pn,s+1|≤
if there holds for a positive constant C1 , |Pn,s
C1 ∀k, n, s, 1 ≤ k ≤ K, n ≥ 1, 1 ≤ s ≤ S − 1, then there
holds for any timeslot n :



K
K
X
1
S(S − 1)
S X k
k
k k
.
KC1 1 +Pn (t)w ≤Pn d n +
H
2
H
k=1

k=1

Proof: The corollary is derived from theorem 1 by approxik
by Pnk - using the assumptions of the corolmating the Pn,slary - and applying the estimates |wk | < 1, |dkn | ≤ 1 which
follow from (7) and (12) respectively.
The assumption of corollary 1 that weights only change bya finite, bounded amount between two iterations of the algorithm is valid for most weight functions proposed in theliterature. In particular, it applies to the weight function
defined in (9).
We now state the main result of this section. The following theorem states the existence of a class of local scheduling policies that are based on a maximal weight matchingalgorithm using a speedup larger than H and that achieve
100% throughput in a network of IQ/CIOQ switches.
Theorem 2: A network of IQ/CIOQ switches that implements a maximal weight matching scheduling policy witha speedup of S > H in which the weight φkn of queue q k attime n is defined as in (9) and φkn > 0, achieves 100%
throughput.
Proof: The proof is given in the appendix.
Volume 34, Number 3: July 2004

C. p-maximal weight matching algorithms
The application of p-maximal weight matching algorithms to the problem of determining the configuration ofa packet switch was first described in [18]. In contrast to
earlier switch architectures that allow only one packet to
be sent from one input or to one output in each timeslot,in [18] a switch with a space-division multiplexing expansion is presented that deploys p, p ≥ 2 connections between
each input and output pair.
The scheduling problem is modeled as a p-matchingproblem on a bipartite graph whose nodes are the inputs
and outputs of a switch and the edges are the connections
between inputs and outputs. A p-matching is defined asa matching, such that no node of the matching is incident
with more than p nodes. Thus, for a p-maximal weightmatching algorithm the following relation holds:||Dn ||IO ≤ p.

|Pnk − Pnk,∗ | ≤ pC2 .

(15)

In this paper, we consider a specific p-maximal weightmatching algorithm that can be considered as a generalization of the maximal weight matching algorithm discussed in the previous section. The algorithm is executedat the beginning of each timeslot. During each execution, it
successively schedules up to pBN transmissions from thelogical queues at the inputs of the switches to the destination outputs. We introduce the additional variables
cr , 0 ≤ r ≤ 2N B, where r indexes all inputs and outputs
in the considered network and 2N B is the total number of
all inputs and outputs in the network. During the execution of the algorithm, if r indexes an input, the value ofthe variable cr expresses the actual number of times thata cell has been scheduled to be sent from the input r to
any output. If r indexes an output, cr equals the actual
number of times a cell has been scheduled to be sent to the
output r from any input. At the start of the algorithm, thevariables cr are initialized equal to zero and they can take
integer values between 0 and p.
We now define a p-maximal weight matching algorithm:
With regard to a set of positive weights P k , 1 ≤ k ≤ K,
where P k is the weight assigned to the logical queue q k , a
p-maximal weight matching algorithm is defined as follows:
1. Initially, all logical queues q k , 1 ≤ k ≤ K, are consideredpotential choices for a cell transfer. All cr , 1 ≤ r ≤ 2N B
are set equal to 0.
2. The logical queue with the largest weight, say q k0 is
chosen for a cell transfer and ties are broken randomly. We
assume without loss of generality that k0 ∈ QI (b1 , i1 ) andk0 ∈ QO (b1 , j1 ).
3. ci1 and cj1 are updated as ci1 = ci1 + 1 and cj1 = cj1 +1. If ci1 = p, all logical queues q k with k ∈ QI (b1 , i1 )are removed. If cj1 = p, all logical queues q k with k ∈QO (b1 , j1 ) are removed.
4. If all q k are removed, the algorithm terminates. Else go
to step 2.
The weights of the logical queues at the beginning of then-th timeslot have been defined as Pnk . After each iteration
ACM SIGCOMM Computer Communications Reviewof the algorithm, some weights are updated. We definePnk,∗ as the actual weight of the logical queue q k between
inclusively the first and the large iteration of the algorithm.
At the beginning of the first iteration we initialize Pnk,∗ =Pnk . As the weight of a queue q k is updated at most p times
during the execution of the p−maximal weight matchingalgorithm, the value of Pnk,∗ might change up to p times
during each execution of the algorithm.
In the sequel, we will only consider actual weights Pnk,∗
that do not change by more than a positive constant C2 ateach update during the execution of a p-th maximal weightalgorithm. This assumption can be justified in the same
way as the assumptions of corollary 1 in section III B. As
an actual weight Pnk is initialized as Pnk,∗ = Pnk and as it
is not updated more than p times during the execution of
the algorithm, there always holds ∀n ≥ 1, ∀k, 1 ≤ k ≤ K.

88

(16)

Similarly to theorem 1, we now prove a lower bound forthe weight of the matching calculated a p-maximal weightmatching algorithm:
Theorem 3: For a network of IQ/CIOQ switches where
each switch deploys p connections between each input andoutput pair and that applies a p-maximal weight matchingalgorithm, p ≥ 2 with speedup S = 1, with positive weights
P k > 0, 1 ≤ k ≤ K that satisfy the condition (16), there
holds for any timeslot n :


K
K
1
p X k k X k k
2.
Pn dn,s + p BN C2 1 +Pn w ≤
H
H
k=1

k=1

Proof: In its first iteration, the algorithm chooses the queuewith the largest actual weight, say Pnk1 ,∗ with k1 ∈ Sb1 ,i1 ,j1 ,for transfer. Thus, from (11):X
Pnk1 ,∗ H ≥ Pnk1 ,∗wmm∈Sb1 ,i1 ,j1

X≥Pnm,∗ wm .

(17)m∈Sb1 ,i1 ,j1

The weights ci1 and cj1 are updated. The second to thep − 1-th iteration of the algorithm are performed exactly as
the first iteration and allow us to derive inequalities as in(17). In the p-th iteration, after updating theW weights, alllogical queues q k , k ∈ Sb,i,j such that ci = p cj = p are removed. In the p + 1-th iteration, the remaining queue withk
the largest weight, say Pn p+1 with kp+1 ∈ Sbp+1 ,ip+1 ,jp+1 ischosen. Thus,
X
wm
Pnkp+1 ,∗ H ≥ Pnkp+1 ,∗
m∈Sb

X

≥

p+1 ,ip+1 ,jp+1
m6∈Sb,i,j s.t.
W
ci =p cj =pPnm,∗ wm .

(18)

m∈Sb

p+1 ,ip+1 ,jp+1
m6∈Sb,i,j s.t.
W
ci =p cj =p

The matching algorithm stops after h, h ≤ pBN iterations
when either none or only empty queues remain. For each
Volume 34, Number 3: July 2004

of the last h − p iterations, an inequality analogous to (18)
holds. For the eventually remaining empty queues, we hypothetically continue to run the algorithm (pBN −h) times
and produce valid inequalities as in (18) where both sides
are equal to zero. Summing over all BN inequalities of thetypes (17) and (18), we obtain:pBN
X

1 X km ,∗ kPw .
H m=1 nThe sumPruns over all logical queues at the switch bk→hthat belong to input h/are destined to output h . We set
X k
h
dn ,
(22)
Fn =
k→h

Ih

pBN

Pnkm ,∗ ≥

=

X

wk .

k→h

(19)

We define a family of real positive functions gh (x) : N →R, 1 ≤ h ≤ 2BN, that satisfy the following property:

Arguing as in the proof of corollary 1, we obtain from (7),(16), and (19):1
gh (n)
w.p.1.
(23)= hIn
For a given positive constant G, we define the weight of theport h at time n as:

m=1

K
X


Pnk dkn + p2 BN C2

k=1

1
1+
H



p X k kPn w . 2
H
K

≥

k=1

Unh

Using theorem 3, we can show that a network of IQ/CIOQ
switches that implements a p-maximal weight matchingscheduling policy achieves 100% throughput:
Theorem 4: A network of IQ/CIOQ switches that implements a p-maximal weight matching scheduling policy,p ≥ 2 with a speedup S = 1, in which the weight φkn ofqueue q k at time n is defined as in (8) and φkn > 0, achieves
100% throughput.
Proof: The proof is given in the appendix.
D. MNCM algorithms
MNCM algorithms have been introduced in [16]. They
are based on maximum size matching algorithms that function on weight functions of the input and output ports
rather than on weights functions of the V OQs or the logical queues as the (p)- maximal weight matching algorithms
described in the two previous sections. An MNCM algorithm is defined as follows:
Definition 5: A maximal size matching algorithm belongs to the class of MNCM algorithms if and only ifeach computed matching contains all nodes with maximum
weight.
The existence of MNCM algorithms has been shown in[16]. An MNCM algorithm is executed without speedup
and allows only one simultaneous connection between an
input and and ouput, i.e.,||Dn ||IO ≤ 1.

lim

n→∞

(20)

In order to define a specific set of MNCM algorithms,
we introduce additional notation. By our assumption, thenetwork contains BN input and BN output ports. We
index all 2BN ports in the network with the index h, i.e.
1 ≤ h ≤ 2BN. In analogy to the definition of per linkweights in (8) and (9), we define per port weights Unh . Fora port h at switch b, we introduce the following notation:

N

 P P
if h is an input port,
X 
j=1 k∈Sb,h,j ,
=
(21)
N
P
P


k→h

, if h is an output port.
= n − g(F(h)(n)) + G.

(24)

We set Un = (Un1 , .., Un2BN ). Similar to the discussion of
the constant C (see (8)) in section III A, one can provethat for every function g(·) that satisfies the relation (23),one can always find a constant G, such that Unh > 0,∀h, 1 ≤ h ≤ H, ∀n, n ≥ 0. Now, we state the following
theorem:
Theorem 5: A network of IQ/CIOQ switches that implements an MNCM scheduling policy with a speedup of
S = 1, in which the weights Unh are chosen as in (24) and
Unh > 0, achieves 100% throughput.
Proof: The proof is given in the appendix.
E. Networks of IQ/CIOQ switches that deploy different
scheduling policies
In the three previous sections, three different schedulingpolicies for networks were presented. It was shown thatthey provide stability for a network of switches where all
switches implement the respective scheduling policy.
In [2], the following stability result for a scheduling policy that is based on a maximum matching algorithm has
been shown:
Theorem 6: A network of IQ/CIOQ switches that implements a maximum weight matching scheduling policy
with a speedup S = 1, in which the weight φkn of queue
q k at time n is defined as in (9), achieves 100% throughput.
In [2], theorem 6 is only proven for C = 0. The proof
can be easily generalized to the case C ≥ 0. This policy issubject to constraint (20).
Following the argument in the previous section, it canbe shown that a maximum weight matching policy can also
be implemented in a distributed manner. It can now be
asked if a network of switches in which each switch deploys
any of the four scheduling policies stated in theorems 2, 4,
5 and 6 achieves 100% throughput. The answer is affirmative:
Theorem 7 A network of IQ/CIOQ switches where
each switch deploys any of the policies defined in theorems
2, 4, 5 and 6 achieves 100% throughput.
Proof: The proof is given in the appendix.

i=1 k∈Sb,i,h

ACM SIGCOMM Computer Communications Review

89

Volume 34, Number 3: July 2004

References

F. Distributed implementation of the scheduling algorithms[1]

In the sections B - E, we presented three centralized
scheduling algorithms for a network of switches. Now, we
explain how those three scheduling algorithms can be implemented in a distributed manner. In a centralized implementation, a switch algorithm cannot implement any arbitrary matching. Depending on the scheduling algorithm,
in each timeslot only a limited number of packets can besent to each input and from each output. These limitations
are expressed by the relations (10), (15) and (20) respectively. These relations prohibit specific configurations at
individual switches. However, scheduling decisions taken
at different switches do not constrain each other.
Further, for a maximal weight matching algorithm wesee by its definition in section B, that when - in step 2 a queue q k0 at switch b is chosen, then - in step 3 - only
queues that also belong to switch b are removed. Thus, amaximal weight matching algorithms can be implemented
in a distributed manner in the following way: The set of
logical queues q k is split in subsets Sb where Sb contains
the queues that belong to the physical queues of the switch
b. Each switch b executes the maximal weight matching algorithm on the set of logical queues that belong to Sb . The
same argument holds for a p-maximal weight matching algorithm.
For an MNCM algorithm, we again divide the set of all
logical queues in subsets Sb and each switch b executes
the MNCM algorithm on the set of logical queues that belong to Sb . Whereas a centralized implementation guarantees that a matching contains all ports with maximum
weight throughout the networks, a distributed implementation guarantees that at each switch all ports with maximum weights are contained in a matching. Obviously, a
distributed implementation will satisfy the requirements ofa centralized implementation as it selects all ports throughout the network with maximum weight. Thus, the proofof theorem 5 in the appendix is also valid for a distributed
implementation.
IV. Conclusions
This paper presents distributed scheduling policies oflow complexity for networks of input-queued switches. In
particular, it defines switching policies based on maximal
weight matching, p-maximal weight matching and MNCM
algorithms. It is shown that for specifc weights, a networkof switches that deploys any of these three switching policies guarantees 100% throughput under admissible traffic.
It is also proved that a network of input-queued switches
where each switch implements either any of these threeswitching policies or a maximum weight matching based
switching policy guarantees 100% throughput.
Acknowledgement The author thanks Dr.Vishal Sharma,
Metanoia, Inc., as well as the referees for their comments
and suggestions that helped to improve this paper.
ACM SIGCOMM Computer Communications Review

90

Ajmone, M.M.,Leonardi, E., Mellia, M., Neri, F., On thethroughput achievable by isolated and interconnected inputqueued switches under multicalss traffic, Proc. of Infocom 2002,
New York City, June 2002.
[2] Ajmone, M.M.,Giaccone, P., Leonardi, E., Neri, F., Local
scheduling policies in networks of packet switches with input
queues, Proc. of Infocom 2003, San Francisco, April 2003.
[3] Andrews, M., Zhang, L., Achieving stability in networks of input
queued, Proc. of Infocom 2001, Anchorage, Alaska, April 2001.
[4] Bauer, C., Packet scheduling in input-queued switches with aspeedup of less than two, Proc. of IEEE International Conference
on Networks, Sydney, Sept. 2003.
[5] Benson, K., Throughput of crossbar switches using maximal
matching algorithms, Proc. of IEEE ICC 2002, New York City.
[6] Charny, A., Krishna, P., et al., Algorithms for providing bandwidth and delay guarantees in input buffered crossbars withspeedup, Proc. of IWQoS, Napa, CA, 1998.
[7] Dai, J.G., Prabhakar, B., The throughput of data switches withand without speedup, Proc. of IEEE Infocom 2000, Tel Aviv.
[8] Dai, J.G., Stability of fluid and stochastic processing networks, Miscellanea publication n.9, Centre for Mathematical
Physics and Stochastic, Denmark (http://www.maphysto.dk),
Jan. 1999.
[9] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., Bounds on
average delay and queue size averages and variances in inputqueued cell-based switches, Proc. of IEEE Infocom 2001, Anchorage, Alaska.
[10] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., On the stability of input-buffered cell switches with speed-up, Proc. of IEEE
Infocom 2000, Tel Aviv, Israel.
[11] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., Stability of
maximal size matching scheduling in input queued cell switches,
Prof. of IEEE ICC 2000, New Orleans.
[12] McKeown, N., Mekkittikul, A., Anantharam, V., Walrand, J.,
Achieving 100% throughput in an input queued switch, IEEE
Transactions on Communications, vol. 47, no. 8, Aug. 1999, 1260
- 1272.
[13] McKeown, N., Mekkittikul, A., A practical scheduling algorithm
to achieve 100% throughput in input queued switches, Proc. ofIEEE Infocom 1998, San Francisco, March 1998.
[14] Shah, D., Kopikare, M., Delay bounds for approximate maximum weight matching algorithms for input queued switches,
Proc. of IEEE Infocom 2002, New York City, June 2002.
[15] Shah, D,; Stable Algorithms for input-queued switches, Proc.
39th Annual Allerton Conference on Communication, Control
and Computing, Oct. 2001.
[16] Tabatabaee, V., Tassiulas, L., MNCM a new class of efficientscheduling algorithms for input-buffered switches with no speedup, Proc. of Infocom 2003, San Francisco, April 2003.
[17] Tarjan, R.E.; Data structures and network algorithms. Society
for Industrial and Applied Mathematics, Philadelphia, PA, 1983.
[18] Yang, M., Zheng, S.Q., An efficient scheduling algorithm
for CIOQ switches with space-division multiplexing expansion,
Proc. of Infocom 2003, San Francisco, April 2003.

V. Appendix: Proof of theorems 2, 4, 5 and 7
A. The fluid methodology
The proofs of theorems 2,4 and 5 make use of the fluid
methodology as introduced in [7], [8]. We now recall an
extension of the fluid model to a network of switches from
[2] and refer the reader for further details to [2]. We defineΠ = {π} as the set of all possible network-wide matchings,
i.e. possible switch configurations throughout the network.
Using (3), we obtain the fluid equations of the system asfollows:
X(t)

=

D(t)

=

X(0) + Λt − D(t)(I − R),X
πTπ (t),

(25)
(26)

π∈Π

Volume 34, Number 3: July 2004

X

Tπ (t)

=

t,

(27)

π∈Π

where Tπ (t) is a non-decreasing function denoting the cumulative amount of time that the matching π has been used
up to time t. Also, noting that by (8) lim fk (t) → t/wk ,t→∞kand that d (t) → ∞ for t → ∞, we obtain1). Now (33) follows fromKC1 (1 + H
where K1 = S(S−1)2(29), (30), (31), (34), and (35):11dV (Φ(t)) = hΦ̇(t)Γ, Φ(t)i + hΦ(t)Γ, Φ̇(t)i
2
2
dt
−1
= hΦ̇(t)Γ, Φ(t)i = h[I − Ḋ(t)Γ ]Γ, Φ(t)iX
hπ1 Ṫπ1 (t), Φ(t)i= hW, Φ(t)i −π1 ∈kφk (t) → t −

d (t)
+ C.
wk

(28)

We denote the set of all switch configurations found attime t by maximal
Q weight matching algorithms as definedin theorem 2 as 1 (t). The fluid equations (6) and (7) canbe rewritten as:XḊ(t) =
π1 Ṫπ1 (t),
(29)
π1 ∈

X
π1 ∈

Q

Tπ1 (t)=Q= hW, Φ(t)i −

1 (t)

t.

(30)

1 (t)

We define Γ = [γ (i,j) ] as the diagonal matrix withγ
= wk , and let Γ−1 be the inverse of Γ. Taking thederivative on both sides of (28), we obtain:
(k,k)

1 (t)

π1 ∈

Q

Ṫπ1 (t)hπ1 , Φ(t)i

1 (t)


S
+ K1
≤ hW, Φ(t)i 1 −HhI, Φ(t)iS+ K1
min wk
≤
1−
1≤k≤K
K
H
k


B. Proof of theorem 2

Q

X

w >0

≤

hI, Φ(t)i
H −S
min wk
1≤k≤K
K
2H
k
w >0

< 0,
where the second to last inequality holds for hI, Φ(t)i >K0 > 0 if K0 is chosen sufficiently large. We see from (28)and (32):
k

0<t−

d (t)
+C
wk

≤ B.

(36)

w.p.1,(37)kΦ̇(t) = I − Ḋ(t)Γ−1 .

(31)

Writing the scalar product for two vectors v1 and v2 as
hv1 , v2 i = v1 v2T , we define the Lyapunov function:
V (Φ(t)) =

lim

t→∞

D(t)
t

= W,

C. Proof of theorem 4

We want to show that ∀t ≥ 0,
(32)

for a certain constant B > 0. Noting that V (Φ(0)) =hΦ(0)Γ, Φ(0)i ≥ 0, we see that ifd
V (Φ(t)) ≤ 0
dtt→∞

which corresponds to the rate stability condition of X(t). 2

1hΦ(t)Γ, Φ(t)i.
2

Φ(t) ≤ B,

This implies lim d t(t) = wk , i.e.,(33)∀t such that hI, Φ(t)i ≥ K0 for a fixed K0 > 0, then ∀t ≥ 0,
there holds V (Φ(t)) ≤ V (L0 ) := max V (L), which in
L∈RK ,
hI,Li≤K0

turn implies (32) for a certain B > 0. Thus we will show(33) in order to prove (32).
We note that for any t, there holds by the pigeonhole
principle:

We denote the set of all switch configurations found attime t by maximal
Q weight matching algorithms as definedin theorem 2 as 2 (t). Theorem 3 can now be expressed
as follows:phW, Φ(t)i ≤ hπ2 , Φ(t)i + K2 ,∀π2 ∈ Π2 (t), (38)H
1
. The proof of theorem 4 iswhere K2 = p2 BN C2 1 + H
identical to the proof of theorem 2 with the exception ofusing the relation (38) instead of the relation(35). TheQ
relations (29)
and
(30)
hold
with
π
and
(t)
substituted
1
1
Q
by π2 and 2 (t). 2

D. Proof of theorem 5
We first introduce some additional terminology. Set
X
Fnh =
dkn .
(39)
k→h

hI, Φ(t)i.
max φ (t) ≥
1≤k≤K
K
k

(34)

Finally, we express corollary 1 in the following way:S
hW, Φ(t)i ≤ hπ1 , Φ(t)i + K1 ,H∀h, 1 ≤ h ≤ 2N B. Based on (22) and (39), we use the fluid
methodology (see [7], [8]) to define the continuous functionhF h (t) and F (t) . By definition,h∀π1 ∈ Π1 (t),ACM SIGCOMM Computer Communications Review

(35)
91

d(F )t=t0
dt= F h (t0 ).

(40)

Volume 34, Number 3: July 2004

We assume that t0 ∈ i−interval:
df (U (t))= 2U̇ hqi (t0 )I hqi U hqi (t0 )
dt+
t=t0


F hqi (t0 )I hqi U hqi (t0 )= 2 1−
I hqi

Arguing analogously to (28), we obtainhU h (t) → t −

F (t)
+ G.
Ih

Thus, we derive from (40)hF h (t)F˙ (t).
=1−U̇ (t) = 1 −
Ih
Ih
h

(41)

Following an argument in [16], we introduce the functionf (U (t)) that plays as similar role as the Lyapunov function(see (32)) in the proofs of theorems 2 and 4. The functionf (U (t)) : R2BN → R is defined as:= I atf (U (t))
where at = arg

max

max

1≤h≤2BN(U h (t))2 ,h

U (t). As U (t) is differentiable

under the fluid model, f (U (t)) is continuous, but not necessarily differentiable. However, we can define the rightderivative of f (·) as follows:
df (U (t))
dt+

=

lim

δ→0+

f (U (t + δ)) − f (U (t))
.
δ

F (t)
t→∞
t

= 1,

= I h,∀h, 1 ≤ h ≤ H.

(46)

From (46), the stability condition as given in (37) folk

lows straight if we take into account that lim d t(t) ≤t→∞wk , ∀k, 1 ≤ k ≤ K, which follows from the fact that the accumulative departure rate at each logical queue q k cannot
be more than the accumulative arrival rate. 2
E. Proof of theorem 7

We note that if f (U (t)) = I h0 (U h0 (t))2 , there holds:
F h0 (t)The first and the second relation follow from (43) and (41)respectively. The third and fourth relations follow from(42) and (7) respectively. Arguing similarly as in (36) and(37), we derive from (44):limh1≤h≤2BN= 2(I hqi − 1)U hqi (t0 )
< 0.

(42)

This relation states that whenever a port h has the maximum weight, a cell is scheduled for transfer from/to the
input/output h. This follows from the definition of an
MNCM algorithm.
We discuss the properties of the function f (U (t)) as in[16]. For every t0 > 0, there is always a set of indices
Qt0 such that ∀h0 ∈ Qt0 , f (U (t0 )) = I h0 (U h0 (t))2 . Moreover, for every t0 > 0 there exists a δ > 0 such thatf (U (t)) = I h0 (U h0 (t))2 , ∀t ∈ [t0 , t0 + δ] and ∀h0 ∈ Qt0 .
We say that U (t) is represented by U h0 (t), h0 ∈ Qt0 , in theinterval [t0 , t0 +δ.] The time axis can always be partitioned
into disjoint intervals [0, ∆1 [, [∆1 , ∆1 + ∆2 [, .. such thateach interval is represented by a common index qi, i=1,2,.. .
If f (U (t)) is represented in the i-th interval by qi , then
df (U (t))= 2U̇ hqi (t)I hqi U hqi (t). (43)dt+t∈i−th int.

We divide the switches in the network into four groups
Gi , i ∈ {1, 2, 3, 4} where the groups G1 , G2 , G3 and G4
contain the switches that deploy the switching policy defined in theorems 2, 4, 5, and 6, respectively. Accordingly,
we can divide the departure vector D(t) and the arrival
rate vector W in four subvectors, i.e., we write D(t) =(D1 (t), D3 (t), D3 (t), D4 (t)) and W = (W1 , W3 , W3 , W4 ). In
order to prove the stability condition (37), it is sufficient
to show that ∀i ∈ {1, 2, 3, 4}
lim

t→∞

Di (t)t= Wi ,

w.p.1.

(47)

For each i ∈ {1, 2, 3, 4}, the relation (47) can be proved byapplying the proofs of theorems 2, 4, 5 and 6 to the corresponding group of switches Gi instead of applying them tothe whole network of switches. 2

Analogously to (32), we want to show thatU h (t) ≤ B1

(44)

for a certain B1 > 0 and ∀t, t ≥ 0, ∀h, 1 ≤ h ≤ H. In orderto prove (44), we show in analogy to (33) that
df (U (t))≤ 0, ∀t ≥ 0.
(45)
dt+
t=t0

The relation (45) implies f (U (t)) ≤pf (U (0)), ∀t, t ≥ 0,
which in turn implies (44) with B1 = f (U (0))/ min I h .
1≤h≤2BNI h >0

ACM SIGCOMM Computer Communications Review

92

Volume 34, Number 3: July 2004