Distributed scheduling policies of low complexity
for networks of input-queued switches
Claus Bauer
Dolby Laboratories, San Francisco, CA, 94103, USA,cb@dolby.com

Abstract. Scheduling algorithms for input-queued switches have been
widely researched. It has been shown that various classes of schedulingalgorithms guarantee the stability of single switches. However, recent
research has demonstrated that most of these scheduling algorithms do
not the guarantee stability for networks of switches. Most of the researchthat treats networks of switches proposes switching policies that require
coordination among switches. The problem to find distributed scheduling policies that guarantee the stability of a network of switches has so
far only been investigated for a policy based on a computationally very
complex maximum weight matching algorithm. In this paper, we investigate a class of distributed scheduling algorithms of low complexity thatare based on maximal weight matching algorithms. We prove the stability of networks of input-queued switches where each switch deploys any
maximal weight matching algorithm of the defined class.

1

Introduction and Motivation

The progress in optical transmission technologies creates a need for fast switching
technologies in the internet core. Research on switch architectures and scheduling algorithms has mostly focused on 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 andare destined for output j and not forwarded immediately upon their arrival, arebuffered 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 istypically modeled as a crossbar, such that 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
can be modeled as the problem of finding a maximum weight matching of a bipartite N × N graph. In [8] and [9], 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 to the lengths of the
VOQs. However, the implementation of maximum weight matching algorithms

is impractical as they require the solution of an optimization problem that isbased on the Hungarian method and has a known complexity of O(N 3 log N )(see [8]).
Therefore, the computationally less complex class of maximal weight matchVOQ1,1

Switching core
Output 1

Input 1

VOQ1,N

VOQN,1
Output N

Input N

VOQN,N

Fig. 1. Architecture of an input-queued switch

ing algorithms has been widely investigated ([7]). It has been shown that under
the assumption of admissible traffic, every maximal weight matching algorithm
deployed with a speedup of 2 ([6]) or even slightly less ([4],[5]) guarantees thestability of a single switch.
In [1] and [3], switching policies that guarantee the stability of all switcheswithin a network, but require coordination and cooperation among the switcheswithin the network, are presented. In [2], for the first time a distributed switchingpolicy was proposed that guarantees 100% throughput in a network of inputqueued switches. Each switch applies a maximum weight matching algorithm
to configure its scheduling matrix independently of the other switches and no
additional signaling traffic between the switches is required.
Due to the high computational complexity of maximum weight matching algorithms, it is of interest to understand if distributed scheduling algorithms oflow complexity that guarantee 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 complexity that are based on maximal weight matching algorithms and that guarantee 100% throughput. We use the theory of the
Lyapunov function ([8]) and the fluid model methodologies ([6]) to establish our
results. Our proofs make use of a new equation that describes the behavior of
maximal weight matching algorithms.
The rest of the paper is organized as follows. Section II introduces the terminology to model networks of queues and networks of switches. In section III,
we define maximal weight matching scheduling policies, develop a mathematicalmodel to describe their behavior and present stability results for networks of
input-queued switches. We conclude in section IV.

2

Terminology and Model

2.1

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 ca-

pacity. Each physical queue consists of one or more logical queues, where each
logical queue corresponds to a certain class of customers within the physicalqueue. Whenever a packet moves from one physical queue to another, it changes
class and 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 the physical queue q̃ j atwhich packets belonging to the logical queue 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 timemodel. Packets are supposed to be of fixed size and a timeslot is the time neededby a packet to arrive completely at an input link.
k
We define a row vector Xn = (x1n , ..., xKn ), where the k-th vector xn reprek
sents the number of packets buffered in the logical queue q at the beginningkof the n-th timeslot. We define En = (e1n , ..., eKn ), where en equals the numberkof arrivals at the logical queue q in the n-th timeslot. Analogously, we definekkDn = (d1n , ..., dKn ), where dn expresses the number 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 candescribe the dynamics of the system as follows:
Xn+1 = Xn + En − Dn .

(1)

Packets that arrive at a logical queue q k either arrive from outside the systemor 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 from inside the system.
We further define a routing matrix R = [ri,j ], 1 ≤ i, j ≤ K, where ri,j is thefraction of customers that depart from the logical queue q i and are destinedfor the logical P
queue q j . Assuming
a deterministic routing policy, there holds,
Pri,j ≤ 1. We set ri,j 6= 0, if q j follows q i alongri,j ≤ 1,
ri,j ∈ {0, 1},
1≤i≤K

1≤j≤K

the route. Noting that Tn = Dn R and writing I for the identity diagonal matrix,
we find from (1) and (??):
Xn+1 = Xn + An − Dn (I − R).

(3)

We assume that the external arrival processes are stationary and satisfy theStrong Law of Large Numbers. Thus,nPAi
lim i=1=Λw.p.1,(4)n→∞nwhere E[An ] = Λ = (λ1 , .., λK ) , ∀n ≥ 11 .
We now calculate the average workload of the logical queues q k which we
1

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

denote by W = (w1 , ..., wK ). The expected traffic arriving from outside thesystem 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 thedefinition of the routing matrix R equal to ΛRm . Noting that (I − R)−1 =I + R + R2 + ..., we find that the overall average workload at the logical queues
q k denoted 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 if
n−1
1X
Xn
= lim
(Ei − Di ) = 0
n−→∞ nn−→∞ ni=0

lim

w.p.1.

A necessary condition for the rate stability of a system of queues is that the
average number of packets that arrive at any physical queue q̃ j during a timeslot
is less than 1. In order 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

||Z||maxL = max(5)zk .
j=1,..,J 

−1
k∈L

(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 that satisfies condition (5)and is rate stable achieves 100% throughput.
2.2

Model of a network of switches

In this section, we apply the terminology of the previous section to a networkof IQ/CIOQ switches. A network of IQ/CIOQ switches can be conceived as aqueueing system as defined in the previous section where the virtual output
queues are considered as the physical queues (The concept of virtual output
queues is explained in the introduction of this article). In this model we neglect
the output queues of 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 a given 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 each physical queue, i.e. aflow can be mapped biunivocally to a series of logical queues.
We assume that each logical queue behaves as a FIFO queue and assume

a per-flow scheduling scheme which is more complex than a per-virtual output
queue scheduling scheme. In sections III B - F, we prove the main results of thispaper for per-flow scheduling schemes. In [2], it has been shown how per flowscheduling schemes can be used to design per-virtual output queue schedulingschemes.
The network consists of B switches and each switch has Nb , 1 ≤ b ≤ B,
inputs and outputs. If the total number of flows in the system is T , we do nothave more than Nb2 physical queues and T Nb2 logical queues
b. We canP at switch
model the whole network of switches as a system ofT Nb2 logical queues.
1≤b≤B

For the sake of simplicity, 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 the b-switch. Analogously, QO (b, i) denotes
the set of indexes corresponding to the logical queues directed to the i-th outputof the b-switch. We further note that logical queues are defined per switch, pervirtual-output queue and per flow. Thus, the index k of any logical queue in the
network can be 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 m | ,|z m | .
||Z||IO = max
b=1,..,B 
i=1,..,Nm∈QI (b,i)

m∈QO (b,i)

Because we assume a deterministic routing policy, the necessary condition
for rate stability given in (5) can now be written for a network of switches asfollows:
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.

(7)

Without further mentioning, in the rest of this paper, we will only consider
traffic and routing patterns that satisfy the condition (6).
2.3

Weight function

All scheduling policies introduced in this paper are matching policies with specific weights. The weights are defined using a family of real positive vector functions f (x) = {fk (x) : N → R, 1 ≤ k ≤ K, } that satisfy the following property:
lim

n→∞
k

We define d (n) =Pm≤n

fk (n)
1= knw

w.p.1.

(8)dkm as the cumulative number of services at queue q k up

to time n. For a given positive constant C, we define the weight of the queue q k

at time n askφkn (f ) := φkn = n − fk (d (n)) + C.

(9)

We set Φn (f ) := Φn = (φ1n , .., φKn ). We see that for a fixed function fk (·) thatsatisfies the relation (7), there exists a constant C > 0 such that ∀n, n ≥ 0, therekdkholds fk (dn ) ≤ wnk −C. Further, because the accumulative departure rate at each
logical queue q k cannot be more than the accumulative arrival rate, there holdsk≤ n. Combining these two estimates, we see that for any function
lim d w(n)kn→∞f (·) that satisfies the condition (7), one can always find a C > 0 such that theweights φkn are positive ∀n, n ≥ 0, ∀k, 1 ≤ k ≤ K. This fact is important for thetheorem 2 and 3 below, which all require the weights φkn to be strictly positive.
In [2], an example for fk (n) is given. The cumulative
P k function of externalarrivals for the logical queue q k is given by ak (n) =am . The inverse functionm≤n[ak ]−1 (p) maps 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 pth packet at time n. At its departure time n, the age of the p-th packet iskn − [ak ]−1 (dn ).
2.4

Maximal weight matching algorithms

In this section, we propose a maximal weight matching scheduling policy for a
network of switches with a speedup of S > H. We suppose that packets arriveat the beginning of an external timeslot t and are transferred instantly at theend of an internal timeslot. As the switching core is modeled as a crossbar, inevery internal timeslot at most one packet can be sent from the same 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 a given switch b, wedefine the set of all logical queues that either 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,no[
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 thatbelong to Sb,i,j , and define the maximum of these summations as H :X
H = max
wm .
(11)
1≤b≤B
1≤i,j≤N m∈Sb,i,j

From (6), we see H < 2. For a set of positive weights P k , 1 ≤ k ≤ K, where P k
is the weight assigned to the logical queue q k , we now formally define a maximal
weight matching algorithm as follows:1. Initially, all logical queues q k , 1 ≤ k ≤ K, are considered potential 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 thatk0 ∈ QI (b1 , i1 ) and k0 ∈ 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.
Now, we establish a lower bound for the weight of a matching calculated bya maximal weight matching algorithm. This bound will be used to prove thestability of a specific maximal weight matching scheduling policy in theorem 2.
We define Pn = (Pn1 , ..., PnK ) as the weight of logical queue q k at the beginningkof the n-th external timeslot and Pn,s
, 1 ≤ s ≤ S, as the weight of 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 timeslotSPof the n-th external timeslot as Dn,s = (d1n,s , ..., dK
Dn,s ,n,s ) such that Dn =s=1

and ∀n ≥ 1, ∀1 ≤ s ≤ S :||Dn,s ||IO ≤ 1.

(12)

Now, we show that the weight of a matching calculated in an external timeslot
is 1/H-times larger than the sum of the products of the average arrival rate wkksummed over allof a logical queue q k multiplied with the actual weight Pn,slogical queues and all internal timeslot of the considered external timeslot.
Theorem 1: For a network of IQ/CIOQ switches that applies 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
S

K

K

k=1

k=1

S

1 XX k k XX k k
Pn,s dn,s .
Pn,s w ≤H s=1
s=1
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. As P k > 0, we see from (10):X
X
Pnk1 H ≥ Pnk1
wm ≥Pnm wm .
m∈Sb1 ,i1 ,j1

m∈Sb1 ,i1 ,j1

All logical queues q k with k ∈ Sb1 ,i1 ,j1 are removed. In the second iteration, theremaining queue with the largest weight, say Pnk2 , k2 ∈ Sb2 ,i2 ,j2 is chosen. Thus,
X
X
Pnk2 H ≥ Pnk2
wm ≥Pnm wm .
(13)
m∈Sb ,i ,j
2 2 2
m6∈Sb ,i ,j
1 1 1m∈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 these h iterations, an inequality analogous to(12) holds. If any empty queues remain, we hypothetically continue to run thealgorithm (BN − h) times and produce valid inequalities as in (12) where bothsides are equal to zero. Summing over all BN inequalities, we obtain
BN
X
m=1

Pnkm =K
X

K

Pnk dkn ≥1 X k kPn w .
H

(14)

k=1

k=1

Applying this analysis to all S internal timeslots, we obtain from (13)
S X
K
X

S

k
Pn,s
dkn,s ≥

s=1 k=1K

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

¤

k=1

The next corollary can be derived from (6), (11) and theorem 1:
Corollary 1 If under the assumptions of theorem 1 there holds for a positivekkconstant C1 , |Pn,s− Pn,s+1| ≤ C1 1 ≤ k ≤ K, n ≥ 1, 1 ≤ s ≤ S − 1, then:
¶
µ
K
K
X
S(S − 1)
1
S X k
k
k k
Pn (t)w ≤Pn dn +
KC1 1 +
.
H
2
H
k=1

k=1

The assumption of corollary 1 that weights only change by a bounded amountbetween two iterations of the algorithm is valid for most weight functions proposed in the literature, and in particular for the weight function defined in (8).
The main results of this paper states the existence of maximal weight matching scheduling policies that guarantee 100% throughput of the network:
Theorem 2: A network of IQ/CIOQ switches that implements a single maximal weight matching scheduling policy with a speedup of S > H with the weights
Φn > 0 at time n defined as in (8), achieves 100% throughput.
Moreover, a network of switches in which individual switches deploy different
scheduling policies P m defined with regard to different weight functions Φn (f m )in (8), also achieves 100% throughput.
Theorem 3 Under the conditions of theorem 2, a network of IQ/CIOQ
switches where each switch deploys any policy P m achieves 100% throughput.
Remark: The condition (9) and the steps 2 and 3 of a maximal weight matchingalgorithm show that scheduling decisions taken at different switches are independent of each other. Thus, in a distributed implementation, each switch executes
the algorithm on the set of logical queues that belong to its physical queues.
2.5

Proofs of theorems 2 and 3

For the proof of theorem 2, we introduce the fluid methodology as applied in [6].
We denote the set of all switch configurations found
Q at time t by maximal weightmatching algorithms as defined in theorem 2 as 1 (t). Using (2), we obtain thefluid equations of the system as follows:
X(t) = X(0) + Λt − D(t)(I − R),

(15)

X

D(t) =

π1 ∈

X
π1 ∈

Q

Q

π1 Tπ1 (t),

(16)

1 (t)

Tπ1 (t) = t.

(17)

1 (t)

where Tπ1 (t) is a non-decreasing function denoting the cumulative amount oftime that the matching π1 has been used up to time t. Also, noting that by (7)klim fk (t) → t/wk , and that d (t) → ∞ for t → ∞, we obtaint→∞kφk (t) → t −

d (t)
+ C.
wk

(18)

We define Γ = [γ (i,j) ] as the diagonal matrix with γ (k,k) = wk , and let Γ −1
be the inverse of Γ. We see from (17):Φ̇(t) = I − Ḋ(t)Γ −1 .

(19)

Writing the scalar product for two vectors v1 and v2 as hv1 , v2 i = v1 v2T , we define
the Lyapunov function V (Φ(t)) = 21 hΦ(t)Γ, Φ(t)i. We want to show that ∀t ≥ 0,
Φ(t) ≤ B,(20)

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

(21)

∀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 turn implies (19) for a certain B > 0. For the
L∈RK ,
hI,Li≤K0

proof of (20), we note that for any t, there holds by the pigeonhole principle:
max φk (t) ≥1≤k≤KhI, Φ(t)i
.
K

(22)

Finally, we express corollary 1 in the following way:
S(S − 1)1ShW, Φ(t)i ≤ hπ1 , Φ(t)i + K1 , where K1 =
KC1 (1 + ),H2H
∀π1 ∈ Π1 (t). Now (20) follows from (15), (16), (18), (21), and (22):d11V (Φ(t)) = hΦ̇(t)Γ, Φ(t)i + hΦ(t)Γ, Φ̇(t)idt
22= hΦ̇(t)Γ, Φ(t)i = h[I − Ḋ(t)Γ −1 ]Γ, Φ(t)i
X= hW, Φ(t)i −hπ1 Ṫπ1 (t), Φ(t)i
π1 ∈= hW, Φ(t)i −

Q

1 (t)

X

π1 ∈

Q

1 (t)

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

(23)

µ
¶
µ
¶
S
S
hI, Φ(t)i+ K1 ≤ 1 −min wk+ K1≤ hW, Φ(t)i 1 −
1≤k≤K
H
H
K
k
w >0

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

where the second to last inequality holds for hI, Φ(t)i > K0 > 0 if K0 is chosenksufficiently large. We see from (17) and (19): 0 < t− dw(t)k +C ≤ B, which implies
lim

t→∞

D(t)
= W,
t

w.p.1,(24)

which corresponds to the rate stability condition of X(t). For the proof of theorem 3, we divide the switches in the network into M groups Gm , 1 ≤ m ≤ M,
where each group Gm contains the switches that deploy the switching policy P M
Accordingly, we can divide the departure vector D(t) and the arrival rate vector
W in M subvectors, Dm (t) and Wm . In order to prove the stability condition(23), it is sufficient to show that for each m lim Dm (t)/t = Wm , w.p.1. For eacht→∞m, this relation can be proved by applying the proof of theorem 2 to the group
Gm instead of applying it to the whole network of switches.

3

Conclusions

This paper investigates distributed scheduling policies of low complexity for
networks of input-queued switches. It defines a class of scheduling policies basedon maximal weight matching algorithms that guarantee the stability of networks
where all switches deploy the same scheduling policy. It is also shown that a
network where each switch deploys any policy out of the defined class of switchingpolicies is stable.

References
1. Ajmone, M.M.,Leonardi, E., Mellia, M., Neri, F., On the throughput achievable byisolated and interconnected input-queued switches under multicalss traffic, Proc. of
Infocom 2002, New York City, June 2002.
2. Ajmone, M.M.,Giaccone, P., Leonardi, E., Mellia, M., Neri, F., Local schedulingpolicies 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 a speedup of less thantwo, 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. Dai, J.G., Prabhakar, B., The throughput of data switches with and without speedup,
Proc. of IEEE Infocom 2000, Tel Aviv.

7. Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., Stability of maximal size matchingscheduling in input queued cell switches, Prof. of IEEE ICC 2000, New Orleans.
8. 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.
9. Shah, D., Kopikare, M., Delay bounds for approximate maximum weight matchingalgorithms for input queued switches, Proc. of IEEE Infocom 2002, New York City,
June 2002.