Distributed scheduling policies for networks ofswitches with a configuration overhead
Claus Bauer
Dolby Laboratories, San Francisco, CA, 94103, USA,cb@dolby.com

Abstract. Optical switching cores are fast gaining importance for deployment in internet switches/routers. The reconfiguration of these switches
requires a large timely switching overhead. The design of efficient algorithms that take into account the configuration overhead has been widely
researched. However, all previous research solely focuses on switching algorithms that optimize the performance features of a single switch withconfiguration overhead. This paper is the first which designs classes ofswitching policies for a network of switches with a configuration overheadthat guarantee the stability of the network. We also show that networksof switches with configuration overhead are stable if different classes ofpolicies are deployed at different switches simultaneously.

1

Introduction

The introduction of new optical transmission technologies such as Dense Wavelength Division Multiplexing (DWDM) have dramatically increased the transmission capacity of optical fibers. As a consequence, there is a need for switches
and routers that work at or above the speed of the high-speed optical links connecting them.
Today, most high-performance routers/switches use an electronic core that deploys a Virtual Output Queueing Scheme and a crossbar switching core. It is notexpected that electronic switches will be able to meet the performance requirements imposed by future optical transmission capacities. Thus, optical switchingcores have increasingly gained importance. At this time, it is neither possible tobuffer packets in the optical domain nor to evaluate the packet header in the
optical domain. Therefore, most researchers ([7], [12])) propose hybrid electronicoptical architectures: Packets that arrive on optical input links are converted
into an electric signal. The header evaluation and the eventual buffering are
performed in the electronic domain. In order to forward the packet through theoptical switching core, the packet is reconverted into the optical domain andsent through the switch. If the switch uses output buffers, the packet is again reconverted into electronics at the output, buffered electronically, and reconverted
into optics when it leaves the switch. Obviously, it is desirable to find ways toperform the header evaluation and buffering in the optical domain in order tosave the numerous electronic-optical and optical-electronic conversions.
The MEMS technology is a favorite candidate for an optical switching core12([6],[13]). Compared to electronic switches, that reconfigure themselves in few
nanoseconds or less, the reconfiguration time of a MEMS based switch is typically quoted as being between 1 and 10 ms. Depending on the link speed, theseswitches take up to 20,000 cell times to reconfigure. This long reconfiguration
time introduces large packet delays and requires scheduling algorithms that takethis configuration overhead into account and optimize the delay and loss characteristics of the resulting schedule.
Recently, various researchers have proposed different scheduling algorithms forswitches for a configuration overhead. Two approaches can be distinguished:
In the Timeslot Assignment based approach ([9], [10], [15]), incoming traffic is
accumulated during a predefined accumulation period. During each cycle, thearriving traffic is buffered in an N × N traffic matrix. Using different algorithms,
the traffic matrix is decomposed into permutation matrices that determine theconfigurations of the switch. The Single Scheduling approach ([10],[11]) can beconsidered as a slow version of scheduling algorithms for switches without configuration overhead. Similar to packet-based based scheduling ([14]), a scheduleis generated and maintained for several timeslots. Most approaches require theswitching core to work at a speedup S > 1 compared to the linkspeed.
Previous research on scheduling algorithms for switches with configuration overhead has investigated scheduling algorithms that optimize the performance features stability and delay for a single switch. So far, no research on schedulingalgorithms that stabilize networks of switches with a configuration overhead
has been performed. For switches without configuration overhead, it has beenshown in [3] for the example of a maximum weight matching algorithm ([7])
that scheduling algorithms that guarantee the stability of individual switches
do not necessarily guarantee the stability of networks of switches. Following theargument in [3], it can be shown that the Single Scheduling LQF + holding
algorithm proposed in [10] can lead to instabilities in a network of switches withconfiguration overhead.
For switches without configuration overhead, in [2] and [3], local scheduling algorithms that stabilize networks of switches, but require signaling traffic between
adjacent switches have been proposed. Only recently, in [1] a scheduling algorithm has been proposed that does not require signaling traffic, but stabilizes a
network of switches. This algorithm requires non-local information to be transported in the packet header.
This paper is the first effort to investigate local scheduling algorithms for networks of input-queued switches with a configuration overhead that stabilize theentire network.
The rest of the paper is organized as follows. In the next section, we develop amodel for a network of switches. In section 3, we define local scheduling policies and prove the stability of networks that deploy any of those policies at all
switches. In section 4, we prove that networks of switches that deploy different
classes of these policies simultaneously at different switches of the network arestable as well. We conclude in section 5.

3

2

Terminology and Model

2.1

Model of a network of queues

In this section, we follow an approach in [1] to describe our model of a queueing
system. We assume a system of J physical queues q̃ j , 1 ≤ j ≤ J of infinite
capacity. Each physical queue consists of one or more logical queues, where each
logical queue corresponds to a certain class of customers within the physicalqueue. Whenever a packet moves from one physical queue to another, it changes
class and therefore also changes logical queue. We denote a logical queue by
q k , 1 ≤ k ≤ K, where K ≥ J. A packet enters the network via an edge switch,travels through a number of switches and leaves the network via another edge
switch. We define a function L(k) = j that defines the physical queue q̃ j atwhich packets belonging to the logical queue q k are buffered. The inverse function
L−1 (j) returns the logical queues q k that belong to the physical queue q̃ j .
Throughout this paper, the time t is described via a discrete, slotted timemodel. Packets are supposed to be of fixed size and a timeslot is the time neededby a packet to arrive completely at an input link.
k
We define a row vector Xn = (x1n , ..., xKn ), where the k-th vector xn representskthe number of packets buffered in the logical queue q in the n-th timeslot. Wekdefine En = (e1n , ..., eKn ), where en equals the number of arrivals at the logicalkqueue q in the n-th timeslot. Analogously, we define Dn = (d1n , ..., dKn ), where
dkn expresses the number of departed packets from q k in the n-th timeslot. 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 from outside the systemor are forwarded from a queue within the system. Thus, we can write:
En = An + Tn ,where An = (a1n , ..., aKn ) denotes the arrivals from outside the system and Tn =(t1n , ..., tK)
denotesthearrivals from inside the system.
n
We define a routing matrix R = [ri,j ], 1 ≤ i, j ≤ K, where ri,j is the fraction ofcustomers that depart from the logical queue q i and are destined for the logicaljqueue
ri,j ∈ {0, 1},
P a deterministic routing policy,j there holds,
P q . Assuming
ri,j ≤ 1. We set ri,j 6= 0, if q follows q i along the route.
ri,j < 1,

1≤i<K

1≤j≤K

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 theStrong Law of Large Numbers. Thus,

lim

n→∞

n
P

Ai

i=1

n

=Λ

w.p.1,(3)

4

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 isgiven by W = Λ(I − R)−1 .
Finally, we give a stability criteria for a network of queues as proposed in [2].
Definition 1: A system of queues is rate stable if
n−1
1X
Xn
(Ei − Di ) = 0= lim
n−→∞ nn−→∞ ni=0

lim

w.p.1.

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

(j)

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

(5)

Model of a network of switches

In this section, we apply the terminology of the previous section to a network ofswitches. We assume that the switching core is an N × N input-queued or combined input/output-queued (IQ/CIOQ) switch that deploys a Virtual Output
Queue buffer structure ([7]. 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 theoutput queues of the switches because instability can only occur at the Virtual
Output Queues (see [1]).
We say that packets that enter the network via the input of a given switch
and leave the network via the output of a given switch belong to the same flow.
Packets belonging to the same flow travel through the same sequence of physicalqueues and are mapped to the same logical queues at each physical queue, i.e.,
a flow can be mapped biunivocally to a series of logical queues.
We assume that each logical queue behaves as a FIFO queue and assume
a per-flow scheduling scheme. It has been shown in [1] how stability results for
per-flow scheduling schemes can be used to design less complex and stable pervirtual output queue schemes.
The network consists of B switches and each switch has Nb , 1 ≤ b ≤ B, inputs and outputs. If the total number of flows in the system is C, we do not havemore than Nb2 physical queues and CNb2 logical queues at switch b. We can model1

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

5

the whole network of switches as a system of

P

1≤b≤B

CNb2 logical queues. For thesake of simplicity, we suppose that Nb = N, 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 the b-switch. Analogously, QO (b, i) denotes the set of indexes
corresponding to the logical queues directed to the i-th output of the b-switch.
We 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||IO = max|z m | .
|z m | ,b=1,..,B 
i=1,..,Nm∈QO (b,i)

m∈QI (b,i)

As we assume a deterministic routing policy, the necessary condition for ratestability given in (5) can 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 and routing patterns
that satisfy the condition (6). We will say that a network which is rate stable
under condition (6) achieves 100% throughput.

3

Local scheduling policies

3.1

Weight function

All scheduling policies introduced in this paper are matching policies. Anymatching policy is defined relative to a specific weight. For the definition of
the weights, we will make use of a family of real positive functions fk (x) : N →R, 1 ≤ k ≤ K, that satisfy the following property:
lim

n→∞
k

We define d (n) =P1
fk (n)= knw

w.p.1.

(7)dkm as the cumulative number of services at queue q k upm≤n

to time n. We define the weights of the queues q k s at time n byk

φkn = n − fk (d (n))Φn = (φ1n , .., φK
n ).

(8)

In [2], an example for fk (n) is given. The cumulativeof external arP function
akm . The inverse function
rivals for the logical queue q k is given by ak (n) =m≤n[ak ]−1 (p) maps the packet number p to the arrival slot. Setting fk (p) = [ak ]−1 (p),the weight φkn = n − [ak ]−1 (p) denotes the time the packet has already spent inkthe network. At its departure time n, the age of the p-th packet is n−[ak ]−1 (dn ).

6

3.2

The fluid methodology

The main proof of this section will make use of the fluid methodology as introduced in [4], [5]. As in [1], we consider an extension of the fluid model to a
network of switches. First, we define three vectors: X(t) = (X1,1 (t), ..., XN,N (t))
denotes the number of packets in the V OQs at time t, D = (D1,1 (t), ..., DN,N (t))
denotes the number of packet departures from the V OQs until time t andA = (A1,1 (t), ..., AN,N (t)) denotes the number of packet arrivals at the V OQs
until time t. We define Π = {π} as the set of all possible network-wide matchingsand denote a specific scheduling algorithm by S. For all π ∈ Π, we denote byTπS (t) the cumulative amount of time that the matching π has been used up to
time t by the algorithm S. Obviously, T Sπ (0) = 0 ∀π ∈ Π. Using (2), we obtainthe fluid equations of the system as follows:
X(t) = X(0) + Λt − D(t)(I − R),
X
πTπS (t),D(t) =(9)(10)

TπS (t) = t.

(11)

π∈Π

X

π∈Π

The first two equations model the evolution of the logical queues, whereas thethird counts the total number of departures from the V OQs. The third equationreflects the fact that in each timeslot, each input is connected to some output.
3.3

Maximum weight matching policies

In this section, we define a class of maximum weight matching policies thatguarantee the stability of a network of IQ/CIOQ switches with configuration
overhead. We introduce a set of functions G as follows:
Definition A real function F is said to belong to the set G ifa) Ḟ(x) exists for all x > 0.
b) F and Ḟ(x) are strictly monotonically increasing, non-negative and F(′) = ′,Ḟ(0) = 0.
c) Ḟ satisfies a Lipschitz condition: ∃CF s.t. |Ḟ (x)− Ḟ(y)| ≤ CF |x−y|, ∀x, y ∈ R.
Using the fluid methodology, we define a function Φ(t) based on the definitionof the function Φn in (8). We set
F(Φ(t)) =K
X

F(φk (t)).

k=1

We define Γ = [γ (i,j) ] as the diagonal matrix with γ (k,k) = wk , and let Γ −1 bethe inverse of Γ. Further, we write the scalar product for two vectors v1 and v2
as hv1 , v2 i = v1 v2T . Following an idea in [1], we first define a scheduling policy
for input-queued switches without configuration overhead. For every function

7

F ∈ G, we define a scheduling algorithm M W M F as follows. At each time t, thescheduling algorithm M W M F chooses the schedule π F which is defined as:noπ F (t) = arg max hπ, Ḟ (φ(t))i .
(12)π

For fixed F, we denote the value of the matching achieved by M W M F as M (t) =hπ F (t), Ḟ (φ(t))i. Using this terminology, we now define a class of schedulingpolicies M W McF for switches with configuration overhead. As shown in fig. 1,
a switch operates in cycles of constant length. Each cycle consists of a configuza

zb

Configuration

Forwarding

za

zb

za

zb

Time

Cycle

Cycle

Cycle

Fig. 1. Operation mode of the M W McF algorithm

ration phase of length za -timeslots, during which the switch is reconfigured andno packets are forwarded, and a forwarding phase of length zb timelslots, during
which the switch configuration remains unchanged and packets are forwarded.
Scheduling decisions are made according to the policy M W M F at instants tn ,where tn+1 − tn = za + zb . The chosen schedule π F (tn ) is kept constant during
the interval [tn + za , tn+1 [. We set
Mc (t) = hπ F (tn ), Ḟ (φ(t))ifor t ∈ [tn , tn+1 [.

(13)

Now, we can formulate the main result of this section:
Theorem 1: For any function F ∈ G, a network of IQ/CIOQ switches withconfiguration overhead that implements a M W McF − policy, in which the weightφkn ofl queuem q k at time n is defined as in (8) , and which deploys a speedupbachieves 100% throughput.
S ≥ zaz+zb
3.4

Proof of theorem 1

F
Before proving the theorem, we introduce the notion of a M W MmschedulF
ing policy for switches without configuration overhead. We define the M W Mmscheduling policy as the scheduling policy that applies an m − timeslots oldmatching of the M W M F scheduling policy to configure the switch: If we set
FFπm(t) = π F (t − m), then the M W Mm
policy calculates the match: Mm (t) =
′
′
F
m,F
hπm (t), Ḟ (Φ(t))i. We set Π(t) = {π : hπ , Ḟ (Φ(t))i = maxhπ, Ḟ (φ(t−m))i},π

and follow an argument in [4] to derive from (11):XF
M W MmṪπ(t) = 1.
π∈Π m,F (t)

(14)

8

Lemma 1
Mm (t) ≥ M (t) − C(W, m),(15)

where C(W, m) is a constant that depends on m and the matrix W.
kProof:
We note that by (7) lim fk (t) → t/wk , and that d (t) → ∞ fort→∞t → ∞. Thuskd (t)φ (t) → t −
,
wk
k

(16)

and


1
|φ (t + m) − φ (t)| ≤ m 1 +
wk
k

k



=: C(W, m),(17)

F
From (17) and the Lipschitz condition of the function Ḟ, we obtain hπm(t), Ḟ (Φ(t))i ≥FFFhπm (t), Ḟ (Φ(t−m))i−KCF C(W, m), and hπ (t), Ḟ (Φ(t−m))i ≥ hπ (t), Ḟ (Φ(t))i−F
KCF C(W, m). Further, by (12) hπm(t), Ḟ (Φ(t − m))i ≥ hπ F (t), Ḟ (Φ(t − m))i.
Combining the estimates, the lemma follows with C(W, m) =: 2KCF C(W, m).
We note that by (13) and lemma 1,

Mc (t) ≥ M (t) − C(W, za + zb ).

(18)

For technical reasons, we first prove theorem 1 for the case za = 0 and then show
the general case za > 0. We define the Lyapunov function: G(t) = hI, F1 (Φ(t))i,where F1 (x) = Γ F(x). By (16),Φ̇(t) = I − Ḋ(t)Γ −1 .

(19)

We want to show that for an absolute constant B > 0 there is ∀t ≥ 0,||Φ(t)||1 ≤ B,

(20)

where || ||1 denotes the L1 norm. Noting that G(0) ≥ 0, we see that ifdG(t) ≤ 0dt(21)∀t such that hI, Φ(t)i ≥ K0 for a fixed K0 > 0, then ∀t ≥ 0, there holds G(t) ≤max h1, Ḟ (L)i, which in turn implies (20) for a certain B > 0. Thus, we derive
L∈RK ,
hI,Li≤K0(21), from (10), (14), (18), and (19):d
G(t) = h1, F˙1 (Φ(t))Φ̇(t)idt= h1, Γ Ḟ (Φ(t))i(I − Ḋ(t)Γ −1 ) = h1, Ḟ (Φ(t))(Γ − Ḋ(t))
X
M W MzFa +zb
˙Ṫπhπza +zb (t), F(Φ(t))i= hΓ, Ḟ (Φ(t)i −π∈Π za +zb ,F (t)≤ hΓ, Ḟ (Φ(t)i − hπ F (t), Ḟ (Φ(t))i + C(W, za + zb ).

(22)

9

As by (6),||W ||IO < 1, we argue as in [7] to find a W1 satisfying ||W1 ||IO < 1
and W ≤ (1 − ǫ)W1 for ǫ > 0. We define Γ1 based on W1 analogously to Γ . We
know from [7] that (12) implies hΓ1 , Ḟ (Φ(t))i < hπ(t), Ḟ (Φ(t))i. Thus, by (22):d
G(t) ≤ hΓ1 , Ḟ(Φ(t))i − hπ(t), Ḟ (Φ(t))i − ǫhΓ1 , Ḟ (Φ(t)i + C(W, za + zb )dt≤ −ǫ min wk max Ḟ(φk (t)) + C(W, za + zb ).
1≤k≤K
wk >0

1≤k≤K

As Ḟ was supposed to be non-negative and strictly monotonically increasing,k(21) follows. The relations (16) and(20) implies that: 0 < t − dw(t)+ C ≤ B.
kk

Whence, limt→∞ d t(t) = wk , i.e., limt→∞ D(t)= W, w.p.1, which correspondstto the rate stability condition for X(t).
Following an argument in [14], we now treat the general case za > 0. For any
switch that operates with a speedup S and has a configuration period of lengthza = 0, the equation (11) changes toX
TπF (t) = St.
(23)
π∈Π

a
of the bandwidth is lost during the
As for the M W McF policy a fraction zaz+zbb
configuration phase, we adjust the RHS of (23) by a factor of zaz+z
and obtainb
P Fzb
the equality
Tπ (t) = S za +zb t. Differentiating this equation, we follow anπ∈Πargument in [4] as in the derivation of (14), and find that for S > za + zb /zb ,Xπ∈Π za +zb ,F (t)M W MzFa +zṪπb(t) = Szb
> 1.
za + zb(24)

Arguing as for za = 0 with (24) instead of (14), the theorem follows for za > 0.

4

Networks of switches that deploy different schedulingpolicies

In the previous section, we introduced scheduling policies for networks that provide stability for a network of switches where all switches implement the samescheduling policy. Here we prove that a network of switches in which each switch
deploys any of those policies also achieves 100 % throughput.
Theorem 2 A network of IQ/CIOQ switches with configuration overhead where
each switch deploys any M W McF policy, F l∈ G, inm which the weight is definedbachieves 100% throughput.
as in (8), and which deploys a speedup S ≥ zaz+zb
Proof: We divide the switches in the network into M groups Gi , i ∈ {1, .., M }where Gi contains the switches that deploy the switching policy M W McFi . Accordingly, we can divide the departure vector D(t) and the arrival rate vector W
in M subvectors, i.e., we write D(t) = (D1 (t), .., DM (t)) and W = (W1 , .., WM ).

10In order to prove rate stability, it is obviously sufficient to show that ∀i ∈{1, .., M }, limt→∞ Dit(t) = Wi , w.p.1. This relation can be proved by applying
the proof of theorem 1 to each group of switches Gi separately.

5

Conclusions

This paper investigates scheduling policies for networks of switches with a configuration overhead. It proposes a class of switching policies that are based on
maximum weight matchings. It is shown that network of switches that deploybeither one or any mixture of those policies with a speedup of S ≥ ⌈ zaz+z⌉ achieveb
100% throughput.

References
1. Ajmone, 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.
2. Ajmone, M.,Leonardi, E., Mellia, M., Neri, F., On the throughput achievable byisolated and interconnected input-queued switches under multicalss traffic, Proc. of
Infocom 2002, New York City, June 2002.
3. Andrews, M., Zhang, L., Achieving stability in networks of input queued, Proc. of
Infocom 2001, Anchorage, Alaska, April 2001.
4. Dai, J.G., Prabhakar, B., The throughput of data switches with and without speedup,
Proc. of IEEE Infocom 2000, Tel Aviv.
5. 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. 9.
6. Lin, L.Y., Micromachined free-space matrix switches with submillisecond switchingtime for large-scale optical crossconnect, OFC Tech. Digest, 1998.
7. Keslassy, I., McKeown, N., Achieving 100% throughput in an input queued switch,
IEEE Transactions on Communications, vol. 47, no. 8, Aug. 1999, 1260 - 1272.
8. Keslassy, Chuang, S.T., Yu, K., Miller, d., Horowitz, M., Solgaard, M., McKeown,N., Scaling Internet Routers Using Optics, Proc. of ACM SIGCOMM, Karlsruhe,
Germany, Aug. 2003.
9. Li, X., Hamdi, M., λ-adjust algorithm for optical switches with reconfiguration
delay, Proc. of ICC’03, Anchorage, Alaska, May 2003. New York City, June 2002.
10. Li, X., Hamdi, M., Design and analysis of scheduling algorithms for switcheswith reconfiguration overhead, Proc. of High Performance Switching and Routing(HPSR’03), Torino, Italy. June 2003.
11. Li, X., Hamdi, M., Analysis of reduced rate scheduling for switches with reconfiguration overhead, Proc. of Global Communications Conference (Globecom’03), San
Francisco, Dec. 2003.
12. McKeown, N., Optics inside Routers, Proc. of ECOC 2003, Rimini, Italy, September 2003.
13. A. Neukermans and R. Ramaswami, MEMS Technology for Optical Networking
Applications, IEEE Communications Magazine January 2001, p.62 - 69.
14. Shah, D, Gangali, Y., Keshavarzian, A., Input-queued switches: Cell switching versus packet switching, Proc. of IEEE Infocom 2003, San Francisco. April 2003.
15. Towles, B., Dally, W.J., Guaranteed scheduling for switches with configuration overhead, Proc. of Infocom 2002, New York City, June 2002.