Scheideler C. Universal Routing Strategies for Interconnection Networks

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

7.4 The Growing Rank Protocol 89

rc'/8'+2K'~

ways to

to choose the delay packets. Finally, there are at most _..~ s,+l /

select the r~ such that 0 < rs,+l _< ... _< rl < r8,+1 + 2K' and rl < 2K. []

Since the packets choose their ranks independently at random, the prob-

ability that an (~', s', K')-delay subsequence is active is

1/K "'+1.

Thus

Pr[there exists an active (s

s',

K')-delay subsequence]

< n.D.C 8'.2 ~'+8'.28'+2K'.

-- g $!

If we set K > 8C and s' _> l' + 2K' + (j3 + 1) logn + logD, where/~ > 0 is

an arbitrary constant, then

Pr[there exists an active (~', s', K')-delay subsequence]

< n 9 D

9 2 2s'+t'+2K' 9

2 -3s'

= n 9

9 2 -a'+g+2K' < 1

_ _nB

With K' d K

2 D we get from Lemma 7.4.3 that d. D K_ = 2K and therefore

a = ~. Since any (s,~,K)-delay sequence can have at most 2D edges, it

holds that g' < 4__DD = d, which has to be ensured for our analysis to work.

Therefore the total delay s of the growing rank protocol is at most

2as' = 2--- d d+d.---l~+(k+l)logn+logD

= O(D+c+l~

This concludes the proof of Theorem 7.4.1. 0

7.4.2

Applications

The proof of Theorem 7.4.1 can easily be modified to prove the following

theorem by using Valiant's trick.

Theorem

7.4.2.

For any d-shortcut-~ee path system of size n with dilation

D and expected congestion C, d < D, any permutation can be routed using

the growing rank protocol in time O(C +

max{l, l~ }D),

w.h.p.

Since any simple path system in a network with girth g is ([2~] - 1)-

shortcut-free (otherwise there must exist cycles of length smaller than g in

it), we get the following result together with Theorem 5.1.1.

90 7. Oblivious Routing Protocols

Theorem 7.4.3.

Let G be an arbitrary network of size N with routing num-

ber R and girth g. Then there exists a path system such that any h-relation

can be routed in time O((h +

max{l, L~})R),

w.h.p.

Since the expander graphs constructed by Lubotzky

et al.

[LPS88] have

a girth of O(log N), this theorem implies that there exists an online proto-

col for these networks with runtime O(logN), w.h.p., for routing arbitrary

permutations, which is optimal. Theorem 7.4.2 applied to node-symmetric

networks yields the following result together with Theorem 5.1.2.

Theorem 7.4.4.

Let G be a node-symmetric network of size N with diame-

ter D. Then the growing rank protocol routes packets according to an arbitrary

h-relation in time O(h. D +

logN),

w.h.p.

Clearly, this time bound is optimal for permutation routing in arbitrary

bounded degree node-symmetric networks. Together with Theorem 5.1.3 we

get the following result for edge-symmetric networks.

Theorem 7.4.5.

Let G be an edge-symmetric network of size N with diam-

eter D and degree d. Then the growing rank protocol routes packets according

to an arbitrary h-relation in time

O(( h + 1)D + logN),

w.h.p.

7.4.3 Limitations

In case of bounded buffers, deadlocks can arise. Furthermore, the following

observation can be shown (see [MV96]).

Observation 7.4.1.

Suppose C satisfies logn/loglogn ~_ C ~_ n ~ for some

constant e < 1 and C >_ D/log

log

n. Then there is a simple path system of

size n with dilation D and congestion C such that the expected routing time

of the growing rank protocol is bounded by (2(C + D.

logn/loglogn).

The observation uses the following path collection.

Fig. 7.4. The counterexample.

Let A and B be two sets of packets of size

C/2

with source node ul and

vl respectively. The routing path of the packets in ,4 is

7.5 The Extended Growing Rank Protocol 91

?~1 -'~ U2 ~ Vl -+ V2 --~ V3 --~ V4 --~ ?-t3 --'~ 154 --~ U5 ~ ?~6 --~t V 5 ---~ 9 9 9

''' -'+ Vd-3 -'~ Vd--2 --'~ Vd--1 --'~ Vd --~ Ud--1 --~ ~d

and the routing path of the packets in B is

Vl --'~V2 -"~ Ul -"~ U2 ~ U3 "-~ U4 -"~ V3 --~V4 "-~ V5 "+ V6 -"~ U5 ~ ...

... ~ Ud--3 "~ Ud-2 "--~ Ud-1 --'~ Ud --'~ Vd-1 --+ Vd 9

Since this path collection is at most 4-shortcut-free, the observation

demonstrates that the analysis of the growing rank protocol above is nearly

tight. Observation 7.4.1 further shows that the growing rank protocol can not

be efficiently applied to arbitrary simple path collections. Note that it is still

an open problem whether efficient shortcut-free path systems exist for any

network. In case of shortest path systems, however, networks exist such that

any shortest path system has a much higher expected congestion than the

best simple path system (consider the union of a mesh and a complete binary

tree). In the following we describe a protocol that can even route packets in

optimal time along the path collection used for Observation 7.4.1.

7.5 The Extended Growing Rank

Protocol

In this section we describe an extension of the growing rank protocol that

can be efficiently used to route packets along the following type of path

collections. It has been presented in [MS95a].

Let ~o be an arbitrary path collection. P is defined to have

S stages

of shortcut-free path collections, if stage numbers in (0,..., S - 1} can be

assigned to the path collections in such a way that every path in ~o consists of

subpaths that belong to path collections of strictly increasing stage number,

and for all s E {0,..., S - 1} the collection of all subpaths with stage number

s forms a shortcut-free path collection. The

stage dilation

is defined as the

length of the longest path in any of these S subpath collections, and the

stage congestion

is defined as the maximal congestion in any of these subpath

collections, In the following we denote the stage congestion by C* and the

stage dilation by D*.

7.5.1 Description of the Protocol

The extended growing rank protocol works as follows. Initially, each packet

starting with a subpath that belongs to a shortcut-free path collection with

stage number q E [S] is assigned an integer rank chosen uniformly at random

from (q- 2K,..., q. 2K + (K - 1)}, where K is determined later. In each time

step, the protocol operates as follows.

92 7. Oblivious Routing Protocols

For each link with nonempty buffer,

- choose a packet p according to the priority rule,

- ifp changes from one shortcut-free path collection to another with

stage number qt, then choose a new random rank for p indepen-

dently and uniformly at random from the set {q~. 2K,..., q~-2K +

(K - 1)}, otherwise increase the rank of p by

K/D*,

and

- move p forward along the link.

This protocol yields the following result.

Theorem 7.5.1.

Suppose we are given an arbitrary path collection 7 ) of

size n that can be partitioned into S shortcut-free path collections with

stage congestion C* and stage dilation D*. Let K >_

8C*.

Then the time

the extended growing rank protocol needs to finish routing in 7 ) is at most

O(S(C* + D*) +

logn),

w.h.p.

Proof.

Similar to the proof of Theorem 7.2.1 we want to find a structure that

witnesses a long runtime of the extended growing rank protocol. First we

introduce the following definitions.

In the following, we denote the rank of a packet p while waiting to traverse

a link e by rank e (p). Let id : {set of packets} -+ [n] be an arbitrary bijective

function. We define the

ident-rank

of p at e as rankS(p) + ~ and denote

it by id-rank e (p). Note that in each round the ident-ranks of all packets are

distinct. This type of rank ensures that whenever a packet p delays a packet

p~ at a link e it holds id-ranke(p) < id-ranke(p~). The following lemma shows

that the rank of any packet at stage q can not be greater than 2(q + 1)K - 1.

Lemma 7.5.1.

Suppose p is a packet at stage q which is stored in the buffer

of link e in some round. Then

ranke(p) < 2(q + 1)K - 1.

Proof.

At the beginning of stage q, the rank of p is at most q 9 2K + K - 1.

Since the length of the routing path of p within one stage is at most D*,

the rank of p is increased by ~ for at most D* times. Thus, ranke(p) <

q.2g

+ K- 1 +D*-~ _< 2(q+ 1)g- 1. [:]

Note that the rank of any packet during any stage of the routing is

bounded above by

2S.K-1.

Analogous to the proof for the random rank pro-

tocol, the following delay sequence will serve as a witness for a long runtime

of the extended growing rank protocol.

Definition 7.5.1 ((s,s sequence).

(s,e)-delay sequence

con-

sists of

1. s not necessarily distinct

delay links el,...,es;

2. s + 1 delay packets

pl,p2,... ,Ps+l such that the path of pl moves along

the link ei and the link ei-1 in that order for all

i G {2,..., s},

the path

of Ps+x contains es, and the path of Pl contains el;

7.5 The Extended Growing Rank Protocol 93

3. s integers ~l,g2,...,~s >_ 0 such that

is the number of links on the

routing path of packet Pl from link el (inclusive) to its destination, for

all i E {2,..., s} s is the number of links on the routing path of packet

Pi from link ei (inclusive) to link ei-1 (exclusive), and ~-]~is=l gi <_ t; and

4. s integer keys rl, r2, . . . , rs+ l such that O <_ rs+x <_ "'" < r2 < rl < 2S.K.

We call s the length of the delay sequence. Further we say that a delay se-

quence is active, /f rank e' (Pi) = ri for all i 6 {1,..., s} and rank e" (Ps+l) =

rsq-1

Lemma 7.5.2. Suppose the routing takes T > 2S. D* or more rounds. Then

there exists an active (T- 2S. D*, 2S. D*)-delay sequence.

Proof. First, we give a construction scheme for a delay sequence. Let Pl be

a packet that arrived at its destination vl in step T. We follow Pl'S routing

path backwards to the last link on this path where it was delayed. We call

this link el, and the length of the path from Vl to el (inclusive) el. Let P2

be the packet that caused the delay, since it was preferred against pl. We

now follow the path of p2 backwards until we reach a link e2 at which P2 was

forced to wait, because the packet P3 was preferred. Let us call the length of

the path from el (exclusive) to e~ (inclusive) e2. We change the packet again

and follow the path of Pz backwards. We continue this construction until we

arrive at a packet Ps+l that prevented the packet Ps at edge es from moving

forward.

The path from es to vl recorded by this process in reverse order is called

delay path. It consists of contiguous parts of routing paths. In particular, the

part of the delay path from link ei (inclusive) to link el-1 (exclusive) is a

subpath of the routing path of packet Pi.

Let ri = rank e' (Pi) for all 1 < i < s and rs+l -- rank e" (Ps+l). Because of

the contention resolution rule we have 0 _< r s+ l <_ ... <_ r l , and r l < 2S.K-1

because of Lemma 7.5.1. Thus, we have constructed an active (s,e)-delay

sequence for every e _> ~-'~i=1 ~i.

Our next goal is to bound the sum of the ~i's. In addition to the ranks

rl,...,r~+l, we denote by r0 the rank of Pl at its destination. It follows

immediately from the protocol that ri + ~ 9 ~ <_ ri-1 for all 1 < i < s. As

a consequence,

, s D*

Z ei" ~K __~

r0 Lem=~7.5.1 Z ei _< (2S 9 K - 1)" ~- _< 25" D* . (7.4)

i=1 i----1

Since the delay sequence consists of ~,"=1 g~ moves and s delays, it covers

at most t = ~i=1 s + s time steps. It follows that

s (7.4)

t=~i+s <_ 2SD*+s.

i=1

94 7. Oblivious Routing Protocols

Suppose that

T >_ 2SD*.

If we stop the above construction at packet

PT-2SD*+I,

then we still have t _< T and therefore found an active (T -

2SD*,

2SD*)-delay sequence. []

In order to bound the probability that a delay sequence is active, we need

the following lemma.

Lemma 7.5.3.

If the routing paths of the packets are shortcut-free within

any stage, then the tuples (p, q) of delay packets p at stage q in the above

construction are pairwise distinct.

Proof.

Suppose, in contrast to our claim, that there is some packet p appear-

ing twice at some stage q in the delay sequence. Then there exist i and j with

1 <_ i < j < s + 1 and p = Pi = Pj.

Thus, the routing path of p crosses the

delay path at the delay links

ej-1 and ei

in that order.

Let m denote the distance from link

ej-1

(inclusive) to link

(exclusive)

in the delay path. If the routing paths within each stage are shortcut-free,

then the rank of p is increased at most m times while moving from

ej-1

ei, and hence

id-rank e' (p) < id-rank e'-I (p) + m. n-- 7 . (7.5)

On the other hand, each packet Pk+l delays the packet

at edge e~, and

consequently, id-rank e~ (Pk) > id-rank e~ (Pk+i) for all k E {1,..., s}. Further,

the length of the routing path of packet

Pk+l

from

ek+l

is ~k+l, and thus

the rank of Pk+l is increased by gk+l 9 fir. on its path from ek+l to ek for all

k E {1,...

,s-1}.Itfollowsthatid-rankeh(pk)

> id-ranke~+l (Pk+l)+~k+l'D-rK

for all k E {1,..., s - 1}. This yields

j-1 K

id-ranke'(P) > id-ranke'-l(P) + E ~k" 0-- 7

k:i+l

= id-rank ej-'(p) + m. D-- 7 . (7.6)

Since (7.6) contradicts (7.5), there is no packet that appears twice at some

stage in the delay sequence. [3

Lemma 7.5.4.

The number of different (s, g)-delay sequences is at most

n'(C')s(s+~)(s+2S'K) \

s+l

Proof.

We count the number of possible choices for each component:

There are n possibilities to determine the packet Pl and therefore the start-

ing point vl of the delay path.

Since ~-~'=1

gi < g,

there are at most

(s+t~

ways to choose the

gi's.

7.5 The Extended Growing Rank Protocol 95

[s+2S.K~

possibilities to choose the

ri's

such that

- Furthermore, there are ~ 8+1 ]

0 <_ rs+l <_ ... <_ rl < 2S. K.

- Once the

gi's

and

ri's

are chosen, there are at most (C*) 8 choices for the

delay packets p2,... ,ps+l- This is because a fixed rank r2 determines a

fixed stage for P2. Thus there are at most C* choices for the packet p2

given r2. We follow the routing path of

backwards for

steps, until we

reach link

e2.

Now we have at most C* choices for P3 given r3. We follow

again the routing path of this packet to link e3, and so on, until we reach

packet Ps+I.

So altogether, we find that the number of (s, g)-delay sequences is at most

n'(C*)8(s+g)(

s+i

[]

Note that, according to Lemma 7.5.3, no packet appears twice at some

stage in a delay sequence. Hence the ranks of the packets in any delay se-

quence have an offset in [K] that is chosen independently at random. There-

fore the probability that a particular delay sequence with s + 1 packets is

active is at most 1/K 8+1. As a consequence,

Pr[the routing takes

T = s + 2SD*

or more rounds]

Lemma 7.5.2

[ an (s, 2SD*)-delay sequence with distinct ]

_< Pr [ delay packets within each stage is active J

Lemma7.5.4__~ n"

(C*) 8(8:~) (8+2~'g)s

+ 1 " (1) s+l

If we set K > 8C* and

s >_ g+2SK+ (a+l) logn,

where a > 0 is an

arbitrary constant, then

Pr[the routing takes at least

T = s + 2SD*

steps]

( n 9 22s+g+2SK 9

2 -38 ( 1

Since ~ _< 2SD*, this proves Theorem 7.5.1. []

7.5.2

Applications

In the following we show that the extended growing rank protocol can be

used for efficient network emulations, which has applications in the field of

compact routing.

96 7. Oblivious Routing Protocols

Consider the problem of simulating the routing of an arbitrary permuta-

tion in a network G by a network H. Using Valiant's trick of first routing

packets to random intermediate destinations in G before they are routed to

their true destinations, it suffices to consider the problem of routing a ran-

dom function in G. Let H be an arbitrary node-symmetric network of size

N with diameter

DH.

Further let G be an arbitrary network of size N with

degree 6 and a path system with dilation Da and expected congestion 7Da.

We start with describing how to embed G in H. Consider an arbitrary

1-1 embedding of the nodes in G into the nodes of H. We intend to simu-

late every edge in G by a path in H that connects the nodes simulating its

endpoints. Since the degree of G is 5, there is a path collection in H con-

sisting of two stages of shortest path collections for simulating the edges in

G with congestion at most

O(~DH -k

log N) and dilation at most

(use

Theorem 5.1.2 together with Valiant's trick).

Consider now the problem of routing a random function in G. Suppose

that each packet p chooses a random

startup stage s 6 [DG].

Then we define

a packet p to be at

superstage q >_ s

at edge e if e is the (q - s)th edge on

its path. Since 7vG has dilation DG, the number of different superstages used

by the packets is at most 2De. As the expected congestion of PG is ")'De,

the expected number of packets that visit some fixed edge e at some fixed

superstage q is at most 7.

As noted above, each superstage can be simulated by H by moving the

packets along two stages of shortcut-free paths. Thus altogether, simulating

the routing of a random function in G by H using random startup stages in

[Dc] requires at most

4DG

stages of shortcut-free path collections. Since the

stage dilation is at most

DH,

it remains to calculate an upper bound for the

stage congestion that holds w.h.p.

Consider some fixed superstage q. Since the expected number of packets

that want to use some fixed edge e in G at some fixed superstage is 7, the

expected number of packets that want to traverse a path in H at some fixed

superstage is at most 7. As the congestion of the shortcut-free path collections

in H simulating edges in G is at most

O(SD +

logN), the expected number

of packets that want to use some fixed edge e in H at some fixed superstage

is at most C* =

O(7(tSDH +

logN)).

For any fixed q, let the random variable Xe q denote the number of packets

at stage q that traverse e during the simulation of routing in G by H. Further

let for every node i in H the binary random variable X~, e be one if and only

if the packet with source i traverses e at stage q during the simulation. Then

Zeq = ~-~ie[N]

Xiq, e"

Since the probabilities for the X'q,,e are independent and

E(X~) < C* = O(7(6DH +

logN)), we can apply Chernoff bounds to get

that the stage congestion for e is bounded by

O(7(~DH +

logN) + logN),

w.h.p. Thus the stage congestion for the whole simulation of routing a random

function in G is bounded by

O(7(~DH +

logN) + logN), w.h.p. Hence we

get the following theorem.

7.5 The Extended Growing Rank Protocol 97

Theorem 7.5.2.

Any node-symmetric network H of size N with diameter

= ~2(log

N) can simulate the routing of any permutation (or randomly

chosen function) in a network G with degree ~ and a path system with dilation

Dc and expected congestion 7Da in

O((3'~ + 1)De-OH)

steps, w.h.p.

This result implies the following corollary.

Corollary 7.5.1.

Any node-symmetric network H of size N with diameter

D = 12(log

N) can simulate the routing of a randomly chosen function in any

bounded degree network G of size N with routing number R in time O(R. D),

w.h.p.

The advantage of the simulation strategy used for this corollary is that it

does not perform a step-by-step simulation. Note that in order to get the same

time bound with a step-by-step simulation we would require a protocol for G

that routes a randomly chosen function in time

O(R),

w.h.p. For arbitrary

bounded degree networks, however, such a protocol is not known yet.

Theorem 7.5.2 also has interesting consequences for simulating routing

in s-ary butterflies by node-symmetric networks, since s-ary butterflies have

routing strategies with a low expected congestion.

Lemma 7.5.5.

There is a randomized online strategy for the s-sty wrap-

around butterfly of size N using paths of dilation at most

2 log s

N such that,

for a randomly chosen function, the expected congestion at

any node is at most

2 log s

N, and

any edge is at most

2 log, N.

Proof.

Consider an arbitrary s-ary d-dimensional wrap-around butterfly. For

any packet p with source (g, x) and destination (e', y), we use the following

strategy:

We first route p to a random intermediate destination at level (l', z). This

will be done by selecting at random one out of s possible edges to the next

higher level until we reach level gl. In order to get from (e',z) to (~,y), p

uses the unique path of length d along the levels ~', l' + 1, g~ + 2,..., ~'. For

a randomly chosen destination, this path corresponds to randomly choosing

one out of s possible edges to the next higher level for each of the d levels.

Hence routing p to a randomly chosen destination as described above

implies routing p along one out of s possible edges to the next higher level,

chosen independently at random, for at most 2d levels. Since the s-ary wrap-

around butterfly is node-symmetric, the expected congestion at every node

is the same for a randomly chosen function, and therefore at most 2d. Hence

the expected congestion at every edge is at most ~. Since the dimension of

any s-ary butterfly of size N is at most log s N, the lemma follows. []

98 7. Oblivious Routing Protocols

Lemma 7.5.5 and Theorem 7.5.2 together yield the following theorem.

Theorem

7.5.3.

Any node-symmetric network of size N with diameter D =

f2(log

N) can simulate any permutation routing problem on an s-ary wrap-

around butterfly o] size N in time

O(log s

N. D), w.h.p.

Because of the regular structure of an s-ary butterfly the nodes only

need to know the numbers of the subbutterflies their edges are connected

with in order to send packets to their correct destinations. Since less space

is necessary to store the paths in H simulating edges of the s-ary butterfly

than to store complete routing tables in H, this strategy can be used to

develop fast compact routing schemes for any node-symmetric network H.

For a more detailed description of how this works we refer to the chapter on

compact routing schemes.

7.5.3 Limitations

In contrast to the previously presented protocols, in order to apply Theo-

rem 7.5.1 to a network we can not use a bound on the expected stage con-

gestion for C*, but instead need a bound for the stage congestion that holds

w.h.p. The reason for this is that for the extended growing rank protocol

it can happen, in contrast to the previous protocols, that the same packet

appears more than once in an active delay sequence. Therefore, a high con-

gestion at one edge may also imply a high congestion at another edge.

Until now it is not known whether there is a simple path collection for

which the extended growing rank protocol performs poorly. However, the

protocol still requires that parts of a path collection are shortcut-free. This

drawback will be removed in the following protocol.

7.6 The Trial-and-Failure

Protocol

In this section we present a protocol that routes packets along an arbitrary

simple path collection of size n with link bandwidth B, congestion C, and

dilation D in time

O( C" D1/B + + D)

w.h.p., without buffering. It is called

trial-and-failure protocol

and has been

presented in [CMSV96]. Since it can be used to route along arbitrary simple

path collections, we will apply the protocol to routing in arbitrary networks,

using the routing number of a network to bound its runtime.

The idea of the trial-and-failure protocol is that, once a packet leaves its

source, it has to move along the edges of its path without waiting until it

reaches its destination. If too many packets want to use the same link at the

same time then some are discarded (and therefore have to be rerouted). In

the following we assume that every link has bandwidth B _> 1.