Scheideler C. Universal Routing Strategies for Interconnection Networks

12.4 Proof of Theorems 12.3.1 and 12.3.3 191

Next we show that for all other distributions of the

mi

it holds that

t (6eLmi-1)m'-l-ei

H \BAt_i+ 1

i=1

(6eLt~

89 k]) 2

<- kB,St]

(12.1)

if all Ai > 40e2Lk

-- B

Consider increasing the number

mj

of worms at a stage j < t with

mj <

mi+l

by 1. Then two terms in the product in (12.1) change: the (i = j)-term

and the (i --j + 1)-term. Before increasing

mj,

these terms are

6eLmj_l

mj-1 --lj mj--ej+l

BAt_j+1) 6eLmj )

(12.2)

(

\BAt_ j

and after increasing

mj

by 1, they change to

6eLmj_l

mj_l-(tj+l)

(6eL(mj +

1) (m./+1)-(s

(12.3)

It holds (12.2) >__ (12.3)

6eLmj_l (mj+_l.)mJ-eJ+'(6eL(mj+l))

r BAt_j+1 >- \ mj \ --B-~t--j

6eL(2mj_l +

1) 2

.~= mj-1 > e 9

At_j+ 1 -- BA2_j

m j-1 40eLm2-x

r >e.

At_j+ 1 - BA2_j+I

40e2Lk

Since any distribution of the

mi

can be obtained from the initial distribution

above by increasing one of the

m{

by 1 again and again, the lemma follows.

[]

t+k--1

2t+k-1

Clearly, there are ( t ) < possibilities for choosing the ~1,..., ~t

t

such that

Y~i=l

gi = k - 1. Thus we get for Ai > 40~_L_.___..~k for all i that

P(t,k)

< (8L'V~k-12t+k_ 1

(6eLt~

89176

---- n-2 t (16L'C~ k-1

(6eLt~

89176

For any constant -y > 0, let

192 12. Protocols for All-Optical Networks

and

(2 + 7) log n

ko = +1

log (2 + 16-~-0 (D + 1))

T> I ,o~

((~+~

2~2 +~),O~o~+ ~ B ~+ 1))) + r,ogkol

If the routing takes more than T rounds then one of the following two cases

must be true:

1. There must exist an active embedding into a witness tree VV(t) with

t _< T and k E {ko,..., 2ko} different worms.

2. There must exist an active embedding into a witness tree W(T) with

k _< ko different worms.

-

32L.~ 40e;Lka } + D + L. Then we get:

Suppose that Ai _> max{~, B1ogn,

Pr[The routing takes more than T rounds]

< Pr[Case (1) holds] + Pr[Case (2) holds]

T 2ko ko

<- E E P(t,k) + E P(T,k)

t=log

ko k=ko k=T

~ ~n 2~(1~ ~ k-1

t----log ko k=ko

En

.2 T

k= T \ ~A ; ) C~7 ]

<

~ ~ n-2'(~-) '2§176 +

t=log

ko kmko

zo.~(~) o~

k:T

2e(++logn+B(LD--+ 11

n--~' n--q'

<_ ... < --~-+-~-_<n -~

Therefore the overall runtime is

T

E (At + 2(D + L))

t----1

= 0 D+L+-~

+ 1-~gn + logn ,

t=l

12.4 Proof of Theorems 12.3.1 and 12.3.3 193

w.h.p., which is bounded by

O(LB-----~-C+(1v~an+l~176 ( LlOgn ))

----ff--- + D + n ,

where a = C + B( D + 1) + 2 and/~ = 2 + B(D + 1). This completes the

proof of the upper bound of Theorems 12.3.1 and 12.3.3.

12.4.2 The Lower Bound

In this section we will prove the lower bound in Theorems 12.3.1 and 12.3.3.

We use a path collection that consists of the following two types of subcol-

lections.

- Let d = /~J + 1. The first type consists of n/(2 ov0-b-ff-ff) structures consist-

ing of ~ paths of length D that are connected as shown in Figure 12.4.

path4 ,-,

path

path2 ,,-,,\ , ~

i

path 1 \ " '--~

,/S;

I I I I I

0 d 2d 3d 4d # levels

Fig. 12.4. A type-1 structure.

In general, the ith path starts in level (i - 1)d for all i _> 0. Paths i and

i + 1 have a common edge from level i- d to level i. d + 1.

- The second type consists of n/(2C) structures each consisting of C identical

paths of length D.

We assume that along each of these paths one worm of length L >_ 2 has to

be sent.

We first compute how long it takes to route all worms in a type-1 structure.

In case of routing along shortcut-free paths using priority routers, we assume

that the worm traversing path i has rank i, and in case of conflicts worms

with higher ranks are preferred. In order to bound the number of ways to

assign delays and wavelengths to the worms such that conflicts occur, we

need the following lemma.

Lemma 12.4.5.

Consider an arbitrary round of the trial-and-failure protocol

with delay range A > L. Suppose that the worms traversing the first i + 1

paths are still active at the beginning of this round. Then with probability at

least f L-1 ~ i the worms traversing the first i paths are discarded.

k2BA/

194 12. Protocols for All-Optical Networks

Proof.

Let A be the delay range of the round, b-~rther let us denote the worm

traversing path j by

wj,

and its delay by 6j. Clearly, there are BA ways to

choose a wavelength and a delay for Wl. In the following we show that for

any delay 51 of worm

wi,

there are at least L~.__!1 ways to assign a delay 5i+1

to worm

Wi+l

such that

wi+l

blocks

wi.

According to the construction of the type-1 structure,

wi+l

starts/b~-~J +

1 levels after

wi.

Hence, if 6i+t <_ 5i + [~_!j then

wi+x

is at least one level

ahead of

wi

during the routing. On the other hand, if 5i+1 _> 6i - /b--~J

then

wi+l

is at most L - 1 levels ahead of

wi

during the routing. Since

l{6i - L~-~J,...,& + LL~J} n [A]I > [~J + 1 > ~ for A _> L, the

number of ways to assign delays to

Wi+l

such that

wi

is blocked by

wi+l

is

at least L-1

2

Thus altogether there are at least

BA(b_~)i

ways to choose delays and

wavelengths for the worms such that the worms traversing the first i paths

are discarded. Hence this happens with a probability of at least

BA(h~-!)i _ (L_I~ i

(BA)i+I \ 2BA ]

D

Consider now the situation that it takes t + 1 rounds to route the worms

traversing the first t + 1 paths in a type-1 structure. This could happen, e.g.,

if in round i only

wt-i+2

is able to reach its destination, and the worms

wl,... ,wt-i+l

are discarded. According to the lemma above, for L > 2 the

probability of such an event is at least

'( L-i

H (B(A i +

L))t-i+2 = H \ 2BF,5~. ~ L) ] ' (12.4)

i=1 /=1

where A~ > 1 is the delay range for round i. Clearly, the number of time

steps necessary for the t rounds is at least

12(~ti=l (Ai + D + L)).

Given a

fixed A =

~ti_ 1 Ai,

the product in (12.4) gets minimal if Ai + L = ( t - i +

1)(A + t. L) / (~-~1) for all i E { 1,..., t}. This is shown in the following lemma.

Lernma 12.4.6.

Consider xl,...,xn E R+ with y = ~in=lxi. Then, for

n n+l

every a E

[O,y], YIi=l(Xi q-or) ~

gets maximal if xi + a = i(y + n.a)/( 2 )

for all i E

{1,...,n}.

Proof.

For n = 1, the lemma is trivially true. We will show by complete

induction on n that the assumption above is also true for n > 1. Suppose

= n ( 2 )) is the

that we have already shown that

f(y,n) 1-Ii=l(i(y + na)/n+l i

maximal value the product of the

(xi + (~)i

can reach. Then we want to find

the

Xn+l + a

for which

f(y -

Xn+l, n)- (Xn+l + a) n+l gets maximal. Clearly,

f(y -

Xn+l,

n) .

(Xn+l +

(9/) nq-1 ~---

[,~+I~

q'- or)n+1

(Y -

Xn+l + '. (Xn+l 9 g(n) , 02.5)

12.4 Proof of Theorems 12.3.1 and 12.3.3 195

where

g(n)

is a function that only depends on n. Taking the logarithm yields

g(.))

log ((y-

Xn+l

+ na)~ : J 9 (Xn+l +

= (n~l) log(y-Xn+l+na)+

(n + 1)log(xn+l + oL) + logg(n) .

(12.6)

Since a maximum of this function is also a maximum for the function in

(12.5), it remains to determine the maximum of the function in (12.6). As

(12.6) is a convex function, this can be done by finding the

Xn+l

for which

the derivation of (12.6) is 0.

_(n+ 1) . 1 + n+l

2 y

-- Xn+ 1

"-~ nol Xn+ 1 -~- Ol

Xn+ 1 --~ Ol _

y

- Xn+ 1 "4- nol

n + 1 (n~l)

r

r Xn+l

~- G

=

=0

(n + 1)(y + (n + 1)a)

1

n+l

(5)

(n + 1)(y + (n + 1)c 0

n+2

(2)

Hence the

xi

with i _< n have to be chosen such that

n

E(xi + a) = y + (n +

1)a - (n + 1)(Y,+2 + (n + 1)a)

, (2)

According to the induction hypothesis,

I]in=l(Xi "~-a)

i

gets maximal if, for

every i E {1,...,n},

Xi + C~ =

i(y

-

Xn+ 1 -~- riG)

n+l

(2)

i (Y-- ((n+l)(y+(n+l)a) --C~)

(.~2)

n+l

/("2+2)-(n+1) ("+2)-(n+1) 9 (n + 1)(~)

i\ (.+21 .y+

i(y+(n+l)a)

n+l

From this the lemma follows. []

196 12. Protocols for All-Optical Networks

Let /~ :

A/t.

Since there are n/(2~) type-1 structures, and each

structure has a probability of at least

t (

(L- 1)(t+ 1)

~t-i+l ~ L-1 ,~ t2

II 2B.2(t

i+I)(A+L)] > \4B(A+L)]

i=l

to have active worms after t rounds, the expected number of type-1 structures

that have active worms after t rounds is at least

n L-1

2 ov~-~ 4B(A+L) <1 r t>

-- log (4B(L~_+L))

Hence the expected number of rounds that are needed to route all worms in

all type-1 structures is at least

f2 ( r /~ /L+2) n)

In order to bound the time needed to route all worms in the type-2 structures,

we distinguish between the cases C >_ 2 l~ and C _< 2 iv/i~ n

Case C <~ 2 l~

Note that any routing protocol needs at least ~(L_~ + D + L) steps to route

all worms in a type-2 structure. Therefore the expected number of steps the

protocol needs to route all worms is at least

Since the runtime bound gets minimal for some z3 chosen in O(~- + D + L),

the expected runtime of the protocol is at least

where a = C + B(~- + 1) + 2. Let ~ = a/C + 2. Since C <_ 2 ]~ it holds

that 1V/~ n <_ loglogn only if B( D + 1) _> 2 ~~176176 >> C. In this

case, however, log ~ = O(log a), that is, 1V~ a n _> log log~ n. Therefore we

arrive at an expected runtime of the protocol of at least

time steps.

12.4 Proof of Theorems 12.3.1 and 12.3.3 197

Case C' > 2 l~

Let Ci be the minimum over all type-2 structures P of the number of worms

that are still active in P after i rounds. Then the following lemma holds.

Lemma 12.4.7.

For every t >__ 2 and L(Q +

2)

<_ A1,..., At_ 1 <_ /~ with

~/( 32BZ~ ~2'-1-1

"~(L---=7~" _> 71nn

it holds that

w.h.p.

32B/~ ~ 2t-1-1

(L-1)C /

Proof.

For t -- 1, the bound on Ct trivially holds. Suppose that the bound

above for Ct is true for some t _> 1. Then we want to show that, if At < /~

(~,1( 32B• ~2t--1

and v,,~, > 71nn, then we get

Ct-{- 1 _~ 2,-1

( 32Bz~

(L-De]

w.h.p. Assume in the following that ~/(

32BA

~2'-1 > 6[alnn] for some

v/x (L_I)C/

fixed constant c~ > 1. Consider any fixed type-2 structure P. Let wx,...,

we

be the worms participating in round t that use this type-2 structure, c _>

C/( 32B/~ ~2t-1-1

-, (L--Z=-~" . Further let the binary random variable Xi = 1 if and only

if wi fails to reach its destination in round t, and the binary random variable

Di

= 1 if and only if

wi

chooses a startup delay in {L,..., At - 1} in round t.

Then

X = ~iC=l Xi

is a random variable denoting the path congestion at P

after round t. In order to bound

)-~ic=l Xi,

we need the following proposition.

Proposition 12.4.1.

For any

{il,...

,it} C

{1,...

,c/2} with ~ <

2[alnn]

it holds

j=l j=l - \ 4B/~ ]

Proof.

In case of using priority routers, suppose that the priorities of the

worms are chosen in such a way that rank(w1) < rank(w2) < ... < rank(wc),

that is, wc has the highest priority. Let W :

{wc/2+1,... ,wc}.

For all i E

{1,..., c}, let

Ei

be the event that

wi

fails because of a worm in W and

Fi

be the event that

Ei

is true under the assumption that

Di

-- 1. Then it holds

for any subset {Q,...,it} C_ {1,...,

c/2}

that

Pr Xi~=llHDis =1 _>Pr Fit

j----1 j=l =i

In order to proceed with our calculation, we need the following claim.

198 12. Protocols for All-Optical Networks

Claim 12.4.1.

t

Pr[Fr

A... A

Fi,]

>_ H

Pr[F,2I

.

j=l

Proof. Let ,4 be the set of all assignments A E ([B] • [At])c/2 of wavelengths

and startup delays to the worms in W. Since the worms Wil,..., wit choose

wavelengths and startup delays independently at random, we get

Pr[Fi, I

F,l A... A Fit_l]

Pr[Fi, A... A Fi,]

Pr[Fil

A... A Fil_l]

Pr[Fi I A... A

Fi, I A]

AE.A

Z Pr[Fil A... A

Fir I A]

AE,,A

s

II Pr[F~ I A] ~ (Pr[Fi, I A]) t

AE.A j=I AEA

t-1 Z (Pr[F/, I A]) t-1

AE.A j=I

To proceed with our calculation we need the following inequality (see [Ho87],

p. 226).

Claim 12.4.2 (Chebychev). If al ~_ a2 >_ ... >_ an >_ 0 and bl >_ b2 >_

9 ..bn >_ 0 then

n X

Hence for every / _> 2 and xl ..., xn >_ 0 with ~"~i=1 i > 0 it holds

E,_-i

n X~ 1 ~n

>

- )

xi 9

n t-1 - n

Ei=I

Xi

i=1

t-1 and bi = xi.) Thus we get

(Choose ai = x~

Pr[Fr I Fr A .. A Fi, 1] > 1 ~ Pr[Fr I A] = Pr[Fr

9 - - IAI

and therefore

t

Pr[Fi,

A... A

Fi,] >_ II Pr[Fi#] .

j=l

[7

12.4 Proof of Theorems 12.3.1 and 12.3.3 199

It remains to bound Pr[Fi] for every i 6 {1,...,c/2}. Let El,6 denote

the event that a worm in W chooses wavelength f and a startup delay in

[6 - 1, 6 - (L - 1)]. For every i 6 {1,..., c/2}, let

fi

denote the wavelength

and 6i denote the startup delay chosen by worm

wi.

Then we can show the

following claim.

Claim 12.4.3.

If there are ~ worms wl, 1 < i < c/2, for which Ef~,6~ is true,

then at least e worms are discarded.

Proof.

Let us choose any worm w in W that causes some, say a set W', of

these e worms wi to have a true Eft,64. Let 6 be the delay of w. Then either

all worms of W' are discarded because of w or w has been discarded and

also at least [W'[ - 1 other worms in W', since only one worm with a delay

in [b - 1,6 - (L - 1)] can survive. In both cases at least [W'[ worms are

eliminated. Summing over all worms in W yields the claim. []

Thus we can assume that

and therefore

Pr[--Ei I Di = 1]

Pr[Ef,,~,

I D,

= 1]

<

Pr[EilDi

: 1]

<_

For At > ~- we get

Pr[Fi]

(

= Pr[Ei Di=l] _> 1- 1 ~

c(L--1)~ c(L-

1) (L- 1)Ct

> 1- 1 4BAt ] = 4"B--~: >- -4-B-~t

Since At < z~, the proposition follows.

[]

Let the random variable Yi be defined

as Yi = Xi. Di.

Proposition 12.4.1

implies that we can consider the random variables

Y1,..., Yc/2 as

(2 [a In hi)-

wise independent with probability at least

Pr

Xi~=llIX/?i~ =1 >

4BAt ]

=I j=l

Pr[-~Ef,,~,

I D~

= 1]

12I (1-Pr [ uses f/ and a delay in ])wj

[6i-- 1, bi - (L - 1)] [ Di = 1

j=c/2-[-I

L-1

So altogether we get

200 12. Protocols for All-Optical Networks

At-L (L-1)C't > (L-1)G't

At 4B/~ - 8Bz~

if At > 2L. In this case we get an expected path congestion after round t of

E[X] >

Let # = c_t. (n-1)~, Then

2 8BA "

c/2 C't (L

-

1)(Tt

> T

i=l

2

>--

16BA

"

32B~'-- 2t-l-l'

---- 2"

( 32BA

~ 2t-l-l+2t-1-1+l

=2

32BA ~ 2t-1

(L-1)C )

In order to proceed with our calculation, we need the following result shown

in [SSS95] (see Theorem 5).

Proposition 12.4.2.

Let X be a sum of k-wise independent binary random

variables with # <

E[X],

then it holds for k < Le2#e-1/3j:

Pr[X _< (1 - e)#] <_ e -tk/2j

(~,/{

32Bzl ~2t-1--1

6[alnn~, we

Let ~ = ~. Since ---,(L--ZL-Y~, >- have 2~alnn 1 <_

e2~ue -1/3, Thus we get together with Proposition 12.4.2:

Pr Ix < C ]

-- ( S2B~- ~ 2t-1 __~

Pr [X < (1 - e)#]

e-alnn -- (1) a

Hence for a > 1 the path congestion after round t is at most _,, (L-1)C"

for all type-2 structures, w.h.p. []

Thus for any L > 2 and z~ > 1 it holds for the expected number t of rounds

to route all worms in type-2 structures that

32B(A+L(OIB+2)))2,_ <

71nn

(L--1)C

Scheideler C. Universal Routing Strategies for Interconnection Networks

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