Public Review for

Low Complexity, Stable Scheduling
Algorithms for Networks of Input Queued
Switches with No or Very Low Speed-up
Claus Bauer
This paper presents a number of new results in the area of switching performance. Prior work has demonstrated that there are backplane scheduling algorithms (for input queued switches) that remain stable withno speedup. However, as this paper points out, the complexity of these algorithms makes them impractical.
The algorithms that are currently practical require a speed-up in the backplane of at least a factor of two.
This paper describes new scheduling algorithms that can achieve stability without a speedup, with comparatively low complexity. The paper first builds approximate approaches that require a partial speed-up, andthen shows how these may be improved to obtain an algorithm which requires no speed-up. The proofs areextended to networks of such switches, and the paper shows how to implement a distributed version of thisscheduling algorithm.
The reviewers all liked the paper raising no major issues, except that it was seen as perhaps a little moreincremental than is aimed for in CCR, as the results are built on a solid body of literature in this area.
However, increasing the practical throughput of switches by a factor of two appears to be quite a significant improvement, worthy of appearing in CCR.

Public review written by

Matthew Roughan
The University of Adelaideacm

sigcomm

ACM SIGCOMM Computer Communication Review

15

•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•

Volume 36, Number 3, July 2006

Low Complexity, Stable Scheduling Algorithms
for Networks of Input Queued Switches with No
or Very Low Speed-up
Claus Bauer

Dolby Laboratories
100 Potrero Avenue
San Francisco, 94103, USA

cb@dolby.com
ABSTRACT

1. INTRODUCTION

The delay and throughput characteristics of a packet switch depend mainly on the queueing scheme and the scheduling algorithm
deployed at the switch. Early research on scheduling algorithms
has mainly focused on maximum weight matching scheduling algorithms. It is known that maximum weight matching algorithms
guarantee the stability of input-queued switches, but are impracticaldue to their high computational complexity. Later research showedthat the less complex maximal matching algorithms can stabilize
input-queued switches when they are deployed with a speed-up of
two. For practical purposes, neither a high computational complexity nor a speed-up of two is desirable.
In this paper, we investigate the application of matching algorithms that approximate maximum weight matching algorithms toscheduling problems. We show that while having a low computational complexity, they guarantee the stability of input queued
switches when they are deployed with a moderate speed-up.
In particular, we show that the improve matching algorithm
stabilizes input-queued switches when it is deployed with a speedup of 23 + ǫ.
In a second step, we further improve on these results by proposing a class of maximal weight matching algorithms that stabilize an
input-queued switch without any speed-up.
Whereas initial research has only focused on scheduling algorithms that guarantee the stability of a single switch, recent work
has shown how scheduling algorithms for single switches can be
modified in order to design distributed scheduling algorithms thatstabilize networks of input-queued switches. Using those results,
we show that the switching algorithms proposed in this paper do
not only stabilize a single switch, but also networks of input-queued
switches.

The development of fast transmission technologies such as Dense
Wavelength Division Multiplexing (DWDM) has led to an explosive increase in the transmission capacity of network links. In
order to cope with the increased transmission capacities, network
switches and routers must be equipped with high-speed switching
and forwarding technologies. For this purpose, the choice of thescheduling algorithm is a major design criteria of a switch as it
determines the throughput and delay characteristics of the switch.
The scheduling algorithm defines a policy that determines whichpackets are forwarded from the inputs of the switch to the outputsof the switch and which packets are temporarily buffered at the input side.
As purely output-buffered switches have shown to be impracticaldue to the required high speed-up in the switching core, in this paper we only consider input-queued (IQ) or combined input/output(CIOQ) queued switches. A typical architecture of a IQ/CIOQ
switch is given in figure 1. For each input i, there are N virtual
output queues V OQi,j , 1 ≤ j ≤ N . The cells arriving at input iand destined for output j are buffered in V OQi,j . The switchingcore itself is modeled as a crossbar which requires that not morethan one packet can be sent simultaneously from the same input or
to the same output. Many switch architectures require the switch
to work at a speed-up of S, S ≥ 1, which is defined as the ratio
between the potentially higher speed of the switching core and theline-speed of the incoming (and outgoing) links.

Input 1
VOQ_1,1

Switching FabricOutput 1

Categories and Subject Descriptors

VOQ_1,NC.2 [Computer-Communications Networks ]: General —Datacommunications; C.2.1 [ Network Architecture and Design]: Packetswitching networks.....
Input N
VOQ_N,1

General Terms

Output N

Modeling of communication networks, performance analysis

VOQ_N,N

Scheduler

Keywords
Scheduling algorithms, stability

Figure 1: Architecture of an IQ/CIOQ queued switch
As a first milestone in research on scheduling algorithms, McKe-ACM SIGCOMM Computer Communication Review

17

Volume 36, Number 3, July 2006

own et al. [15] have shown that maximum weight matching (M W M )algorithms stabilize input IQ/CIOQ switches when they are deployed without speed-up, i.e., S = 1. However, their high computational complexity of O(N 3 ) does not allow their practical deployment. As a less complex alternative, maximal matching (M M )algorithms have been investigated and it has been shown that they
can stabilize IQ/CIOQ switches when they are deployed with aspeed-up of S = 2. switches. The computational complexity ofa maximal weight matching algorithm is O(N 2 ).
Due to the impracticality of even low speedups at high line
speeds, it is desirable to understand if scheduling algorithms exist
that are of low complexity and can stabilize switches at speed-ups
significantly smaller than S = 2 or even without a speed-up. The
scope of this paper is to answer this question affirmatively and show
both, the existence of stable algorithms at speed-ups smaller thanS = 2 and in a second step the existence of M M algorithms thatstabilize IQ/CIOQ switches without a speed-up, i.e., S = 1.
In order to establish these results, we proceed as follows. In thefirst step, we define a large class of M W M algorithms and showthat they provide stability without speed-up. This investigation extends the work in [14] and is of independent interest, but also serves
us procedurally to prepare our investigation of low complexity algorithms with low or no speed-up.
In a second step, we investigate the application of matching algorithms of low complexity that approximate M W M algorithms
as scheduling algorithms for IQ/CIOQ switches. Generalizing thenotion of a performance ratio from [11], we say that a matchingalgorithm approximates a M W M algorithm with approximation
parameters (c, d), 0 < c ≤ 1, d ≥ 0, if for any values of theweights of the matching algorithm, the sum of the weight calculated by the matching algorithm and of the constant d is at leastc times as large as the optimal weight calculated by the M W M.
The case d = 0 reduces the definition of approximation parameters to the concept of a performance ratio c as defined in [11]. The
case d > 0 describes the case when the weight of the consideredmatching algorithm has to be increased by d in order to achieve a
performance ratio c.
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 these algorithms in a IQ/CIOQ
switch. We show that in both modes, a deployment of the switch
with a rational speed-up S ≥ 1c is sufficient to guarantee the stability of a IQ/CIOQ switch.
As a first application of these general results, we investigate four
known types of maximal matching algorithms that have a computational complexity of O(N 2 ). We derive a previously known resultthat their deployment with a rational speed-up S ≥ 2 guarantees
the stability of a IQ/CIOQ switch. Compared to previous work [3],[8], [6] that relied on a detailed analysis of the specific M M algorithm under consideration, our analysis of approximation M W M
algorithms provides a unified framework to show the stability of
the four considered types of M M algorithms.
As a second application, we discuss the improve matching algorithm from [11] that approximates a M W M algorithm with approximation parameters ( 23 − ǫ, 0) and has a computational complexity of O(N 2 ). Applying our general results on approximation algorithms, we show that this algorithm stabilizes a IQ/CIOQ
switch when it is deployed with a rational speed-up of S ≥ 32 + ǫ.
In the third step, we propose a class of M M algorithms that stabilize input IQ/CIOQ switches with a speed-up S = 1. In [19],it has been shown that under the assumption that no two V OQs
ever have the same occupancy, such a maximal weight matchingalgorithm exists. In practice, this assumption can obviously not be

ACM SIGCOMM Computer Communication Review

18

made. In contrast, this paper proposes the first maximal weightmatching algorithms that stabilize a IQ/CIOQ switch without any
speed-up and without assumptions on the occupancy V OQs. We
prove the stability of the proposed algorithm by further developing an idea from [19]: We first define, as described above, a large
class of maximum weight matching algorithms that guarantee thestability of a IQ/CIOQ switch. Then we show that a specific maximum weight matching algorithm out of this class is equivalent to
the maximal weight matching algorithm we propose. This equivalence and the stability of the stability of the M W M algorithm
prove the stability of the M M algorithm.
The improvement of our work compared to the ideas proposedin [19] derives from the specific choice of our weights. We define
weights of the maximal weight matching algorithm such that at any
point in time, no two weights are ever equal. This fact is crucial forshowing the equivalence of the maximal matching algorithm with a
specific maximum weight matching algorithm without making any
assumptions on the occupancy of the V OQs.
The early work on switch algorithms quoted above has investigated stable scheduling algorithms for single IQ/CIOQ switches.
Later work [1],[4] has shown that scheduling algorithms that guarantee the stability of a single switch might lead to instabilities when
deployed in networks of IQ/CIOQ switches. In [1] and [4], switching policies that require the exchange of information between theswitches have been proposed. In [2], for the first time a distributed,
complex maximum weight matching algorithm that does not require the exchange of information between switches in the network
has been proposed. We apply the methods developed in [2] to thedesign of the scheduling algorithms proposed in this paper. Consequently, the scheduling algorithms proposed here do not only guarantee the stability of a single switch, but also stabilize networks of
IQ/CIOQ switches.
Specifically, we not only show that the proposed algorithms stabilize networks of IQ/CIOQ switches when all switches deploy thesame scheduling algorithm, but we also prove that networks of
IQ/CIOQ switches where each switch deploys any of the scheduling policies proposed in this paper are stable.
In conclusion, to the best knowledge of the author, this is thefirst time that stability for a network of IQ/CIOQ switches could
be shown for a non-M W M algorithm with a speed-up strictly below S = 2. In particular, the class of M M algorithms proposed inthis paper satisfies the most common performance requirements on
a scheduling algorithm: It guarantees the stability of a network ofswitches, it can be implemented in a distributed manner that does
not require the exchange of information between the switches, it isof feasible computational complexity, and it does not require any
speed-up.
In sec. 3 - 5, we first describe the proposed scheduling policies
in a non-distributed, centralized way, i.e., we will assume that theconfigurations of all switches are computed by a centralized server,which sends each switch its specific configuration. In sec. 7, we
will then show how the algorithms presented in this paper can also
be implemented in a distributed fashion, such that in each time slot,
each switch calculates its own configuration. The stability results
proved in this paper hold for both a centralized and a distributed
implementation.
In the next section, we introduce a mathematical model of a network of switches. In sec. 3, we propose scheduling algorithms
based on generalized M W M algorithms and provide stability results for these algorithms. Stable scheduling algorithms based on
approximation algorithms are investigated in sec. 4. In sec. 5, we
present a class of maximal weight matching algorithms that guarantees the stability of a network of IQ/CIOQ switches when it isVolume 36, Number 3, July 2006

deployed with a speed-up S = 1. The stability of networks that
deploy a combination of different types of scheduling algorithms
at different switches is discussed in sec. 6. In sec. 7 we explain
how the algorithms proposed in this paper can be implemented in a
distributed manner throughout a network of switches. We conclude
in sec. 8.
We mention that parts of the work presented in Section 4 havebeen described in a more condensed form in [5].

2.

We assume that the external arrival processes are stationary andsatisfy the Strong Law of Large Numbers. Thus,

lim

n→∞

2.1 Model of a network of queues
In this section, we follow an approach in [2] to describe a modelof a queueing system. We assume a system of J physical queuesq̃ 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 of customers within the physical queue. Whenever a packet moves from one physical queue to another, it changes
class and therefore also changes logical queue. We denote a logicalqueue by q k , 1 ≤ k ≤ K, where K ≥ J. A packet enters the network via an edge switch, travels through a number of switches andleaves 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. We define L−1 (j) as
the counter-image through function L(k), i.e., it returns the logicalqueues 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 a packet to arrive completely at an input link. For a speed-up S ≥ 1, we define
an internal time slot as the amount of time needed for a packet totraverse the switching core.
We define a row vector Xn = (x1n , ..., xKn ), where the k-th
vector xkn represents the number of packets buffered in the logical queue q k at the beginning of the n-th external time slot. Wekdefine En = (e1n , ..., eKn ), where en equals the number of arrivalskat the logical queue q in the n-th external time slot. Analogously,kk
we define Dn = (d1n , ..., dKn ), 0 ≤ dn ≤ S, where dn expresseskthe number of departed packets from q in the n-th external timeslot. Thus, we can describe the dynamics of the system as follows:Xnn−→∞ n
lim

(4)

n−1

=

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

k∈L

w.p.1.

(j)

If we apply this norm to the average workload vector W, thenthe 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.

(1)

(5)

2.2 Model of a network of switches
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 theprevious section where the virtual output queues correspond to thephysical queues. In this model we neglect the output queues of theswitches 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 physical queues and are mapped tothe same logical queues at each physical queue, i.e., a flow can bemapped bi-univocally 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 sec.
3 - 7 we prove the main results of this paper for per-flow scheduling schemes. In [2], it has been shown how per flow scheduling(2)

system.
We further define a routing matrix R = [ri,j ], 1 ≤ i, j ≤ K,
where ri,j is the fraction of customers that depart from the logicalqueue q i and are destined for the logical queue q j . Assuming adeterministic routing policy, there holds, ri,j ∈ {0, 1},
1
0XX
ri,j A ≤ 1.
ri,j ,max @1≤j≤K

We set ri,j = 1, if q j follows q i along the route. Noting that
Tn = Dn R and writing I for the identity diagonal matrix, we findfrom (1) and (2):ACM SIGCOMM Computer Communication Review

w.p.1,D EFINITION 2. For a vector Z ∈ RK , Z = (z 1 , .., z K ), andthe function L−1 (k) as defined in this subsection, we set:
8
9
< X
=
zk .
||Z||maxL = max
j=1,..,J :;−1where An = (a1n , ..., aKn ) denotes the arrivals from outside thesystem and Tn = (t1n , ..., tKn ) denotes the arrivals from inside the

Xn+1 = Xn + An − Dn (I − R).

=Λ

Throughout this paper, whenever we talk about a stable system, we
refer to the notion of rate stability as given in definition 1.
A necessary condition for the rate stability of a system of queues
is that the average number of packets that arrive at any physicalqueue q̃ j during a time slot is less than 1. In order to formalize thiscriteria, we introduce the following norm for a vector Z ∈ RK :Packets that arrive at a logical queue q either arrive from outside
the system or are forwarded from a queue within the system. Thus,
we can write:

1≤i≤K

n

D EFINITION 1. A system of queues is rate stable ifk

E n = A n + Tn ,

Ai

i=1

where E[An ] = Λ = (λ1 , .., λK ) , ∀n ≥ 11 .
We now calculate the average workload of the logical queues
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 throughm previous queues inside the network is by the definition of therouting matrix R equal to ΛRm . Noting that (I − R)−1 = I +R + R2 + ..., we find that the overall average workload at thelogical queues q k is given by W = Λ(I − R)−1 .
Finally, we give a stability criteria for a network of queues asproposed in [2].

TERMINOLOGY AND MODEL

Xn+1 = Xn + En − Dn .

nP

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

(3)

19

Volume 36, Number 3, July 2006

is chosen as follows: We see from (7) that there exists a constant csuch thatd¯k(9)fk (d¯kn ) ≥ nk − c.
w
As the cumulative departure rate is less than the cumulative arrivalrate, there holds limn→∞ d¯kn ≤ wk n. Both estimates imply thatfor a c chosen as in (9) the weight φkn is always positive. This fact
is used in the proofs of Theorems 1 and 2 in the appendix. For
further usage, we note that the relations (7) and (8) imply that for
any given positive integer v, there is
˛
˛
˛
˛ k
k
(10)
˛φn − φn+v ˛ ≤ c2 (v),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 thesystem is T , we do not have more than Nb2 physical queues andT Nb2 logical queues at switch b. P
We can model the whole netT Nb2 logical queues. For
work of switches as a system of1≤b≤B

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 theb-switch. Analogously, QO (b, i) denotes the set of indexes corresponding to the logical queues directed to the i-th output of the bswitch. We further note that logical queues are defined per switch,
per virtual-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 networkof switches that handle multiple flows at their inputs.

where c2 (v) is a positive constant depending on v.
In [2], an example for fk (n) is given. The cumulative functionofPexternal arrivals for the logical queue q k is given by ak (n) =akm . The inverse function [ak ]−1 (p) maps the packet numm≤nber p to the time slot in which the packet arrived externally tothe network. Setting fk (p) = [ak ]−1 (p), the weight φkn = n −[ak ]−1 (p) + c denotes the age of the p-th packet at time n,i.e., theamount of time the packet has spent in the network, plus the constant c. At its departure time from the network n, the age of thekp-th packet is n − [ak ]−1 (dn ).

D EFINITION 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:
9
8
=
< X
X
|z m | .
|z m | ,||Z||IO = max
b=1,..,B :;m∈QO (b,i)

m∈QI (b,i)

i=1,..,N

3.2 Definition of maximum weight matchingalgorithms

Throughout this paper we assume a deterministic routing pattern
defined by the routing matrix R and we call a traffic and routing
pattern that satisfies the necessary rate condition for stability as defined in (5) admissible. Using definition 3, we can now rewrite thecondition (5) for a network of switches as follows:

In this section, we define a class of maximum weight matching policies that guarantee the stability of a network of IQ/CIOQ
switches. This class of policies is an extension of the policies defined in [14]. This extension is not only of interest in itself, but isnecessary to prove the stability of a class of M M algorithms deployed without speed-up as specified in Theorem 5 below.
We define a set of functions G :D EFINITION 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.

(6)

D EFINITION 5. A real function F : R → R is said to belong to
the set G ifa) F is monotonically non-decreasing, F (0) = 0, F (x) > 0 if
x > 0.
b) Ḟ (x) exists for all x > 0.
c) F (x) → ∞ for x → ∞.

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

3.

MAXIMUM WEIGHT MATCHING
POLICIES

For a fixed set of functions F1 , .., FK ∈ G, we define the functional
weights

3.1 Weight function
The scheduling policies introduced in this paper are based onmatching algorithms. Any matching algorithm 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:
lim

n→∞
k

We define d (n) =P

fk (n)
1= k.
nw

Ḟk (φkn ), 1 ≤ k ≤ K.

Furthermore, we define the following vector function via the functions F1 , .., FK and their derivatives:“”VḞ (Φ(n)) :=Ḟ1 (φ1n ), ..., ḞK (φK
n) .

(7)

We write the scalar product for two vectors v1 and v2 as hv1 , v2 i =v1 v2T . We define a schedule π = (π 1 , ..., π K ) of a switch as thechosen configuration of the switch core. If π k = 1 then the logicalqueue q k is connected to its output. In contrast if π k = 0, then the
logical queue q k is not connected to its output.
We define a scheduling algorithm M W M VF as follows: At eachtime t, the scheduling algorithm M W M VF chooses the schedule
π VF which is defined by the following equation:

dkm as the cumulative number of servicesm≤nat 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 the queue q k at time n as
φknk

= n − fk (d (n)) + c,

(8)where c is a given constant, and we set Φn = (φ1n , .., φKn ). This

π VF (n)choice of the weights is motivated by the fact that it will allow us
to derive the relation (23) in the appendix, which in turn is used forthe proof of the rate stability in Theorems 1 and 2. The constant c

ACM SIGCOMM Computer Communication Review

(11)

=

arg maxhπ, VḞ (φ(n))i,π(12)where the maximization is taken over all possible schedules π. Thismaximization problem is solved using the Hungarian method and20

Volume 36, Number 3, July 2006

has a complexity of O(K 3 ). We write the weight of the matching
chosen by a M W M VF algorithm as defined in (12) asDn (M W M VF )(VḞ (φ(t)))T

For the mode keep, the evolution of the queue lengths is describedas follows:= max Dn (VḞ (φ(t)))T (. 13)

Xn+ da1Dn

b1

We formulate the main result of this section:da1

0≤c< b 1

T HEOREM 1. For any set of functions F1 , .., FK ∈ G, a network of IQ/CIOQ switches that implements a M W M VF scheduling policy is stable under admissible traffic.

„
where Dδ = max 0, dDn − Xn −Proof: The proof is given in the appendix.
For further usage, we state the following corollary:
Corollary 1: If in (8) the weights are defined as [φnk + 1] insteadof φnk , where [x] denotes the biggest integer smaller than or equal
to x, then Theorem 1 still holds.
Proof: The proof is nearly identical to the proof of Theorem 1.

4.

= Xn − dDn (ALGO)
X+
En+c + Dδ , 1 ≤ d ≤ b1 ,da10≤c< b 1«
En+c . Here, 0 is

the vector with K elements with all entries equal to zero and the
maximum is taken for each vector entry separately. If dkn = 1, theentry dkδ denotes the difference between the number of cells that1), and the number
have been forwarded in the interval [n, n + dab1
kof internal time slots d in the interval. If dn = 0, then dkδ = 0.
In the mode reconf ig, a new matching is computed in every
internal time slot, i.e., every ab11 external time slots, and cells areforwarded accorded to a calculated matching at most once. The
queue evolution for the mode reconf ig is described as follows:

APPROXIMATIONS TO THE
MWM - ALGORITHM

In this section, we introduce local scheduling policies that are
based on algorithms that approximate M W M algorithms.

Xn+ da1

=

Xn −

b1

d−1
X

Dn+ ea1 (ALGO)

e=0

4.1 Definition of an approximation
MWM algorithm

+

X

b1

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

We formally define an approximation M W M algorithm as follows.

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 , thenthere is gδk = 0. If at time n, there holds xkn < b1 , then depending on the V OQ length xkn at time n and the arrival patterns
1
ekn+c , 0 ≤ c ≤ d − 1, in the interval [n, n + da), the switchb1
might not always be able to forward a packet from V OQi,j even if
the scheduling algorithm prescribes so because dk da1 = 1. The

D EFINITION 6. For a scheduling algorithm ALGO that approximates a M W M VF `algorithm- as defined in (12) - with ap´proximation parameters ab , d , a, b ∈ N, a and b prime to eachother, there holds
Dn (ALGO)(VḞ (φ(t)))Ta
Dn (M W M VF )(VḞ (φ(t)))T − d,
≥
b

P

n+ b

1

value gδk equals the number of instances 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 fasterto the changing lengths of the V OQ. Applying the analysis from[16], one can show that the mode keep mode leads to larger average package delays at the V OQs than the mode reconf ig mode.
In order to state the main result of this paper, we define a the setof functions G ∗ as a subset of the set G defined in section 3.2:

(14)

where Dn (ALGO) denotes the matching chosen by the algorithm
ALGO.

4.2 The deployment of approximation
algorithms in a switching core
We consider approximation algorithms that ` approximatea´
MWM algorithm with approximation parameters ab , d . Without
further mentioning it, we always assume that a ≤ b, where a and b
are prime to each other. To compensate for the factor ab , we propose
to deploy all approximation algorithms with a rational speed-up of
S = ab11 ≥ ab . We propose two different modes to implement anapproximation algorithm in a IQ/CIOQ switch.
We extend the notation introduced in sec. 2 as follows: We define Xn+ da1 , 0 ≤ d ≤ b1 − 1, as the vector the entries of which

D EFINITION 7. A real function F: R → R belongs to the set
G ∗ ifa) F ∈ G.
b) F̈ exists and for any fixed positive constant c,
lim

max

F̈ (x)

x→∞ t∈[x−c,x+c] Ḟ (x)

= 0.

(15)

b1

are the number of packets buffered in the logical queues at time1
1
. For every n satisfying n ≡ (0 mod a1 ), time n + dan + dab1
b1
denotes the beginning of the (d + 1) -th internal time slot after thethe n-th external time slot. Dn+ da1 expresses the number of pack-Now, we state the main result of this paper:
T HEOREM 2. We consider a network of IQ/CIOQ switches that
implements an approximation M W M VF algorithm with approximation parameters ( ab , d), with functional weights Fk (φkn ) as defined in (11), and where the functions Fk ∈ G ∗ . Assuming admissible traffic, the network is stable when the M W M VF algorithm isdeployed in either mode keep or mode reconf ig with a rational
speed-up of S = ab11 ≥ ab .

b1

ets departing in the (d + 1)-th internal time slot of the n-th external
time slot, and En+ da1 is defined analogously.
b1

In the mode keep, the scheduling algorithm computes a matching at the beginning of a time slot n ≡ (0 mod a1 ). It keeps thematching constant until the beginning of the time slot n + a1 , whena new matching is calculated. In the interval [n, n + a1 ), up to b1
cells are forwarded at equally spaced time intervals of length ab11 .

ACM SIGCOMM Computer Communication Review

Proof: The proof is given in the appendix.

21

Volume 36, Number 3, July 2006

Algorithm improve matching

4.3 Examples of approximation algorithms(G = (V, E), w : E → R+ , M )4.3.1 Maximal matching algorithms

1
2
3
4

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 contained in any othermatching of the graph.
The greedy maximal matching algorithm works similar to a general maximal matching as explained in [12]. It differs from a general maximal matching algorithm by not choosing an arbitrary edgeat each step, but picking the heaviest edge currently available instead. It has approximation parameters ( 12 , 0). A specific implementation for switches that deploy a per − V OQ queueing andscheduling discipline is proposed in [3]. We generalize this implementation to a per −f low queueing discipline as considered in thispaper as follows:

5
6
7

Figure 2: T he improve matching algorithm

D EFINITION 8. For a given input i and a given output j at agiven switch b, we define 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) .

4.3.2 The improve matching algorithm
We give a short overview of the main structure of the algorithm
and refer the reader for the missing details to [11]. We assume thatthe reader is familiar with standard graph theoretic terminology as
used in [11].
The idea of the improve matching algorithm is first to use
standard techniques to expand a given matching to a maximal matching (if the given matching is not already maximal) and then to makelocal improvements via appropriate augmentations to the maximal
matching. In particular, the improve matching algorithm considers only local improvements that are obtained via short augmentations. A short augmentation is defined as an augmentation suchthat all the edges in the augmenting set are adjacent to a specificedge of the graph.
Furthermore, the algorithm does not consider all short augmentations, but only considers β-augmentations , which are defined as
those short augmentations that lead to a local gain of a factor of atleast β, where β is a fixed constant > 1. In a particular instant, there
might be more than one possible β-augmentation. Intuitively, it isdesirable 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 is called good if it achieves at least (β − 1)/(β − 12 )fraction of the gain that the best local β-approximation can achieve.
We now formally define the improve matching algorithm infigure 2. First, the input matching M is made maximal (if necessary) and then no further changes are made to M. Instead, M iscopied to M ′ and all local augmentations are done with respect toM ′ . The algorithm visits each edge e ∈ M only once, and if it
finds any β-augmentation set at this edge in M ′ , it performs a good
β-augmentation centered at e in M ′ . In [11], it is shown that thethe complexity of the improve matching is linear in the numberof edges E, i.e., O(K 2 ).
`´In order to achieve approximation parameters 23 − ǫ, 0 the
improve matching algorithm is applied iteratively. We first use
a maximal matching algorithm (see sec. 4.3.1) to calculate a maximal matching M0 with a weight 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 thematching M0 to obtain a matching M1 and then iteratively apply
the algorithm to the matching`M´i to obtain a matching Mi+1 . It isshown in [11] that at most `O 1ǫ iterations
are required to achieve´
approximation parameters 32 − ǫ, 0 . Thus, we deduce from Theorem 2:

For a set of positive weights P k , 1 ≤ k ≤ K, where P k is theweight assigned to the logical queue q k , we now formally define amaximal weight matching algorithm as follows:
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 ) 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 tostep 2.

Preis [17] presented another linear time approximation algorithm
for a M W M algorithm with approximation parameters ( 21 , 0). The
main idea is to replace the heaviest edge needed by the greedy algorithm with a locally heaviest edge.
A different approach is used by Drake and Hougardy in [9]. The
main idea of the proposed algorithm is to grow in a greedy way
two matchings independently and to return the heavier of both as aresult. Again, this algorithm has approximation parameters ( 12 , 0).
In [10], the same authors propose local improvements to a given
matching as a postprocessing step to enhance the performance of
the approximation algorithm for the M W M problem in practice.
The postprocessing does not improve the approximation parameters ( 12 , 0).
Using the fact that all algorithms discussed in this section apthe M W M algorithm with approximation parameters´`proximate
1, 0 , we deduce from Theorem 2:2

T HEOREM 3. For admissible traffic, the maximal matching algorithms described in this section stabilize a network of IQ/CIOQ
switches when they are deployed in either mode keep ormode reconf ig with a rational speed-up S ≥ 2 and the functional weights are chosen as in (11).
Thus, among others, we provide a new way to prove that greedy
maximal weight matching algorithms are stable with a rational speedup of S ≥ 2 as shown in [3]. The maximal matching algorithms described in this section have a complexity of at most O(K 2 log K).

ACM SIGCOMM Computer Communication Review

make M maximal
M ′ := M
for e ∈ M do begin
if there exists a β-augmentation in M ′ with
with center ethen augment M ′ by a good β-augmentation
with center eend
return M ′22Volume 36, Number 3, July 2006

T HEOREM 4. The iterated improve matching algorithm defined with functional weights as in (11) stabilizes a network of
IQ/CIOQ switches under any admissible traffic when it is deployedwith a rational speed-up S ≥ 32 + ǫ in both modes mode keep andmode reconf ig.

T HEOREM 6. A network of IQ/CIOQ switches where each switch
deploys any of the scheduling algorithms defined in Theorems 1 - 5
is stable under admissible traffic.

5.

7. DISTRIBUTED IMPLEMENTATION OF
THE ALGORITHM

Proof: The proof is given in the appendix.

MAXIMAL WEIGHT MATCHING
ALGORITHMS WITHOUT SPEED-UP

The scheduling algorithms as defined in sec. 3, 4, and 5 formulate the scheduling problem as an optimization problem thattakes into account all logical queues of the network. Thus, theseformulations assume the existence of a centralized scheduling algorithm that always knows the state of the whole network. This
seems to contradict the purpose of the paper to investigate distributed scheduling policies, in which each switch only considers
the logical queues at its own V OQs. In this section, we describe
how the centralized scheduling policies proposed in sec. 3- 5 canbe implemented in a distributed manner.
We first consider M W M scheduling policies. The maximization in (12) is subject only to the crossbar constraint: In each timeslot, at each switch at most one cell can be sent from each one
input and at most one cell can be sent to each output. However,a switch configuration at a specific switch does not constrain the
choice of the switch configuration at another switch. Thus, we split
the weight vector Φ into B weight sub-vectors Φ = (Φ1 , .., ΦB ),where the sub-weight vector Φb contains the logical queues at theb-th switch. Accordingly, we split the vector VF in B sub-vectors
VF = (VF,1 , .., VF,B ). Thus, the maximization in (12) can be written as:

5.1 A stable maximal weight matching algorithm
In this section we define a class of maximal weight matchingalgorithms M M VG that guarantee the stability of a network ofswitches when they are deployed without a speed-up. A maximal weight matching algorithm with general weights has been described in sec. 4.3.1. Thus, in this section we only have to define
the specific weights of the class of algorithms M M VG .
We consider a set of functions gi , 1 ≤ i ≤ K that belong to theset G defined in sec. 3.2. We also require that for i 6= j and forany pair of two not necessarily different integers a and b ∈ N, thereholds
gi (a) 6= gj (b).

(16)
k

We define the functional weight of the queue q as
“
”
“ “h
i””
Gk φk (n):= exp g φk (n) + 1,(17)

where exp(x) is the exponential function. We note that the functions Gk in (17) correspond to the functions Ḟk in (11). Thus, thefunctions Fk (x) ∈ G introduced in sec. 3.2 correspond to the funcRx
tions Gk (t)dt.

F

π V (n)0= arg maxhπ, VḞ (φ(n))iπ=

We now give an example for a set of functions gk . A square-freenumber is defined as a natural number that cannot be divided by
the square of any other natural number. We denote by s1 < s2 <... < sK as the first K square-free numbers in increasing order.
For a fixed even natural number m, we then define the function
gk (x) as gk (x) = sk xm . The definition of the weights ensures that(16) always holds. This is true because for any two different logical queues k and l, i.e., k 6= l, there exist a prime number p suchthat the largest power of p that divides sk ([φk (n) + 1])m is odd,
whereas the largest power of p that divides sl ([φl (n)+1])l is either
even or equal to zero. In a specific implementation, the numbers si
could be chosen as the first K prime numbers.
We now state the main result of this section:

BX

arg maxhπb , VḞ ,b (Φb (n))i,

b=0

πb

where πb is the schedulechosen at the ¯b-th switch. The maximiza˘tion problem max hπb , VḞ ,b (φb (n))i can be solved solely at theπbb-th switch.
With regard to M W M approximation algorithms the same argument applies. Again, the approximation algorithm is executed
separately at each switch in the network as the crossbar constraint.
Finally, the same argument shows how the class of maximal matching algorithms M M VG can be implemented in a distributed manner.

8. CONCLUSIONSThis paper examines distributed scheduling algorithms of low
complexity that stabilize networks of IQ/CIOQ switches with low
or no speed-up and that do not require any coordination between
the switches in the network.
First, we consider a generalized class of M W M algorithms thatstabilize networks of IQ/CIOQ switches. Then, we investigate theapplication of approximation M W M algorithms scheduling algorithms for networks of IQ/CIOQ switches. We show that M W M
approximation algorithms guarantee the stability of networks of
IQ/CIOQ switches under specific speed-up requirements. Applying these results, we show that the improved matching algorithm
guarantees the stability of a network of IQ/CIOQ switches when it
is deployed with a rational speed-up S ≥ 23 + ǫ.
Second, we propose a maximal matching algorithm that satisfies
the most common performance requirements on a scheduling algorithm: It guarantees the stability of a network of switches, it can

T HEOREM 5. A network of IQ/CIOQ switches that implementsa M M VG . scheduling policy with a speed-up S = 1 and the functional weights as defined as in (17) stabilizes a network of IQ/CIOQ
switches under admissible traffic
Proof: The proof is given in the appendix.

6.

NETWORKS OF IQ/CIOQ SWITCHESWITH DIFFERENT SCHEDULINGPOLICIESIn sec. 3 - 5, we considered networks of IQ/CIOQ switches
where all switches deploy the same scheduling algorithm. As afurther extension, we show that a network of switches, where eachswitch in the network deploys any of the switching policies described in sec. 3 - 5, is stable as well:

ACM SIGCOMM Computer Communication Review

23

Volume 36, Number 3, July 2006

Switches, Proc. of the Conf. on Information Sciences andSystems, Princeton: March 2002.
[17] Preis, R., Linear time 1/2 approximation algorithm for
maximum weighted matching in general graphs, Symposiumon Theoretical Aspects of Computer Science (STACS) 1999,
Springer LNCS 1563, 259 - 269.
[18] 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.
[19] Shah, D,; Stable Algorithms for input queued switches, Proc.
39th Annual Allerton Conference on Communication,
Control and Computing, Oct. 2001.

be implemented in distributed manner that does not require the exchange of information between the switches, it is of feasible computational complexity, and it does not require any speed-up.
Finally, we prove that networks of IQ/CIOQ switches where eachswitch deploys any of the scheduling algorithms presented in thispaper are stable.

9.

REFERENCES[1] Ajmone, M.M., Leonardi, E., Mellia, M., Neri, F., On thethroughput achievable by isolated and interconnected
input-queued switches under multiclass 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 switcheswith input queues, Proc. of Infocom 2003, San Francisco,April 2003.
[3] Ajmone M.M., Leonardi, E., Mellia, M., Neri, F., On thestability of input-buffer cell switches with speed-up, Proc. of
Infocom 2000, Tel Aviv, March 2000.
[4] Andrews, M., Zhang, L., Achieving stability in networks of
input queued switchs, Proc. of Infocom 2001, Anchorage,
Alaska, April 2001.
[5] Bauer, C., Approximations to maximum weight matchingscheduling algorithms of low complexity, AICT 2005,
Lisbon, Portugal.
[6] Bauer, C., Throughput and delay bounds for input bufferedswitches using maximal weight matching algorithms and a
speed-up of less than two, Proc. of ICOIN 2004, Pusan,
Korea, Springer LNCS 3090.
[7] Dai, J.G., Prabhakar, B., The throughput of data switcheswith and without speed-up, Proc. of IEEE Infocom 2000, TelAviv, March 2000.
[8] Benson, K., Throughput of crossbar switches using maximal
weight matching algorithms, Proc. of IEEE ICC 2002, NewYork City.
[9] Drake, D.E., Hougardy, S., A simple approximation
algorithm for the weighted matching problem, Information
Processing letters 85 (2003), 211-213.
[10] Drake, D.E., Hougardy, S., Linear time local improvements
for weighted matchings in graphs, WEA 2003, LNCS 2647,
Seiten 107-119, 2003.
[11] Drake, D. E., Hougardy, S., A linear time approximation
algorithm for weighted matchings in graphs, ACM
Transactions on Algorithms, 1(1), pages 107-122.
[12] Gabow, H.N., Tarjan, R.E., Faster scaling algorithms forgeneral graph-matching problems, J. ACM 38:4, 1991,
815-853.
[13] Gabow, H.N., Data structures for weighted matching andnearest common ancestors with linking, SODA 1990, 434 443.
[14] McKeown, N., Keslassy, I., Analysis of schedulingalgorithms that provide 100% throughput in input-queued
switches, Proceedings of the 39th Annual Allerton
Conference on Communication, Control, and Computing.
Monticello, Illinois, October 2001.
[15] McKeown,N., Mekkittikul, A., Anantharam, V., Walrand, J.,
Achieving 100% throughput in an input queued switch, IEEE
Trans. on Communications, vol. 47, no. 8, Aug. 1999, 1260 1272.
[16] Neely, M.M., Modiano, E., Rohrs, C.E., Tradeoffs in Delay
Guarantees and Computation Complexity for NxN Packet

ACM SIGCOMM Computer Communication Review

10. APPENDIX
10.1 The fluid methodology
For the proofs of the Theorems 1, 2, and 5, we use the fluid
methodology and its extension given in [2] and [7]. Applying thedefinitions introduced in sec. 2, we define the three following continuous vector functions:• X(t) = (X1 (t), ..., XK (t)) denotes the number of packets
in the logical queues at time t.
• D = (D1 (t), ..., DK (t)) denotes the number of packet departures from the logical queues until time t.
• A = (A1 (t), ..., AK (t)) denotes the number of packets arrivals at the logical queues until time t.
We consider a specific scheduling algorithm F and we define ΠF ={π F } as the set of all possible network-wide matchings chosen by
F. For all π F ∈ ΠF , we denote by TπF (t) the cumulative amountof time that the matching π F has been applied until time t by thealgorithm F. Obviously, TπF (0) = 0 ∀π F ∈ ΠF . Using (3), we
obtain the fluid equations of the network of IQ/CIOQ switches asfollows:
X(t)D(t)= X(0) + Λt − D(t)(I − R),X=
π F TπF (t),

(18)
(19)

π F ∈ΠFX

π F ∈Π

TπF (t) = t.

(20)

F

The first equation models the evolution of the logical queues,
whereas the second equation counts the total number of departuresfrom the V OQs. The third equation reflects the fact that in eachtime slot each input is connected to some output. Taking the derivatives, we derive from (19) and (20):X
Ḋ(t) =
π F ṪπF (t),(21)π F ∈ΠF

X

ṪπF (t)

= 1.

(22)

π F ∈ΠF

Applying the fluid methodology further, we define a continuousversion of the weights Φn - defined in (8) - as Φ(t).

10.2 Proof of Theorem 1
First, we state an algebraic relation which we will use for thesubsequent proof. We note that by (7) lim fk (t) → t/wk . Thus,t→∞kby (8) and d (t) → ∞ for t → ∞, we obtainkφk (t) → t −

24

d (t)
+ c,
wk

(23)

Volume 36, Number 3, July 2006

from which we obtain by taking the derivative on both sides:
Φ̇(t) = I − Ḋ(t)Γ−1 ,

find
(24)

(i,j)

b1 −1

X

(k,k)

where we define Γ = [γ] as the diagonal matrix with γ=
wk , and let Γ−1 be the inverse of Γ. Then, we set H(x) = ΓVF (x), x ∈RK and define the Lyapunov function:

Dn (ALGO)VḞT (Φn+ da1 )
b1

d=0

=

G(t) = hI, H(Φ(t))i,b1 Dn (ALGO)VḞT (Φn )+ Dn (ALGO)||Φ(t)||IO ≤ B,dG(t) ≤ 0
dt

(26)

b1

1≤k≤K

that ||Φ(t)||IO>
C, then there holds
maxG(s), which by c) in definition 5 implies

b1

˛
˛
˛
k ˛ da1
˛F̈k (φn )˛1≤k≤K n≤t≤n+ da1
b1≤ K maxs, ||G(s)||IO ≤C

max

b1

(25) for a certain B > 0. Thus, we will show (26) in order to prove(25). Now (26) follows from (24), (21), and (22):k≤ ǫ max Ḟk (φ (n)),
1≤k≤K

d
G(t)
dt
d
h1, H(Φ(t))i=dt= hΦ̇(t), ΓVḞ (Φ(t))i= hI − Ḋ(t)Γ

«VḞT (Φn+ da1 ) − VḞT (Φn ) . (28)We see from (10) and (15),˛˛˛˛˛Dn (ALGO)(V T (Φ da1 ) − V T (Φn ))˛
Ḟ
Ḟ
˛
˛
n+ b
1
˛
˛
˛
˛
≤ K max ˛˛(Ḟk (φkn+ da1 ) − Ḟk (φkn ))˛˛

(25)

for a certain constant B > 0. We see that if

−1

X
d=0

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

b1 −1 „

(29)

for any arbitrarily small ǫ and for sufficiently large φk (n). Inserting(29) in (28) we see using (14)
b1 −1

X

, ΓVḞ (Φ(t)))i

π VF ∈ΠV≥

b1 Dn (ALGO)VḞT (Φn ) − ǫ≥ab1
Dn (M W M )VḞT (Φn ) − ǫ max Ḟk (φkn ) − b1 d
1≤k≤K
b

F

= hW, VḞ (Φ(t))i −

b1

d=0

= hW, VḞ (Φ(t))i − hḊ(t), VḞ (Φ(t))iX
π VF ṪπVF (t), VḞ (Φ(t))i= hW, VḞ (Φ(t))i − hX

Dn (ALGO)VḞT (Φn+ da1 )max Ḟ (φkn )1≤k≤K≥ a1 Dn (M W M )VḞT (Φn ) − ǫ max Ḟ (φkn ) − b1 d. (30)ṪπVF (t)hπ VF (t), VḞ (Φ(t))i1≤k≤Kπ VF ∈ΠV

F

In a similar way we now derive a lower bound for an approximation
algorithm with approximation parameters ( ab , d) that is deployedin mode reconf ig with a rational speed-up ab11 > ab . For this purpose, we note that the relation (29) holds for any scheduling algorithm ALGO, in particular it holds for M W M VF . Using (14),(13), and (29), we obtain:= hW, VḞ (Φ(t))i − hπ VF (t), VḞ (Φ(t))i≤ 0.
The last inequality follows from (12) and by an argument in [15].
We see from (23) and (25):
k

0<t−

d (t)
+c
wk

≤ B.

b1 −1

X

k

d=0

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

D(t)
lim
t→∞
t

b1

b1

b1 −1

≥
= W,

Dn+ da1 (ALGO)VḞT (Φn+ da1 )w.p.1,(27)≥

which corresponds to the rate stability condition of X(t) according
to definition 1. 2=

10.3 Proof of Theorem 2+

10.3.1 Lower bounds for the weights calculated byapproximation algorithms

ab1
Dn (M W M )VḞT (Φn+ da1 ) − b1 d
b
b1
ab1
T
Dn (M W M )VḞ (Φn ) − b1 d
b
«
„
ab1
Dn (M W M ) VḞT (Φn+ da1 ) − VḞT (Φn )bb1≥ a1 Dn (M W M )VḞT (ΦTn ) − b1 d − ǫ max Ḟk (φk (n)).
1≤k≤K

In this section, we define lower bounds for the weight calculatedby an approximation algorithm deployed with a rational speed-up
b1> ab in either mode keep or mode reconf ig. We will needa1these lower bounds for the proof of Theorem 2 in sec. 10.3.2. For
our investigations, we consider the weight of all matchings calculated in a1 successive time slots [n, n+a1 ) by an approximation algorithm with approximation parameters ( ab , d) in mode keep. We

ACM SIGCOMM Computer Communication Review

a X
D da (M W M )VḞT (Φn+ da1 ) − b1 d
b d=0 n+ b11
b1

(31)

10.3.2 Proof of stability
Applying the principles of the fluid terminology as in [7] anddividing both sides of the equations by the number of consideredtime slots a1 , we express the equations (28) and (31) in the fluid

25

Volume 36, Number 3, July 2006

10.4 Proof of Theorem 5

terminology as follows:

We follow an idea in [19] to show that the algorithm M M VG
always calculates the same matching as the following maximum
weight matching algorithm M W M VG : M W M VG is defined as
the M W M algorithm with the functional weights chosen as in(17). This maximum weight matching algorithm is stable by Corollary 1. The stability of M M VG then follows from the fact that
M W M VG and M M VG always calculate the same matching. Thisis shown using an argument from [19]. In the first iteration, theM M VG algorithm chooses the queue with the largest functional
weight of all Gk (φk (n)), 1 ≤ k ≤ K, say Ga (φa (n)). We recallafrom`ˆ (16) and (17)˜´ that at any time n, there is ga ([φ (n) + 1]) 6=
gb φb (n) + 1 . Thus, the M W M Vg,E algorithm, which maximizes the weight of the whole matching, will also choose the queue
q a with the functional weight Ga (φa (n)) for packet transfer because
K
K
“h
i”
X
X
exp(gk φk (n) + 1
Gk (φk (n)) =hπ VF (t), Φ(t)i≤hπ ALGO (t), Φ(t)i + K1 + ǫ max Ḟk (φk (t)), (32)1≤k≤K

where π VF (t) and π ALGO (t) are the matchings chosen at time t
by M W M VF and ALGO algorithms, respectively, ǫ > 0 can bechosen arbitrarily small, and K1 = b1 d. Now the proof of Theorem 2 is similar to the proof of Theorem 1 by taking into account
(32):
d
d
G(t) =
h1, H(Φ(t))idtdt= hΦ̇(t), ΓVḞ (Φ(t))i= hI − Ḋ(t)Γ−1 , ΓVḞ (Φ(t)))i= hW, VḞ (Φ(t))i − hḊ(t), VḞ (Φ(t))i= hW, VḞ (Φ(t))iX− hπ ALGO ṪπALGO (t), VḞ (Φ(t))ig([φa (n)+1])−1

π ALGO ∈ΠALGO≤≤ hW, VḞ (Φ(t))i + K1 + ǫ max Ḟk (φ(n))
1≤k≤K
X
VF
− h
π (t)ṪπALGO (t), VḞ (Φ(t))i=<=≤ hW, VḞ (Φ(t))i + K1 + ǫ max Ḟk (φ(n))
1≤k≤K
X
ALGO
−
Ṫπ
(t)hπ VF , VḞ (Φ(t))i
ALGO

1≤k≤K

(33)

We see from (6) that there exists a constant ǫ1 > 0 such that||W ||IO ≤ 1 − ǫ1 . Applying (12), we obtain from (33)
d
G(t)
dt
= hVḞ (Φ(t)), W − (1 − ǫ1 )π VF i − ǫ1 hπ VF , VḞ (Φ(t))i

In order to prove Theorem 6, we apply the techniques used forthe proofs of Theorems 1- 5. We divide the switches in the network into h groups Gh where h denotes the number of different switching policies deployed throughout the considered networkof IQ/CIOQ switches. Accordingly, we divide the departure vector D(t) and the arrival rate vector W into h sub-vectors, i.e.,D(t) = (Di (t))1≤i≤h and W = (Wi )1≤i≤h . In order to provestability according to def. 1, we have to show that for 1 ≤ i ≤ h,1≤k≤K

≤ −ǫ1 hπ, VḞ (Φ(t))i + K1 + ǫ max Ḟk (φ(n)). (34)1≤k≤K

The last estimate is derived using a well-known argument based on
Birkhoff’s theorem as in [15]. We note thatḞkmax (φ(n)) := max Ḟk (φ(n)) ≤ hπ VF , VḞ (Φ(t))i.
1≤k≤K

Di (t)= Wi , w.p.1.
(37)t
For each i, the relation (37) can be shown by applying the respective proofs of the Theorems 1, 2, and 5 to the respective groupof switches Gi , instead of applying them to the whole network ofswitches.

(35)

Otherwise there would behπ ∗ , Ḟkmax (φ(n))i > hπ VF , VḞ (Φ(t))i,(36)where π ∗ is the schedule defined as π kmax = 1 and π k = 0 for
k 6= kmax . This is impossible as the relation (36) would contradict
the definition of the M W M algorithm M W M VF . Choosing ǫ =ǫ1 /2, we see from (34) and (35):d
G(t) ≤dt−

exp ([φ (n) + 1]) − 1
exp(1) − 1
exp ([φa (n) + 1])
Ga (φa (n)).

10.5 Proof of Theorem 6+ K1 + ǫ max Ḟk (φ(n))
VF

exp(b)

Due to the crossbar structure of the switch, neither the M M VG
nor the M W M VG algorithm chooses any logical queue for packet
transfer that competes for a switch input and output with the chosen logical queue. Thus, these logical queues can be discarded forthe rest of the proof. Applying the same arguments to the subset of the remaining queues, one sees that both algorithms choose
the queue with the largest functional weight among the remaining
queues. The successive application of this argument shows thatboth scheduling algorithms are indeed identical.

= hW, VḞ (Φ(t))i − hπ VF , VḞ (Φ(t))i+ K1 + ǫ max Ḟk (φ(n)).

X

b=1
a

π ALGO ∈ΠALGO

π ALGO ∈Π

k=1
k6=a

k=1
k6=a

ǫ1 VF
hπ , VḞ (Φ(t))i < 0,3

for a sufficiently large ||Φ(t)||IO . Now Theorem 2 follows from(23) and (25) in the same way as Theorem 1.2

ACM SIGCOMM Computer Communication Review

26

Volume 36, Number 3, July 2006