Stable local scheduling policies in networks of
input-queued switches
Claus Bauer, Research Scientist, Dolby Laboratories
100 Potrero Avenue, San Francisco, CA, 94103, USA
cb@dolby.com, tel.: +1 415 558 0343, fax: +1 415 863 1373
Keywords: Stable local scheduling policies, networks of switches

that guarantees the stability of the switch, i.e., that guarantees
that the input and output queues do not grow infinitely underreasonable traffic arrival patterns.
For switches without speedup, a scheduling algorithm thatguarantees the stability of the switch was first proposed in [11].
The scheduling problem is modeled as a bipartite maximum
weight matching problem. The weights of the matching are thelengths of the V OQs, which we denote as Li,j , 1 ≤ i, j ≤ N.
It was shown in [11] and later in [8], that if the average arrival
traffic at each input and the average arrival traffic destined toeach output is not more than 1, then this maximum weightmatching policy guarantees the stability and even a bound on
the average delay of the switch. In [12] and [14], the result in[11] has been generalized to a wider class of maximum weightmatching algorithms. We define a real function F (x) : R → R
which satisfies the following properties: I. F is monotonicallynon-decreasing and F (0) = 0, F (x) > for X > 0, II. Ḟ (x)exists for all X > 0. It is shown in [14] that if we define
a maximum weight matching policy that uses as weights thefunction values of the derivative of F , applied to the lengthof the V OQs, i.e. Ḟ (Li,j ), then such a policy guarantees thestability of a single switch.
It was shown in [3] that in a specific network of input-

Abstract— Most research on switch architectures andscheduling algorithms has focused on single switches. It is
well known that certain scheduling policies that are based on
maximum weight matching algorithms guarantee the stability ofsingle switches. However, recent research has shown that mostof these scheduling policies do not guarantee the stability of
networks of input-queued switches.
So far, only one local scheduling policy has been proposed thatprovides the stability of a network of input-queued switches if it
is deployed at every switch. In this paper, we show the existenceof a large class of scheduling policies based on maximum weightmatching policies that guarantee the stability of a network ofswitches. We also show the stability of networks of switches inwhich specific classes of different switching policies are deployedsimultaneously at different switches.
It has been shown that the iOCF algorithm guarantees thestability of a single input-queued switch if it is deployed with aspeed-up of two. In this paper, we generalize the iOCF algorithm
to the iN COF algorithm and show under which condition
the iN OF C algorithm, when it is deployed without speedup,
stabilizes networks of input-queued switches.

I. I NTRODUCTION AND M OTIVATION
During the last decade, most research on switch architectures, scheduling algorithms and switch stability has focusedon switch architectures and scheduling algorithms for single
switches. Only very recently, researchers have started to investigate the stability of networks of switches.
With regard to single switches, input-queued switches havebeen investigated extensively. A typical input-queued switch isshown in figure 1. An N × N input-queued switch consists of
N inputs and N outputs. It deploys buffers at the inputs and/or outputs. In order to avoid head of line blocking, each input
buffer is split into N virtual output queues as follows: At each
input i, packets that are destined for an output j, 1 ≤ j ≤ N,
are buffered in the virtual output queue V OQi,j . In general,
the switching core is modeled as a crossbar such that not
more than one packet can be sent simultaneously from thesame input or to the same output. In addition, various switch
architectures require that the switching speed in the switchingcore is S, S ≥ 1 times faster than the speed of the input andoutput links. The factor S is denoted as the speedup.
At any moment in time, different packets might compete for
input or output resources of the switch. Thus, the switch design
includes the definition of a scheduling policy that decides
which packets will be forwarded and which will be buffered.
In particular, the designer is interested in a scheduling policy

Input 1
VOQ_1,1

Switching FabricOutput 1

VOQ_1,N.....
Input N
VOQ_N,1
Output N

VOQ_N,N

Scheduler

Fig. 1.

1

Architecture of an input-queued switch

2

queued switches that is not overloaded, a maximum weightmatching policy as defined in [11] that is implemented independently at each switch does not guarantee the stability of
the network. The authors give a specific example where under
non-overloaded conditions the number of packets bufferedat specific V OQs at some switches in the network grows
to infinity. This result showed that the previous work on
maximum weight matching algorithms in isolated switches isof limited practical value in networks of switches.
In [1] and [3], switching policies are presented that guarantee the stability of all switches within a network, but require
coordination and cooperation among the switches within the
network. In [3], the LIN policy is proposed, which assumes
that all switches in the network always know the actual traffic
patterns all other switches. In [1], a stable scheduling policythat requires the exchange of state information only among
adjacent switches is illustrated. Both policies require signaling
traffic for the communication between the switches.
In [2], for the first time a distributed switching policy
was proposed that guarantees 100% throughput in a networkof input-queued switches. Each switch makes its schedulingdecision independently of the other switches and no additionalsignaling traffic between the switches is required. The scheduling algorithm is a maximum weight matching algorithm withspecific weights.
It is of interest to understand if other classes of distributedscheduling policies that guarantee the stability of a networkof input-queued switches exist. In this paper, we will provethat the class of maximum weight algorithms defined in [14]and which was proven to be stable for an isolated switch canbe modified to a local scheduling policy that guarantees thestability of a network of switches. We will also show that
networks of switches that deploy different scheduling policiesof this class at different switches simultaneously are stable.
Based on these results, we will also establish new theorems
related to the theory of maximal matching algorithms andtheir deployment in networks of input-queued switches. Dueto their low complexity, maximal matching algorithms havebeen widely researched ([5], [9], [10]). It has been shown in[6], [4] that maximal matching algorithms deployed with aspeedup of two, or even slightly less, guarantee the stabilityof a switch. Recently, Shah ([14]) could prove that a specificmaximal matching algorithm, the iLQF algorithm which isdefined as the maximal matching algorithm that uses the lengthof the V OQs - the Li,j - as weights, is stable even without aspeedup. This result assumes however, that ties are broken ina specific way or that no two V OQs have the same length.
Another maximal matching algorithm that has been widely
researched in the literature ([5]) is the iOCF algorithm, which
is defined as the maximal matching algorithm that uses thetime a cell has already spent in its respective V OQ as theweight.
Compared to the iLQF algorithm, the iOCF algorithm
is more complex to implement as it requires the switch toattach a time tag to each cell. However, the iOCF algorithm
provides guarantees on the absolute packet delay which theiLQF algorithm does not ([5]).
Thus, it is desirable to understand if the iOCF algorithm

can also provide stability without speedup. In this paper, we
answer this question affirmatively. We not only show that theiOCF algorithm is stable without speedup, but prove that theiOCF algorithm can be generalized to the iN OCF maximal
matching algorithm that guarantees the stability of a networkof switches when it is deployed without speedup.
The rest of the paper is organized as follows. Section II
introduces the terminology to model networks of queues andnetworks of switches. In section III, we introduce the fluid
methodology to describe the state of the network and define
the classes of matching policies we are interested in. Then
we prove that a network wide deployment of any of thesematching policies guarantees the stability of a network. We
also show that a network which deploys different matchingpolicies simultaneously at different switches is stable. In
section IV, we show that the iN OCF algorithm ensures thestability of a network of input-queued switches when it isdeployed without speedup. We conclude in section IV.
II. T ERMINOLOGY AND M ODEL
A. Model of a network of queues
In this section, we follow an approach in [2] to describe
our model of a queueing system. We assume a system of J
physical queues q̃ j , 1 ≤ j ≤ J of infinite capacity. 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 fromone 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 thatbelong to the physical queue q̃ j .
Throughout this paper, the time t is described via a discrete,slotted time model. Packets are supposed to be of fixed size
and a timeslot is the time needed by a packet to arrivecompletely at an input link.
We define a row vector Xn = (x1n , ..., xKn ), where thek-th vector xkn represents the number of packets bufferedin the logical queue q k in the n-th timeslot. We definekEn = (e1n , ..., eKn ), where en equals the number of arrivalskat the logical queue q in the n-th timeslot. Analogously, wekdefine Dn = (d1n , ..., dKn ), where dn expresses the number ofkdeparted packets from q in the n-th 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 fromoutside the system or are forwarded from a queue within thesystem. Thus, we can write:
En = A n + T n ,where An = (a1n , ..., aKn ) denotes the arrivals from outside thesystem and Tn = (t1n , ..., tKn ) denotes the arrivals from inside3

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

1≤i≤K

follows q i along the route. Noting that Tn = Dn R and writing
I for the identity diagonal matrix, we find
Xn+1 = Xn + An − Dn (I − R).

(2)

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,
(3)
lim
n→∞
n
where E[An ] = Λ = (λ1 , .., λK ) , ∀n ≥ 11 . Noting that (I −R)−1 = I + R + R2 + ..., we find that the average workload
W = (w1 , ..., wK ) 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 ifXnn−→∞ 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 definition:
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 .
(4)
j=1,..,J 

−1
k∈L

(j)

The necessary condition for rate stability can now be formalized as follows:||W ||maxL < 1.

are 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.
It has been shown in [2] how stability results for per-flowscheduling schemes can be used to design stable per-virtual
output queue 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 C, we do not have more thanNb2 physical queues and CNb2 logical queues at switch b.
We canP model2 the whole network of switches as a systemof
CNb logical queues. For the sake of simplicity,1≤b≤B

we suppose that Nb = N, ∀b, 1 ≤ b ≤ B and set K =CN 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 use these definitions to adapt the norm||Z||maxL to a network of switches:
Definition 3: Given a vector Z ∈ RK , Z = {z k , k =CN 2 b + CN i + Cj + l, 0 ≤ b < B, 0 ≤ i, j < N, 0 ≤ l < C,
the norm ||Z||IO || is defined as follows:


 X

X
|z m | ,||Z||IO = max|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 (5) can now
be written for a network of switches as follows:
Definition 4: For a network of IQ/CIOQ switches, a traffic
and routing pattern W is admissible if and only if:||W ||IO = ||Λ(I − R)−1 || < 1.

(6)

In the rest of this paper, we will only consider traffic androuting patterns that satisfy the condition (6).

(5)

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

III. M AXIMUM WEIGHT MATCHING LOCAL SCHEDULINGPOLICIES

A. Weight function
B. 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 the previous section where the virtual output queues
are 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 and1 Throughout the paper, we abbreviate ”with probability 1” by ”w.p.1”.

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:
1
fk (n)= kw.p.1.
(7)
n→∞
n
w
P k
k
We define d (n) =dm as the cumulative number of
lim

m≤n

services at queue q k up to time n. For a given positive constantC, we define the weight of the queue q k at time n as
φkn

=

k

n − fk (d (n)) + C.

(8)

4

C. Maximum weight matching policies

We setΦn = (φ1n , .., φK
n ).

(9)

We see that for a fixed function f (·) that satisfies the relation(7), there exists a constant C > 0 such that ∀n, n ≥ 0, therekkdholds f (dn ) ≤ wnk − C. Further, because the accumulative
departure rate at each logical queue q k cannot be more thankthe accumulative arrival rate, there holds lim d w(n)
≤ n.
k
n→∞
Combining these two estimates, we see that for any functionf (·) that satisfies the condition (7), one can always find a
C > 0 such that the weights φkn are positive ∀n, n ≥0, ∀k, 1 ≤ k ≤ K. This fact is important for the proof oftheorem 1 below. In the sequel, we will always assume thatthe weights φkn are positive.
In [2], an example for fk (n) is given. The cumulative
function of external
q k is given
P karrivals for the logical queue
by ak (n) =am . The inverse function [ak ]−1 (p) mapsm≤nthe packet number p to the arrival slot. Setting C = 0 and
fk (p) = [ak ]−1 (p), the weight
φkn = n − [ak ]−1 (p)(10)

denotes the age of the p-th packet at time n, i.e., it denotes
the time the packet has already spent in the network. At its
kdeparture time n, the age of the p-th packet is n − [ak ]−1 (dn ).

In this section, we define a class of maximum weightmatching policies that guarantees the stability of a networkof input-queued switches. We introduce a set of functions G
as follows:
Definition A real function F 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.
Using the fluid methodology, we can define a function Φ(t)based on the definition of the function Φn in (9). We set

FV (Φ(t)) = F (φ1 (t), ..., F (φK (t) .
We define Γ = [γ (i,j) ] as the diagonal matrix with γ (k,k) =wk , and let Γ−1 be the inverse of Γ. Further, we write thescalar product for two vectors v1 and v2 as hv1 , v2 i = v1 v2T .
For every function F ∈ G, we define a scheduling algorithm
M W M F as follows: At each time t, the scheduling algorithm
M W M F chooses the schedule π F which is defined by thefollowing equation:no
π F (t) = arg max hπ, ḞV (φ(t))i .
(14)πFinally, we define the Lyapunov function:
G(t) = hI, Ḟ1 (Φ(t))i,

B. The fluid methodology
The main proof of this section will make use of the fluid
methodology as introduced in [6], [7]. As in [2], we consider
an extension of the fluid model to a network of switches. Basedon the definitions introduced in section II A, we define threevectors as follows:
X(t) = (X1 (t), ..., XK (t)) denotes the number of packets inthe logical queues at time t, D = (D1 (t), ..., DK (t)) denotes
the number of packet departures from the logical queues until
time t and A = (A1 (t), ..., AK (t)) denotes the number ofpackets arrivals at the logical queues until time t. We defineΠ = {π} as the set of all possible network-wide matchings anddenote a specific scheduling algorithm by F. For all π ∈ Π,
we denote by T F
π (t) the cumulative amount of time that thematching π has been used up to time t by the algorithm F.
Obviously, T F
π (0) = 0 ∀π ∈, ∀F. Using (2), we obtain thefluid equations of the system as follows:
X(t)

=

D(t)

=

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

(11)

t.

(13)

(12)

where F1 (x) = ΓFV (x). Now, we can formulate the main
result of this section:
Theorem 1: For any real function F ∈ G, a networkof IQ/CIOQ switches that implements a M W M F achieves
100% throughput.

D. Proof of theorem 1k

We note that by (7) lim fk (t) → t/wk , and that d (t) →t→∞∞ for t → ∞. Thus,
k

d (t)
+ C.
wk

(15)

Φ̇(t) = I − Ḋ(t)Γ−1 .

(16)

φk (t) → t −We can write (15) as:

We want to show that ∀t ≥ 0,
Φ(t) ≤ B,π∈ΠX

TπF (t)=π∈Π

The first equation models the evolution of the logical queues,
whereas the second equation counts the total number of
departures from the V OQs. The third equation reflects thefact that in each timeslot each input is connected to some
output.

(17)

for a certain constant B > 0. We see that ifdG(t) ≤ 0
dt∀t > 0, then holds
G(t) ≤ G(0),

(18)

5

which in turn implies (17) for a certain B > 0. Thus, we willshow (18) in order to prove (17).
Now (18) follows from (12), (13), (14) and (16):
d
G(t)
dt

=
=
=
=

d
h1, F1 (Φ(t))idt
KX
wk Ḟ (φk (t))φ˙k (t)

k=1
K
X

k=1
K
X

||Dn ||IO ≤ 1,

wk Ḟ (φk (t))(1 − dk wk−1 )wk Ḟ (φk (t)) −K
X

dk Ḟ (φk (t))= hW, ḞV (Φ(t))i − hD(t), ḞV (Φ(t))i
≤ 0.

k

d (t)
+C
wk

≤

B.

(19)

Therefore,
k

d (t)
lim
= wk ,
i.e.,
t→∞
t
D(t)
lim
= W,
w.p.1,(20)t→∞twhich corresponds to the rate stability condition for X(t).
IV. N ETWORKS OF SWITCHES THAT DEPLOY DIFFERENTSCHEDULING POLICIESIn the previous section, a class of scheduling policies for
networks was presented. It was shown that each of thesepolicies provides stability for a network of switches where
all switches implement the respective scheduling policy.
It can now be asked if a network of switches in which
each switch deploys any of those policies achieves 100%
throughput. The answer is affirmative:
Theorem 2 A network of IQ/CIOQ switches where eachswitch deploys a M W M F policy for any F ∈ G achieves
100% throughput.
Proof: Assume that each switch in the network deploys anyof the switching policies M W M F1 , .., M W M FM . We divide
the switches in the network into the M groups GM , i ∈{1, .., M } where Gi contains the switches that deploy theswitching policy M W M Fi . Accordingly, we can divide thedeparture vector D(t) and the arrival rate vector W in M
subvectors, i.e., we write D(t) = (D1 (t), .., DM (t)) andW = (W1 , .., WM ). In order to prove the stability condition(20), it is obviously sufficient to show that ∀i ∈ {1, .., M }Di (t)= Wi ,
w.p.1.
(21)t
For each i ∈ {1, .., 4}, the relation (21) can be proved byapplying the proof of theorem 1 to the corresponding groupof switches Gi instead of applying them to the whole networkof switches. 
lim

t→∞

(22)

A maximal weight matching algorithm is defined for a setof positive weights P k , 1 ≤ k ≤ K, where Pk is the weightassigned to the logical queue q k , as follows:

The relation (17) implies that:0<t−∀n ≥ 1.

Further, we define ∀b, i, j, 1 ≤ b ≤ B, 1 ≤ i, j ≤ N,[
Sb,i,j := m : 1 ≤ m ≤ K, m ∈ QI (b, i) QO (b, j) ,

k=1

k=1

V. S TABILITY OF THE iN OCF ALGORITHM
The iOCF maximal weight matching scheduling algorithm
is described in [5] for a per-virtual output queue schedulingscheme. Here, we will expand this definition to a per-flow
based scheduling scheme.
We recall that the switching core is modeled as a crossbar
such that in every internal timeslot at most one packet can besent from the same input or to the same output, i.e.,

1) Initially, all logical queues q k , 1 ≤ k ≤ K, areconsidered 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 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
to step 2.
Using this definition of a maximal weight matching algorithm, we now define the iN OCF algorithm as the
maximal matching algorithm that uses the weights definedin (10). These weights denote the time a packet has already spent in the network. Thus, we call the algorithm
the N etwork Oldest Cell F irst algorithm - iN OCF. If the
network consists of only one switch, the iN OCF algorithm
is identical to the iOCF algorithm as defined in [5].
We show the following theorem:
Theorem 3: Assuming that at any time t, no two weights
Ḟ (φk (t)) are equal, the iN OCF algorithm is stable.
Proof: We follow the proof of theorem 3 in [14]. If wechoose F (x) = ex , then we know from theorem 1 that thecorresponding matching policy M W M EX P guarantees thestability of a network of input queued switches. Thus, in orderto show the stability of the iN OCF algorithm under theassumption that at any point in time no two logical queues
have the same weight, it is sufficient to show that under thisassumption the iN OCF and the M W M EX P algorithm are
identical. The identity of both algorithms is proved in exactly
the same way as lemma 3 in [14]. We note that the proofin [14] requires that the weights are always integers. The
definition of the weights in (10) satisfies this requirement. The
assumption that no two logical queues have the same weight isrealistic for large queue sizes due to the randomness of packet
arrivals.
VI. C ONCLUSIONSIn this paper, we investigate local scheduling policies for
networks of input-queued switches. We show that there ex-

6ists a large class of switching policies that guarantee thestability of a network of input-queued switches. It is also
proved that a network of input-queued switches where eachswitch implements any scheduling policy out of this class ofpolicies achieves 100% throughput. Finally, it is shown thatthe iN OCF maximal weight matching algorithm can stabilize
a network of input-queued switches under the assumption thatno two logical queues have the same weight at any time.
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] Andrews, M., Zhang, L., Achieving stability in networks of input queued,
Proc. of Infocom 2001, Anchorage, Alaska, April 2001.
[4] Benson, K., Throughput of crossbar switches using maximal matchingalgorithms, Proc. of IEEE ICC 2002, New York City.
[5] Charny, A., Krishna, P., et al., Algorithms for providing bandwidth anddelay guarantees in input buffered crossbars with speedup, Proc. of
IWQoS, Napa, CA, 1998.
[6] Dai, J.G., Prabhakar, B., The throughput of data switches with andwithout speedup, Proc. of IEEE Infocom 2000, Tel Aviv.
[7] Dai, J.G., Stability of fluid and stochastic processing networks, Miscellanea publication n.9, Centre for Mathematical Physics and Stochastic,
Denmark (http://www.maphysto.dk), Jan. 1999.
[8] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., Bounds on average
delay and queue size averages and variances in input-queued cell-based
switches, Proc. of IEEE Infocom 2001, Anchorage, Alaska.
[9] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., On the stability of
input-buffered cell switches with speed-up, Proc. of IEEE Infocom 2001,
Anchorage, Alaska.
[10] Leonardi, E., Mellia, M., Neri, F., Marsan, M.A., Stability of maximal
size matching scheduling in input queued cell switches, Prof. of IEEE
ICC 2000, New Orleans.
[11] McKeown, N., Mekkittikul, A., Anantharam, V., Walrand, J., Achieving
100% throughput in an input queued switch, Proc. 39th Annual Allerton
Conference on Communication, Control and Computing, Oct. 2001.
[12] Keslassy, I., McKeown, N., Achieving 100% throughput in an input
queued switch, IEEE Transactions on Communications, vol. 47, no. 8,
Aug. 1999, 1260 - 1272.
[13] Shah, D., Kopikare, M., Delay bounds for approximate maximum weightmatching algorithms for input queued switches, Proc. of IEEE Infocom
2002, New York City, June 2002.
[14] Shah, D., Stable Algorithms for input-queued switches, Proc. 39th Annual Allerton Conference on Communication, Control and Computing,Oct. 2001.