3
2 −Approximations to Maximum Weight Matching

Scheduling Algorithms for Networks of
Input-Queued Switches
Claus Bauer, Dolby Laboratories, San Francisco, USA, cb@dolby.com

Abstract— It is well known that maximum weight matching algorithms guarantee the stability of input-queued switches, but are
impractical due to their high computational complexity. In thispaper, we investigate the application of matching algorithms thatapproximate maximum weight matching algorithms to schedulingproblems. We show that while having a low computational
complexity, they guarantee the stability of input queued switches
when they are deployed with a moderate speedup.
Recent research has shown that scheduling algorithms thatstabilize individual switches do not necessarily guarantee thestability of networks of input-queued switches. We apply recent
results on networks of input-queued switches and show that theapproximation algorithms proposed in this paper stabilize both
single switches and networks of input-queued switches.
Finally, we show that the improve matching algorithm stabilizes networks of switches when it is deployed with a speedupof 32 + ².

VOQ1,1

Switching core
Output 1

Input 1

VOQ1,N

VOQN,1
Output N

Input N

VOQN,N

Fig. 1.

F ig.1 Architecture of an input queued switch

I. I NTRODUCTION
Most high-speed switches are based on a combined input
and output (CIOQ) queued architecture. As shown in figure 1,
at each input the arriving cells are buffered into N Virtual
Output Queues (V OQs) where each V OQ contains cells
destined to a specific output. The switching core itself ismodeled as a crossbar requiring that not more than one packet
can be sent simultaneously from the same input or to the same
output. The switching core works at a speed-up S ≥ 1, which
is defined as the ratio between the potentially higher speed of
the switching core and the line-speed of the incoming (andoutgoing) links.
The scheduling algorithm of a switch determines the stability and delay characteristics of the switch. McKeown [12]has shown that maximum weight matching (M W M ) basedscheduling algorithms that are deployed with a speedup of
S = 1 stabilize single input-queued switches when the weights
are chosen proportional to the V OQ lengths. Due to thehigh complexity of O(N 3 ) of M W M algorithms, researchers
have investigated less complex scheduling algorithms withperformance characteristics similar to those of the M W M
algorithm. It has been shown in [3], [6] that maximal weightmatching algorithms stabilize a CIOQ switch when they are
deployed with a speed-up of 2.
In this paper, we investigate the application of matchingalgorithms of low complexity that approximate M W M algorithms as scheduling algorithms for CIOQ switches. Generalizing the notion of a performance ratio from [9], we say thata matching algorithm approximates a M W M algorithm withapproximation parameters (c, d), 0 < c ≤ 1, d ≥ 0, if for any
values of the weights of the matching algorithm, the sum of

the constant d and of the weight calculated by the matchingalgorithm is at least c times as large as the optimal weightcalculated by the M W M.
First, we prove general results for matching algorithms
that approximate a M W M algorithm with approximation
parameters (c, d). We discuss two modes to deploy thesealgorithms in a CIOQ switch. We show that in both modes, adeployment of the switch with a rational speed-up S ≥ 1c issufficient to guarantee the stability of a CIOQ switch.
In the next step, we apply our results to four known maximal
matching algorithms that have a computational complexity ofO(N 2 ). We show that their deployment with a rational speedup S ≥ 2 guarantees the stability of a CIOQ switch.
Finally, we discuss the new improve matching algorithm
from [9] that approximates a M W M algorithm with approximation parameters ( 32 −², 0) and has a computational complexity of O(N 2 ). Applying our general results on approximation
algorithms, we show that this algorithm stabilizes a CIOQ
switch when it is deployed a rational speedup of S ≥ 32 + ².
The initial research on scheduling algorithms for CIOQ
switches has only investigated the impact of scheduling algorithms on the stability of single switches. Researchers [4]have shown that scheduling algorithms that stabilize single
switches might lead to instabilities when deployed in networks of input-queued switches. Stable switching policies for
networks of switches that require the exchange of control
information between switches in the network were introducedin [1], [4]. In [2] distributed scheduling policies based on
the computationally complex M W M algorithms that require
no communication between switches are proposed. Here, we
11-4244-0000-7/05/$20.00 ©2005 IEEE.

2

apply the ideas developed in [2] to the less complex approximation maximum weight matching algorithms and show thatthese algorithms stabilize single switches as well as networksof switches with moderate speed-up requirements. To the best
knowledge of the author, this is the first time that stability
for a network of input-queued switches could be shown for a
non-M W M algorithms with a speedup strictly below 2.
In the next section, we introduce a mathematical model of a
network of switches. In sections III and IV, we propose generalscheduling algorithms based on approximation algorithms andprove stability results for these architectures. We describe stability results for specific approximation algorithms in section
V and conclude in section VI.

where ri,j is the fraction of customers that depart from thelogical queue q i and are destined for the logical queue q j .
AssumingPa deterministicP
routing policy, there holds, ri,j ∈{0, 1},
ri,j ≤ 1,
ri,j ≤ 1. We set ri,j 6= 0, if q j

II. T ERMINOLOGY AND M ODEL

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 find that theoverall average workload at the logical queues q k 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

A. Model of a network of queues
In this section, we follow an approach in [2] to describe
a model of a queueing system. We assume a system of J
physical queues q̃ j , 1 ≤ j ≤ J of infinite capacity. Eachphysical queue consists of one or more logical queues, where
each logical queue corresponds to a certain class of customers
within the physical queue. Whenever a packet moves from one
physical queue to another, it changes class and therefore alsochanges logical queue. We denote a logical queue by q k , 1 ≤k ≤ K, where K ≥ J. A packet enters the network via anedge 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 at which 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 time model. Packets are supposed to be of fixed size
and an external time slot is the amount of time needed by apacket to arrive completely at an input link. For a speedup
S ≥ 1, we define an internal time slot as the amount of timeneeded for a packet to traverse the switching core.
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 external time slot.
k
We define En = (e1n , ..., eKn ), where en equals the numberof arrivals at the logical queue q k in the n-th external timekslot. Analogously, we define Dn = (d1n , ..., dKn ), 0 ≤ dn ≤ S,
where dkn expresses the number of departed packets from q k in
the n-th external time slot. Thus, we can describe the dynamics
of the system as follows:
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 thesystem. Thus, we can write:
En = An + Tn ,(2)where An = (a1n , ..., aKn ) denotes the arrivals from outside thesystem and Tn = (t1n , ..., tKn ) denotes the arrivals from inside
the system.
We further define a routing matrix R = [ri,j ], 1 ≤ i, j ≤ K,

1≤i≤K

1≤j≤K

follows q i along the route. Noting that Tn = Dn R and writing
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
Ai
i=1
=Λ
w.p.1,
lim
(4)
n→∞
n

Xn
n−→∞ n
lim

n−1

=

1X
(Ei − Di ) = 0
n−→∞ ni=0
lim

w.p.1.

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. In order toformalize this criteria, we introduce the following norm for avector Z ∈ RK :Definition 2: For a vector Z ∈ RK , Z = (z 1 , .., z K ), andthe function L−1 (k) as defined in this subsection, we set:


 X

||Z||maxL = max
zk .
(5)
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 (6) and is rate stable achieves 100% throughput.
B. Model of a network of switches
In this section, we apply the terminology of the previous
section to a network of CIOQ switches. A network of CIOQ
switches can be conceived as a queueing system as definedin the previous section where the virtual output queues are
1 Throughout the paper, we abbreviate ”with probability 1” by ”w.p.1”.

3

considered as the physical queues. 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 ofa 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 physical queues andare mapped to the same logical queues at each physical queue,i.e., a flow can be mapped biunivocally to a series of logicalqueues.
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
section III we prove the main results of this paper for per-flowscheduling schemes. In [2], it has been shown how per flowscheduling 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 canP model2 the whole network of switches as a systemofT Nb logical queues. For the sake of simplicity,1≤b≤B

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 outputof the b-switch. We further note that logical queues are defined
per switch, per virtual-output queue, and per flow. Thus, theindex 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 thenorm ||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 CIOQ switches, a traffic androuting 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 thecondition (7).
III. A PPROXIMATIONS TO THE M W M - ALGORITHM
In this section, we introduce local scheduling policies thatare based on approximation algorithms. We present thesepolicies in a non-distributed, centralized way, i.e., we willassume that the configurations of all switches are computedby a centralized server, which sends each switch its specificconfiguration. Following an argument in [5], one can show
how the algorithms presented in this paper can also be
implemented in a distributed fashion, such that each switch
calculates its own configuration. The stability results provedin this paper hold for a distributed implementation as well.
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 makeuse of a family of real positive functions fk (x) : N → R, 1 ≤k ≤ K, that satisfy the following property:
fk (n)
1= kw.p.1.
(8)
n
w
P k
k
We define d (n) =dm as the cumulative number of
lim

n→∞

m≤n

services at queue q k up to time n. Here, we assume that all
switches start service at the same time m = 0 and all switches
continuously work until time n. We define the weight of thequeue q k at time n as
φkn

=

k

n − fk (d (n)).

(9)

This choice of the weights is motivated by the fact that it willallow us to derive the relation (25), which in turn is used forthe proof of the rate stability in Theorem 1. We set Φn =(φ1n , .., φKn ). We note that the relations (8) and (9) imply thatfor any given positive integer v, there is¯ k¯¯φn − φkn+v ¯ ≤ c2 (v),(10)
where c2 (v) is a positive constant depending on v.
In [2], an example for fk (n) is given. The cumulative
function of external
q k is given
P k arrivals for the logical queuekk −1
by a (n) =am . The inverse function [a ] (p) maps them≤npacket number p to the arrival slot. Setting 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 n, the age of the p-thkpacket is n − [ak ]−1 (dn ).
B. Definition of an approximation algorithm
By definition [12], the choice of the matching Dn (M W M )by a M W M algorithm with weights Pn = (Pnk )1≤k≤B intime slot n can be described by the relation
Dn (M W M )PnT=

max Dn PnT .
Dn

(11)

For a scheduling algorithm ALGO that approximates¡¢a
M W M algorithm with approximation parameters ab , d ,a, b ∈ N, a and b prime to each other, there holds by definitionaDn (M W M )PnT − d, (12)Dn (ALGO)PnT ≥bwhere Dn (ALGO) denotes the matching chosen by the algorithm ALGO. In this paper, we only consider approximation
algorithms with weights chosen as in (9).

4

C. The deployment of approximation algorithms in a switchingcore
We consider approximation algorithms that approximate¡¢
the M W M algorithm with approximation parameters ab , d .
Without further mentioning it, we always assume that a ≤ b,a and b are prime to each other. To compensate for the factorab , we propose to deploy all approximation algorithms with arational speed-up of S = ab11 ≥ ab . We propose two different
modes to implement an approximation algorithm in a CIOQ
switch.
We extend the notation introduced in section II as follows:
We define Xn+ da1 , 0 ≤ d ≤ b1 −1, as the vector the entries ofb1which are the number of packets buffered in the logical queues
1
at time n + da
b1 . For every n satisfying n ≡ (0 mod a1 ), timeda1
n + b1 denotes the beginning of the (d + 1) -th internal timeslot after the the n-th external time slot. Similarly, Dn+ da1
b1

expresses the number of packets departing in the (d + 1)-thinternal time slot of the n-th external time slot.
In the mode keep, the scheduling algorithm computes amatching at the beginning of a time slot n ≡ (0 mod a1 ). It
keeps the matching constant until the beginning of the timeslot n + a1 , when a new matching is calculated. In the interval[n, n+a1 ), up to cells b1 are forwarded at equally spaced timeintervals of length ab11 . For the mode keep, the evolution of
the queue lengths is described as follows:
Xn+ da1b1=

Xn − dDn (ALGO)
X+
En+c + Dδ , 1 ≤ d ≤ b1 ,da0≤c< b 11µwhere Dδ = max 0, dDn − Xn −dkdan+ b 1= 1. The value gδk equals the number of instances1

where this happens for the V OQi,j and thus takes values c in
the range 0 ≤ c ≤ b1 .
The mode keep mode requires less computations than themode reconf ig mode. However, the mode reconf ig reacts
faster to the changing lengths of the V OQ. Applying theanalysis from [13], one can show that the mode keep modeleads to larger average package delays at the V OQs than themode reconf ig mode.
Now, we state the main result of this paper:
Theorem 1: For admissible traffic, a network of CIOQ
switches that implements an approximation maximum weightmatching algorithm with approximation parameters ( ab , d), andwhich is deployed in either mode keep or mode reconf ig
with a rational speedup of S = ab11 ≥ ab and where the weightφkn of queue q k at time n is defined as in (9) achieves 100%.
IV. P ROOF OF THEOREM 1
A. Lower bounds for the weights calculated by approximation
algorithms
In this section, we define lower bounds for the weight calculated by an approximation algorithm deployed with a rational
speedup ab11 > ab in either mode keep or mode reconf ig. We
will need these lower bounds for the proof of Theorem 1 insection IV-C. For our investigations, we consider the weight ofall matchings calculated in a1 successive time slots [n, n+a1 )by an approximation algorithm with approximation parameters( ab , d) in mode keep. Applying the relations (10) and (12), we
find
bX
1 −1

¶
En+c . Here,

P

d=0

da

0≤c< b 1
1

0 is the vector with K elements with all entries equal tozero and and the maximum is taken for each matrix entry
individually. If dkn = 1, the entry dkδ denotes the difference
between the number of cells that have been forwarded in the1interval [n, n + dab1 ), and the number of internal time slots din the interval. If dkn = 0, then dkδ = 0.
In the mode reconf ig, a new matching is computed inevery internal time slot, i.e., every ab11 external time slots, andcells are forwarded accorded to a calculated matching at mostonce. The queue evolution for the mode reconf ig is describedas follows:
Xn+ da1
b1= Xn −

d−1
X
e=0

+

X

Dn+ ea1 (ALGO)b
1

En+c + Gδ , 1 ≤ d ≤ b1 ,da0≤c< b 1
1

where Gδ is a vector with K elements where each entry is an
integer between 0 and b1 . If at time n, there holds xkn ≥ b1 ,then there is gδk = 0. If at time n, there holds xkn < b1 , thendepending on the V OQ length xkn at time n and the arrival
1
patterns akn+c , 0 ≤ c ≤ d − 1, in the interval [n, n + dab1 ),the switch might not always be able to forward a packet fromV OQi,j even if the scheduling algorithm prescribes so because≥≥≥

Dn (ALGO)ΦTn+ da1
b1

b1 Dn (ALGO)ΦTn − b1 Kc2 (a1 )ab1
Dn (M W M )ΦTn − b1 Kc2 (a1 ) − b1 db
a1 Dn (M W M )ΦTn − b1 Kc2 (a1 ) − b1 d.

(13)

Similarly, for an approximation algorithm with approximation
parameters ( ab , d) that is deployed in mode reconf ig with arational speedup ab11 > ab , we find using the relations (10),(11), and (12):
bX
1 −1

≥

Dn+ da1 (ALGO)ΦTn+ da1

d=0
bX
1 −1

a
b

d=0

b1

b1

Dn+ da1 (M W M )ΦTn+ da1 − b1 d
b1

b1

ab1
Dn (M W M )ΦTn+ da1 − b1 dbb1T≥ a1 Dn (M W M )Φn − b1 d − a1 Kc2 (a1 ).
≥(14)

B. The fluid methodology
The proof of theorem 1 makes use of the fluid methodology
as introduced in [6]. We 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

5of all possible network-wide matchings, i.e. possible switch
configurations throughout the network. Using (3), we obtainthe fluid equations of the system as follows:
X(t)
X

D(t)

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

= t,

(15)
(16)

π∈Π

(17)

π∈Π

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 , and that
t→∞

k

k

d (t)
.
wk

d
1
1
V (Φ(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πALGO ṪπALGO (t), Φ(t)i
πALGO ∈Q

ALGO (t)≤ hW, Φ(t)i − hπM W M , Φ(t)i + K1
< 0,
where the last estimate is derived using a well-known argument from [12]. We see from (18) and (22):d (t) → ∞ for t → ∞, we obtainφk (t) → t −where πM W M (t) and πALGO (t) are matchings chosen by
the M W M and ALGO algorithms, respectively, and K1 =(b1 d + (a1 + b1 )Kc2 (a1 ))/a1 . Now (23) follows from (19),(20), (21), and (24):

k

(18)

0<t−

d (t)
wk

≤

B.

(25)

k

C. Proof of Theorem 1

This implies lim d t(t) = wk , i.e.,

We denote the set of all switch configurations found attime t by an approximation algorithm withQapproximation
parameters ( ab , d) as defined in Theorem 1 as ALGO (t). The
fluid equations (16) and (17) can be rewritten as:XḊ(t) =πALGO ṪπALGO (t),
(19)

D(t)
= W,
w.p.1,(26)t
which corresponds to the rate stability condition of X(t)according to Definition 1. ¤

π1 ∈

Q

ALGO (t)X
Q

πALGO ∈

t→∞

lim

t→∞

V. E XAMPLES OF APPROXIMATION ALGORITHMS
TπALGO (t) = t.

(20)

ALGO (t)We define Γ = [γ (i,j) ] as the diagonal matrix with γ (k,k) =wk , and let Γ−1 be the inverse of Γ. Taking the derivative on
both sides of (18), we obtain:Φ̇(t) = I − Ḋ(t)Γ−1 .

(21)

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

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

(23)

∀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

A. Maximal matching algorithms
The most common approximation algorithms to a M W M
algorithm are variations of maximal matching algorithms. A
maximal matching is a matching that is not properly containedin any other matching of the graph. Different types of greedy
maximal matching algorithms are presented in [3], [14], and[7]. In [8], Drake and Hougardy propose a postprocessing step
to further improve the performance of a given maximal matching. As all algorithms discussed in this section approximate¡¢
any M W M algorithm with approximation parameters 12 , d ,we deduce from Theorem 1:
Theorem 2: For admissible traffic, the approximation algorithms to a M W M algorithm presented in this section
stabilize a network of CIOQ switches when they are deployedin either mode keep or mode reconf ig with a rational speedup S ≥ 2.
Thus, among others, we provide a new way to prove thatgreedy maximal matching weight matching algorithms arestable with a rational speed-up of S ≥ 2 as shown in [3].
B. The improve matching algorithm

We first give an overview of the main structure of thealgorithm
and refer the reader for the missing details to [9].
turn implies (22) for a certain B > 0. Thus we will show (23)Usingcommonnotation, we denote a graph as G = (V, E),
in order to prove (22).
where
E
and
V
are
the set of edges and vertices of the graph,
Finally, applying the principles of the fluid terminology as
respectively.
It
is
known
from graph theory that for any given
in [6] and dividing both sides of the equations by the number
weightM,theweightofwhich is not the largest possible,of considered time slots a1 , we can express the equations (13)onecanreplacesomeedges
of M with some other edges ofand (14) in the fluid terminology in the following way:
the graph such that the new set obtained is again a matchinghπM W M (t), Φ(t)i ≤ hπALGO (t), Φ(t)i + K1 , ∀π1 ∈ Π1 (t), (24)and has a strictly larger value than M. Such a process, which
L∈RK ,
hI,Li≤K0

6

Algorithm improve matching(G = (V, E), w : E → R+ , M )
1
2
3
4
5
6
7
Fig. 2.

make M maximal
M 0 := M
for e ∈ M do begin
if there exists a β-augmentation in M 0 with
with center ethen augment M 0 by a good β-augmentation
with center eend
return M 0
F ig.2 T he improve matching algorithm

adds a new set S ⊂ E to M and removes a set M (S) iscalled an augmentation. The set S is called the augmenting
set for this augmentation and the set M (S) is defined as theset of all edges in M that are incident with an end vertex ofan edge in S. If S contains edges of M, then these are also
contained in M (S). The gain of an augmentation is definedas w(S) − w(M (S)) which is the increase of weight achievedby the augmentation.
The idea of the improve matching algorithm is first touse standard techniques to expand a given matching to a
maximal matching (if the given matching is not alreadymaximal) and then to make local improvements via appropriate
augmentations to the maximal matching.
The improve matching algorithm considers only local
improvements that are obtained via short augmentations. A
short augmentation is defined as an augmentation such that
all the edges in the augmenting set are adjacent to someedge e ∈ E. This edge e is called a center of this shortaugmentation. It may or may not belong to the actual matchingwhich is locally changed. Examples of short augmentations are
given in [9].
Furthermore, the algorithm does not consider all shortaugmentations, but only those short augmentations that leadto a local gain of a factor of at least β, where β is a fixed
constant > 1. We call such a short augmentation that satisfies
the inequality w(S) ≥ βw(M (S)) a β-augmentation andthe augmenting set S the β-augmenting set. In a particularinstant, there might be more than one possible β-augmentation.
Intuitively, it is desirable to choose the β-augmentation that
produces the biggest gain. However, for the purpose of the
improve matching algorithm, it is sufficient to choose a good
β-augmentation. A β-augmentation with center e is called
good if it achieves at least (β − 1)/(β − 12 ) fraction of thegain that the best β-approximation with center e can achieve.
We now formally define the improve matching algorithm
in figure 2. First, the input matching M is made maximal(if necessary) and then no further changes are made to M.
Instead, M is copied to M 0 and all local augmentations aredone with respect to M 0 . The algorithm visits each edgee ∈ M only once, and if it finds any β-augmentation set at
this edge in M 0 , it performs a good β-augmentation centered
at e in M 0 . In [9], it is shown that the the complexity of theE.¢
improve matching is linear in the number of edges¡
In order to achieve approximation parameters 23 − ², 0 the

improve matching algorithm is applied iteratively. We firstuse a linear time maximal matching algorithm (see sectionV) to calculate a maximal matching M0 with weight at least
as large as w(M0 ) ≥ 21 w(Mopt ), where Mopt denotes a
maximum weight matching of the graph G = (V, E). We
then apply the improve matching algorithm to the matching
M0 to obtain a matching M1 and then iteratively apply thealgorithm to the matching Mi to ¡obtaina matching Mi+1 .
¢It is shown in [9] that at most O 1² iterations¡¢are required
to achieve approximation parameters 23 − ², 0 . Thus, we
deduce from Theorem 1:
Theorem 3: The iterated improve matching algorithm
when it is deployed in either mode keep or mode reconf ig
with a rational speed-up S ≥ 32 + ² stabilizes a network of
CIOQ switches under any admissible traffic.
VI. C ONCLUSIONSThis paper proposes the application of M W M - approximation algorithms scheduling algorithms for networks of
input queued switches. We show that M W M approximation
algorithms guarantee the stability of networks of switches
under specific speedup requirements. Applying these results,
we show that the improved matching algorithm guarantees
the stability of a network of input-queued switches when it isdeployed with a rational speed-up S ≥ 32 + ².
R EFERENCES[1] Ajmone, M.M., Leonardi, E., Mellia, M., Neri, F., On the throughput
achievable by isolated and interconnected input-queued switches undermulticlass traffic, Proc. of Infocom 2002, New York City, June 2002.
[2] Ajmone, M.M., Giaccone, P., Leonardi, E., Mellia, M., Neri, F., Local
scheduling policies in networks of packet switches with input queues,
Proc. of Infocom 2003, San Francisco, April 2003.
[3] Ajmone M.M., Leonardi, E., Mellia, M., Neri, F., On the stability of
input-buffer cell switches with speed-up, Proc. Infocom 2000, Tel Aviv,
March 2000.
[4] Andrews, M., Zhang, L., Achieving stability in networks of input queuedswithces, Proc. of Infocom 2001, Anchorage, Alaska, April 2001.
[5] Bauer, C., Distributed scheduling policies in networks of input-queued
packet switches, ACM Comp. Commun. Review, Vol. 34, no. 3, July
2004, 83 -92.
[6] Dai, J.G., Prabhakar, B., The throughput of data switches with andwithout speedup, Proc. of IEEE Infocom 2000, Tel Aviv, March 2000.
[7] Drake, D.E., Hougardy, S., A simple approximation algorithm for theweighted matching problem, Information Processing letters 85 (2003),
211-213.
[8] Drake, D.E., Hougardy, S., Linear time local improvements for weighted
matchings in graphs, WEA 2003, LNCS 2647, Seiten 107-119, 2003.
[9] Drake, D. E., Hougardy, S., A linear time approximation algorithm
for weighted matchings in graphs, preprint: http://www.informatik.huberlin.de/ hougardy/paper.html.
[10] Gabow, H.N., Tarjan, R.E., Faster scaling algorithms for general graphmatching problems, J. ACM 38:4, 1991, 815-853.
[11] Gabow, H.N., Data structures for weighted matching and nearest
common ancestors with linking, SODA 1990, 434 - 443.
[12] Keslassy, I., McKeown, N., Achieving 100% throughput in an input
queued switch, IEEE Trans. on Communications, vol. 47, no. 8, Aug.
1999, 1260 - 1272.
[13] Neely, M.M., Modiano, E., Rohrs, C.E., Tradeoffs in Delay Guarantees
and Computation Complexity for NxN Packet Switches, Proc. of theConf. on Information Sciences and Systems, Princeton: March 2002.
[14] Preis, R., Linear time 1/2 approximation algorithm for maximum
weighted matching in general graphs, Symposium on Theoretical Aspects of Computer Science (STACS) 1999, Springer LNCS 1563, 259 269.