Scheideler C. Universal Routing Strategies for Interconnection Networks

Подождите немного. Документ загружается.

170 11. Oblivious Routing Protocols

Proof.

Wit first prove part (a) of the Theorem.

Proof of Part (a): Suppose that

worms, q per input, have to be sent to

random outputs. Let ~ -- min(L, log N}. Then the worms can be given delays

such that the routing can be viewed as divided into [log

N/~J

independent

passes in which every input has to send out at most

q~ = [q/llogN/gJl

worms9 Therfore, we have to show that there exists a rank allocation such

that each pass takes O(-~ (q~.log 1/B N+log N)) rounds, w.h.p., each requiring

2 log N + L time steps9 In the following we do not only show the existence

but also describe a specific allocation that ensures the above routing time.

The ith worm (0 < i <

q')

starting at node

(XlogN_l,... ,

X0) on level

0 is assigned rank i 9 N + (x0,... ,XlogN-1)2. Thus, the rank of a worm is

essentially the bit-reversal number of its input node plus an offset. In the

following we identify a worm with its rank9 (Note that the ranks of all worms

participating in the same phase are distinct.)

For an integer m _> 1 with binary representation (... ,m2, ml,m0), we

define

5(m) = max{i _< logN I

(mi-1,... ,mo) ~-

0/} 9

(i(m) has the nice property that any two worms w and w ~ can not use the

same edge before level log

N - 6(IJ -

w]). Further the following two claims

can be shown that will be used in the further analysis.

Claim 11.1.1.

For any m,k E ~I with k < m, there are at most

(~)/2 i'k

possibilities to choose a subset

{Xl,...,

} C_ {1,..., m}

such that

min{(i(xx),

= i.

Proof.

Let m E IN be an arbitrary constant. According to the definition

of (i(i), for every i E {1,..., LlogmJ} there are at most [m/2iJ numbers

x E {1,...,m} with 6(x) _> i. Therefore there are at most ([m/2"J) choices

for {xl,.

}. Since for all j E {0, , k - 1} it holds that

m/2'-j

< ~ we

9 9 ' " " ~ ~r~--j --

get (%/2'j) < []

Claim 11.1.2.

For any k E g4 and any strictly decreasing function f : ~

I~ it holds that

k k

Z 2'(i)f(i) -< (logU + 1)

Zf(i) .

i=1 i=1

Proof.

Let k E Is/be an arbitrary constant. We first show that Y]~=I 2'(i) ~-

(log N + 1)k' for any k' 6 {1,..., k}. Since there are at most [k'/21J numbers

x E {1,...,k'} with

6(x) = i,

it holds

k' flog ~'] [ k, j 2mi,{i,log N}

i=1 i:I

11.1 The Trial-and-Failure Protocol 171

logN flog k'J [k']

-< E k'+ E 27 "N

i=1 /:log N+I

<: (logN+ 1)k'

(11.1)

Since f is strictly decreasing, we can show by induction that

k t k t

E 2~(i)f(i) ~ (logN + 1) E

f(i)

i~l i~l

for all k' > 1. The case k' = I is trivial. Suppose that k' _> 1 and 6(k'+1) = m.

If m < log N then

k'+l

i----1

(11.1) k'

<_ (logg+l) Ef(i)+(logg+l)f(k'+l)

i=1

k'+l

= (log N + 1) E

f(i) .

i=1

Suppose now that m > logN. Then we get from Inequality (11.1) that

Y]i=l

26(I) <- (logN + 1)k' - (m - (logN + 1)). Hence it holds

kt+l

E 2~(') f(i)

i----1

k !

_< (logN+ 1)E26(i)f(i ) +

i=1

(logN + 1-

m)f(k') +m. f(k' +

k'+l

< (logN+ 1) E

2~(i)f(i)

i=l

From this the claim follows.

[]

Suppose Wl < ... <

wB+l

are B + 1 worms. Then there are

N. (L 2mi"{6(~2-wl) ..... 6(ws+'-w~)}-lJ) B

ways to choose the destinations of the worms such that all B + 1 routing

paths share an edge, i.e. the worms can not reach their destination altogether

in the same round. This is because the worms r~,~ not meet before level

g = log N - min{5(w2 -Wl),...,

5(wB+l --Wl)},

and once the destination of

worm wl is fixed, the node in that level and the edge leaving it are fixed,

which means, that only L2t-lJ destinations can be chosen by the B other

worms.

Now, consider an arbitrary worm Wl with some fixed destination, and

let m be an arbitrary integer. Then the number of possibilities to choose B

172 11. Oblivious Routing Protocols

worms (M2,... ,03B+ 1 and their destinations such that Wl < w2 < ... <

WB <

wB+l = Wl + m, and all B + 1 routing paths share an edge, is at most

Z 2(min{~(w2-wl) .....

5(ws-wl),5(m)}-l).B

Wl<W2<...<a~l +m

<-- (Bmi)[5(~-12-i(B-I)'2(i-1)B+L

i:0

i=5(m)

~ 2-i(B-l)'2(5(m)-l)'B]

_< (Bin_ 1)26(m) (11.2)

This is because according to Claim 11.1.1 for every level logN - i there are

at most (Bin_l)/2 i(B-1) possibilities to choose B- 1 worms w2,... ,wB that

share an edge leaving that level, and

2 min{i'5(m)}-I

possibilities to choose a

destination for each of these worms and WB+l.

Now we are able to estimate the number of (s, B)-delay sequences. For

this purpose we have to count the number of ways to choose s 9 B + 1

worms o31,... ,

~)s.B+l

and their destinations such that 0 _< wl < w2 < ... <

ws.B+l < q'N

and such that for every 1 < i < s, the routing paths of the

worms

w~.S+l,Wi.B+2,...,

w(i+l).B+l

share an edge. Of course, there are at

most

q'N 2

possibilities to choose wl and its destination. Define R --

q'N,

and let

mi = wi.B+l -

W(i-1).S+l. Then it follows by repeatedly applying

Inequality (11.2) that the number of (s, B)-delay sequences is at most

q'N2" Z

~I (Bm~ 1) "26(m')

rnl,vn2,.. ,ms>--I

i=l

sW-

ml,-..,mJ->l i=l

mi_<R

=:Aa,R

We now show by induction on s that As,R _< (log N + 1)8 (R). For s = 0,

this inequality trivially holds. For s >_ 1, we have

R--I s--I

A.R -- E E II2 (m')

fia-s~l rnl,rn2,.-,ma--l~l

i----I

Z ~ni<R--m$--I

R--1

= Z 26(m) "

As-l,R-m

rn=l

R--1

-< Z 26(m) " (l~ + i)s-1 (R-l)

m----1

11.1 The Trial-and-Failure Protocol 173

R--1

(:-r)

< (log N + 1)*

m----1

= (logN+l)S(s R)

Since each worm chooses uniformly and independently at random one out

of N possible destinations, the probability that a worm is still active after

4e- q'. (log N + 1) 1/B + (a + 2) log(q'N)

T >

- B

= O( q''(l~176

rounds can be bounded by

q'N2" (T(BR 1)) "(logN + I)T" (RT) "N -TB

_< q'N 2 . (2e'q'N" (l~ + l)l/B) N

< (q'.N)-~ .

This yields part (a) of Theorem 11.1.3.

Proof

of part (b): Consider the problem of routing log a N worms from each

input node to random output nodes for any constant a > 0. Let us choose an

arbitrary subset of these worms of size

m >_ 7BN/log

N. We first bound the

probability P that all these worms can be routed simultaneously, i.e., they

can arrive at their random destinations in log N + L steps. In the following

we say that worms

collide

if more than B of them want to travel along the

same edge at the same time.

In order to cope with dependencies between the collision probabilities on

different levels we use an idea from Ranade

et al.

[RSW94] which is to divide

the butterfly into many small subbutterflies. Let k -- [log log N] and K = 2 k.

Then the first k levels consist of

N/K

small distinct subbutterflies. We denote

the number of worms starting in the ith of these subbutterflies by mi.

We first estimate the probability Pi that the mi worms do not collide

in one of the 2K edges leaving subbutterfly i. Let el,..., e2K denote these

edges. Further, let Ej denote the event that more than B worms want to

traveTaIon~ge

e j, ~

let E~ denote the event t-hat exactly B~+~I

worms want to travel along the edge ej. If

B + 1 <_ mi <_ 2KB

then we get

Pr[Ej] _> Pr[E~]

( 1 ~B+1(1 -

1'~ 'm-"-I

= (.+1)

174 11. Oblivious Routing Protocols

and therefore,

B+1<_m,

( mi

,~ B+I

3 -(m'-B-1)/2K

k 2K(B ~- 1)1

m.<2K. ( m~ ))B+ 1

- .3-B

-> 2K(B + 1

HPr -~Ejle__~I-~E,

-<HPr[-~Ej]

j=l j=l

B+I

exp (--mr "bl. (B

+ 1) -(B+I) 9 (6K) -B)

Now we can bound the probability P that in every subbutterfly i the mi

worms do not collide at edges leaving that subbutterfly. If there is at least

one subbutterfly in which more than

2KB

worms start, then we have P = 0.

Otherwise,

N/K

P <_

li P,

z=l

mi>_B+l

Let ~ denote the number of subbutterflies in which more than B worms start,

and let m' denote the number of worms that start in subbutterflies with more

than B worms. Then

N/K BN 6

m'= ~

mi>m----K-->_Tm.

i=I

Hence we get

~/~ ~/~

(~)'+' (6~) "+'

E mM~- > E _>e~

i=l i=l

mi>_B+l mi>_B+l

Thus, we can conclude that the probability that collisions occur at edges

leaving level k of the butterfly is at most

11.1 The Trial-and-Failure Protocol 175

f6m B§ 1 )

P g exp --e ~k-ff~- ] 9 (B q- 1) -(B+I) 9

(6K) -B

l<g/g

<_ exp(--(6/7).(7N)-B.mB+l.(B+

1)-(B+I))

We can repeat this argument to obtain upper bounds for the probability

of having no collisions in edges leaving levels 2k, 3k, 4k and so on. Since we

obtain all these bounds by using only information regarding the k levels in

front of the respective collision level, the probabilities for each of these levels

can be considered as independent. Hence the probability that the m worms

do not collide on their way through the whole butterfly is at most

(exp (-(6/7>. (7N> -B -m "+'- (B + l)-('+'>))L'~

< exp 21oglog/V: (ff-N-ffff:(-B + 1) B+I "

Therefore, the probability that there exists a set of

2) log2 logN.

lIB

m _> 7N. (2(, q- 10g N (B + 1) B+I)

worms that can be routed simultaneously is at most

log N. m B+I 1)B+f~ /

(NI? aN)

"exp (-21oglog/~:-(~--/~-~-~ +

log N. m B

< exp(m((otq-1)loglogN-21oglogN:(--~:-(B+l)B+l))

< exp(-m) .

As a consequence, the routing takes at least time

m \ B ~, log: log N ] ]

with probability at least 1- exp(-m). This proves part (b) of Theorem 11.1.3.

11.1.3 Further Applications

Applying Theorem 11.1.1 to node- and edge-symmetric networks gives the

following results.

Corollary 11.1.1.

Given any node-symmetric network of size N, diameter

D, and link bandwidth B there exists an online wormhole routing algorithm

176 11. Oblivious Routing Protocols

that routes N worms of length L, one from each processor, to random desti-

nations in

0 ( L'DI+I/sB + (1_~ +

1)(D+ L))

time, w.h.p., without buffering.

Corollary 11.1.2.

Given any edge-symmetric network of size N, diameter

D, degree d, and link bandwidth B there exists an online wormhole routing al-

gorithm that routes n worms of length L, one from each processor, to random

destinations in

0 ( L'DI+I/Bd.B + (~ + 1)(D +L))

time, w.h.p., without buffering.

Applying Corollary 5.3.2 and Theorem 5.1.1 yields the following result.

Corollary 11.1.3.

Given any bounded degree expander of size N, there ex-

ists an online wormhole routing algorithm that routes N worms of length L,

one from each processor, to random destinations in

o + +1)

time, w.h.p., without buffering.

11.2 The Duplication Protocol

The duplication protocol presented in Section 7.7 can easily he adapted to

the case of routing worms in arbitrary leveled networks. To be able to use

the same analysis, we require the worms to collide with each other only by

their heads. That is, if we want to route worms of length L, then their delays

have to be a multiple of L. Then we get the following result.

Theorem 11.2.1.

Given any leveled path collection 79 of size n with conges-

tion C, dilation D, and bandwidth {9 (log ( C. D ) / log

log(C.D)),

the duplication

protocol requires

log n. log log n'~

O (L (Dloglogn +C + ~-~(-~:-~ ]]

time, w.h.p., to route worms of length L along paths in 79 without buffering.

For example, if D > logn and C _> Dloglogn, Theorem 11.2.1 yields

a routing time of

O(L 9 C),

which is only a factor of

logC/loglogC

away

from the lower bound. For d-dimensional meshes and tori, combining Theo-

rem 11.2.1 with techniques in [LMRR94] yields the following result.

11.3 Summary of Main Results 177

Corollary 11.2.1.

Given any d-dimensional mesh of side length n and link

bandwidth B = O(log( dn) / log log( dn) ) there exists an online wormhole rout-

ing algorithm that routes N = n d worms of length L, one from each processor,

to random destinations in

log N log log N

O ( L ( d " n l~ l~ N + l-~g log~og( d : -~) ] )

time, w.h.p., without buffering.

For butterflies, Theorem 11.2.1 yields the following result.

Corollary 11.2.2.

Given a butterfly with N inputs and link bandwidth

O(lolg~176 ),

routing

qN worms, q from each input, to random outputs can

be done in time

0 (L(q +

log N- log log N)) ,

w.h.p., without buffering.

11.3 Summary of Main Results

At the end of this chapter, let us summarize its main results. After present-

ing upper and lower bounds for offline wormhole routing, we presented two

online protocols: the trial-and-failure protocol and the duplication protocol.

In particular, we could prove the following two results (see Theorem 11.1.1

and Theorem 11.2.1).

Suppose we are given an arbitrary simple path collection 79 of size n with

link bandwidth B, congestion C, and dilation D. Further let K >_

4e~C.

D -l+t/B, where

g = min{2L- 1,D}.

Then the trial-and-failure protocol

needs

o (L'C-BD1/B + (I-~ + I) (D + L))

steps, w.h.p., to route worms of length L along paths in 79 without using

buffers.

Given any leveled path collection 7 9 of size n with congestion C, dila-

tion D, and bandwidth

O(log(C.

D ) / log log( C .

D)),

the duplication protocol

requires

log. loglog

O(L(Dloglogn+C+

loglog(C. D)]]

time, w.h.p., to route worms of length L along paths in 79 without buffering.

We further showed how to improve the time bound of the trial-and-failure

protocol when applied to d-dimensional meshes, and how to remove random

ranks and delays when applied to butterflies.

12. Protocols for All-Optical Networks

In this chapter we present analyses of variants of the trial-and-failure proto-

col that can be run efficiently on an emerging generation of networks known

as all-optical networks (see, e.g., [Br90, CNW90, Gr92, Pe83, Ra93, IEEE94,

Ch95]). These networks promise data transmission rates several orders of

magnitudes higher than current networks. The key to high speeds in these

networks is to maintain the signal in optical form, thereby avoiding the pro-

hibitive overhead of conversion to and from the electrical form. (Traditional

networks use the electrical form to switch signals along routes, and to re-

store signals. Signals can be modulated electronically at a maximum bit rate

of the order of tens of Gps, while the optical fiber bandwidth is at least

25 THz [Ch95]. The high bandwidth of the optical fiber is utilized through

WDM (wavelength-division multiplexing, see Section 2.1): two signals con-

necting different source-destination pairs may share a link, provided they use

different wavelengths of light. The major applications for such networks are

in video conferencing, scientific visualization and real-time medical imaging,

high-speed supercomputing and distributed computing [Gr92, Ra93, DV93].

12.1 An All-Optical Hardware Model

In the following we consider routing elements that are capable of direct-

ing messages at different wavelengths to different destinations and detect-

ing collisions of messages. A routing element (or router in short) consists of

wavelength-selective switches and couplers.

The task of the switches is to direct different wavelengths to different

directions. Several types of optical switches have already been developed

[HC+93, BCFR96].

The task of the couplers is to combine the signals from many incoming

optical fibers into one outgoing optical fiber. Since we do not allow central

control, collisions might occur, that is, two or more signals from different

incoming fibers use the same wavelength. In our design of protocols we will

consider two different strategies to avoid collisions:

- If a message that arrives at a coupler uses a wavelength already used by

another message traversing the coupler, the new message is eliminated.

180 12. Protocols for All-Optical Networks

This can be realized with the help of detector arrays that tell the elec-

tronic control of the coupler which wavelengths are currently used, and

wavelength-selective filters at each incoming fiber.

- If a message that arrives at a coupler uses a wavelength already used by

another message traversing the coupler, the message with higher priority

is forwarded and the other suspended. This strategy is significantly more

difficult to realize than the first strategy. We consider it nevertheless to see

whether it would be worth to invest this effort or better use the first type.

We call a coupler using the first rule

serve-first coupler and priority coupler

otherwise.

The following picture illustrates how a 2 x 2 router can be built by switches

and couplers.

incoming ~ outgoing

signals ~ ~ signals

switch coupler

Fig. 12.1. A 2 • 2 router.

The number of wavelengths a router can handle is called the

bandwidth

the router and denoted by B. As defined for the coupler above, we distinguish

between two rules to avoid collisions in the router: the

serve-first rule and

the

priority rule.

12.2 Overview on All-Optical Routing

All-optical routing problems have been considered for two basic network mod-

els: the

non-reconfigurable

switchless

networks, and the

reconfigurable

net-

works. In the first class of networks, a fixed set of wavelengths is assigned

to every connection between any input and output of a router, whereas in

the second class switches axe allowed, that is, connections between the inputs

and the outputs of a router can change the set of wavelengths that are sup-

ported by them. The

elementary

switch can not direct different wavelengths

axriving at some input to different outputs, whereas the

generalized

switch

can do this. Figure 12.2 gives an example of a router for non-reconfigurable

networks and reconfigurable networks with elementary switches.

The routing protocols developed for the class of non-reconfigurable net-

works can be separated into two categories: the

single hop

strategies and