Scheideler C. Universal Routing Strategies for Interconnection Networks

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

48 5. The Routing Number

Hence asymptotically the routing number is not only an upper bound, but

also a lower bound for the average permutation routing time using optimal

routing strategies in G. This demonstrates that the routing number is a robust

measure for the routing performance of networks.

Note that the routing number might be defined by some protocol which

uses specific routing paths tailored to the permutation to be routed. This

implies the following result.

Remark 5.0.1. For any network G of size N with routing number R, there

exists a collection of simple paths for any permutation routing problem 7r E

with congestion at most R and dilation at most R.

The question is whether it is possible to find such a path collection in an

efficient way for every permutation routing problem. This will be answered

in the following two sections. In the first section we prove the existence of

path systems with low dilation and expected congestion, and in the second

section we show how to choose path collections out of such systems in a

distributed way such that the dilation and congestion bounds in Remark 5.0.1

can be reached up to constant factors for any permutation routing problem.

Furthermore we show in Section 5.4 how the routing number of a network is

related to its expansion. Section 5.3 gives bounds on the routing number of

some important classes of networks. Finally, Section 5.5 contains high-level

descriptions of algorithms for constructing efficient path systems in arbitrary

networks.

5.1 Existence of Efficient Path Systems

A necessary prerequisite for efficient oblivious routing is a path system with

low dilation and low expected congestion. In this section we construct path

systems whose dilation and expected congestion are close to the routing num-

ber for arbitrary networks. The main result of this section is formulated in

the next theorem.

Theorem

5.1.1.

For any network G of size N with routing number R there

is a simple path system with dilation at most R and expected congestion at

most R. Furthermore, for random functions the congestion is bounded by

R + O(x/max{R, logN } 9

logg),

w.h.p.

Proof.

Let G be a network of size N with routing number R. Then for any

permutation 7r~ : IN] -~ [N] with Try(x) = (z + i) mod N for all

i,x e

[N]

there is a path collection

79i

along which packets can be routed in at most R

time steps. Therefore the congestion and dilation of

"Pi

is at most R. We then

choose P = I.J~o I

to be the path system for G. Clearly, this path system

has congestion at most N 9 R and dilation at most R. It remains to bound

5.1 Existence of Efficient Path Systems 49

the expected congestion and the congestion that holds w.h.p, for routing a

random function in G using paths in 7 ).

Consider any edge e in G. Let the random variable X denote the num-

ber of paths that cross e and are used by a packet. Since each node in G

chooses a destination for its packet uniformly and independently at random,

the probability that a path crossing e is used by a packet is 1/N. Therefore

the expected congestion is at most R.

For any node v in G, let the binary random variable Xv be one if and only

if the packet with source v contains e in its routing path. Then

X = ~,ey Xv.

Since we consider routing a random function, the probabilities of all X~

are independent. As E[X] _< R, the Chernoff bounds (see Theorem 3.2.2)

therefore yield that

l e e2R/2

: if 0 < e < 1

Pr[X_>(I+e)R]_< e_~.R/3 : ife>l

~ig~N ,osN

This probability is polynomially small in N for e = O(max( , R ))

sufficiently large. Hence w.h.p, all edges have a congestion of at most R +

O(x/max{R, log Y}- log N). [3

For node-symmetric networks we can strengthen Theorem 5.1.1 by showing

that the path system may even consist solely of shortest paths. This is impor-

tant, because some oblivious routing protocols are especially good for shortest

path systems, see Chapter 7. Since the diameter of a network is a lower bound

for its routing number, we use the diameter instead of the routing number in

the following theorem.

Theorem

5.1.2.

Let G be a node-symmetric network with N nodes and di-

ameter D. Then there exists a shortest path system that has an expected

congestion of D + O( ~/ D I~ N ).

Proof.

Consider the problem of gossiping in G. For every source-destination

pair

(u,w) E V 2,

perform the random experiment of choosing uniformly at

random one path out of the set of all shortest paths that connect u with w.

For every node v in G, let the binary random variable X v be one if and

only if the path chosen from u to w traverses v, and Pu,wv = Pr[X~, w = 1].

Further let the random variable

denote the number of paths traversing v.

Then it holds

C~= ~ X ~

U,W "

(u,w)~V 2

Since G is node-symmetric, there exists for every node v' in G an automor-

phism ~o that maps v to v I. The uniform choice of the paths ensures that

P~,~-- PV(')v(u),~(~) for all node pairs (u, w). Thus it holds

50 5. The Routing Number

~'v(=),v(w)

(u,w)eV 2 (u,w)eV 2

(u,w)~V 2

Hence, E[Cv] is the same for every node v in G, namely at most N. D. Since

the paths are chosen independently at random, applying Chernoff bounds

yields that Cv = N 9 D + O(x/D. NlogN), w.h.p. Thus there exists a path

system in G with such a congestion. Since, for a randomly chosen function,

each of the paths has a probability of ~ to be chosen, Theorem 5.1.2 follows.

[]

Theorem 5.1.2 implies, for instance, that for the wrap-around butterfly

network there exists a shortest path system connecting all of its nodes with

expected congestion at most its diameter plus one. It also implies how to

construct such a path system: Just choose, for any pair of nodes, a path uni-

formly at random from all shortest paths connecting these nodes. Similarly,

the following result holds for edge-symmetric networks.

Theorem 5.1.3. Let G be a edge-symmetric network with N nodes, degree

d, and diameter D. Then there exists a shortest path system that has expected

congestion

DO. + O( ~ ~/max{ -~, log N }. log N)

5.2 Valiant's Trick

In Section 5.1 we have seen that for any network with routing number R there

is a fixed path system that yields asymptotically optimal parameters C and D

for almost all functions. However, Borodin and Hopcroft [BH85] could prove

a very high lower bound for the maximal congestion that can be reached by

a permutation routing problem in a network using a fixed path system. Their

result has been improved by Kaklamanis et al. [KKT91]. Together with an

extension by Parberry [Pa90] we obtain the following theorem.

Theorem 5.2.1. Let G be an arbitrary network of size N with degree d, and

let 7 9 be an arbitrary path system in G. Let n nodes in G be determined as

souvces and destinations. Then there is a permutation 7r E Sn that has a

congestion C, of O( d-~ ).

Hence, if G has constant degree and all nodes in G are source and des-

tination, that is n = N, then there exists a permutation with congestion

12(v/N). Therefore the congestion might be much higher than the dilation,

since networks of bounded degree can have a diameter of O(log N).

5.2 Valiant's Trick 51

For the d-dimensional hypercube M(2, d) Theorem 5.2.1 implies a worst

case congestion of

C = f2(x/~/d).

Kaklamanis et

al.

present a path system

in [KKT91] that reaches this bound.

In case that packets have to be sent from the inputs to the outputs of

a d-dimensional wrap-around butterfly according to some arbitrary permu-

tation, Bock [Bo96] presents a path system that reaches the lower bound

C = f2(v/~/d).

According to Theorem 5.2.1, oblivious routing might perform very poorly

for some functions. Thus, in order to get close to the routing number, we have

to turn to non-oblivious strategies. A beautiful, simple idea was presented in

[V~S2].

Valiant's trick:

Consider routing an arbitrary permutation. Route the packets first

to intermediate destinations, chosen uniformly and independently

at random, before routing them to their true destinations.

Applying this trick to a fixed path system P yields the following strategy:

Each node first chooses random intermediate destinations for its packets.

Then each packet is first sent to this intermediate destination, and from there

to its final destination, both times using the path prescribed in P.

With this strategy, the congestion of

every

permutation routing problem

can be brought close to the expected congestion of P, w.h.p. In particular,

the following theorem holds.

Theorem 5.2.2.

Let P be an arbitrary path system of size n with dilation

D and expected congestion C. Then every permutation can be routed along

paths in 7 a using Valiant's trick with dilation at most 2D and congestion at

most

2C + O(~/max{C, logn}, logn),

w.h.p.

Proof.

Consider first the problem of routing a random function. Let V be

the set of sources in P. Consider an arbitrary edge e in P. For every v E V,

let the binary random variable Xv be one if and only if the packet starting

from v traverses e. Further let the random variable X denote the number

of packets that traverse e. Then X =

~vev Xv.

According to the definition

of the expected congestion, it holds E[X] _< C. For a random function, the

probabilities for all Xv are independent. Hence the Chernoff bounds yield

that

( e -e2~/2 : if 0 < e < 1

Pr[X_>(I+e)C]<_ e_~V/3 : ife>l

which is polynomially small in n fore -- O(max{ ~c ~, l~

large. If we use Valiant's trick to route an arbitrary permutation then both

situations, routing packets from their sources to intermediate destinations

and from the intermediate destinations to their destinations, can be regarded

as routing random functions. Hence the overall congestion of routing packets

according to an arbitrary permutation using Valiant's trick is at most

52 5. The Routing Number

2C + O (~/max{C, logn} . logn)

w.h.p. Furthermore, the dilation of the resulting paths is at most 2D. []

An easy consequence of this theorem is the following corollary.

Corollary 5.2.1. Let 79 be an arbitrary path system of size n with dilation

D and expected congestion C. Then every h-relation can be routed along paths

in 79 using Valiant's trick with dilation at most 2D and congestion at most

2h. C + O(x/max{hC, logn } 9 logn), w.h.p.

Theorem 5.1.1 and Corollary 5.2.1 yield the following result.

Corollary 5.2,2. For any network G of size N with routing number R there

exists a simple path system 7 9, such that routing any h-relation along paths

in 79 using Valiant's trick has dilation at most 2R and congestion at most

2h. R + O(x/max{h. R, logn), logn), w.h.p.

This result implies that if there is an oblivious protocol that can route

packets along an arbitrary simple path collection with dilation D and conges-

tion C in time O(C + D) then a combination of the path selection strategy in

Corollary 5.2.2 and this protocol would yield a routing protocol that reaches

the optimal routing performance of permutation routing in arbitrary net-

works. We will show in Chapter 7 that in fact there is an oblivious routing

protocol that comes quite close to this bound.

5.3 The Routing Number of Specific Networks

In this section we determine the routing number of some important classes

of networks. Theorem 5.1.2 together with Theorem 5.2.2 and Theorem 6.0.1

yields the following result.

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

~2(log N) has routing number (9(D).

Since the butterfly is node-symmetric, Corollary 5.3.1 yields that the rout-

ing number of a butterfly of size N is 69(log N). As any bounded degree net-

work of size N has a diameter of I2(log N), and any expander has a constant

expansion, we obtain the following result together with Theorem 5.4.2, which

will be presented in the next section.

Corollary 5.3.2. Any bounded degree expander of size N has a routing num-

ber of ~9(log N).

5.4 Routing Number vs. Expansion 53

5.4 Routing Number vs. Expansion

In this section we establish a relationship between the routing number and

the expansion of a network. In [LR88] the following result is shown.

Theorem

5.4.1. Let H be a bounded degree network of size N with expan-

sion ~. Given any N-node bounded degree network G, and any 1-1 embedding

of the nodes of G onto the nodes of H, the edges of G can be simulated by

paths in H with congestion and dilation at least 12(~) and at most O(~)

Ot I"

Together with Theorem 6.0.1 we obtain the following result.

Theorem 5.4.2. Any bounded degree network of size N with expansion a

has a routing number

at lea, t a, d at most

As shown in the next theorem, these bounds are tight.

Theorem 5.4.3. For all 1IN < a < 1/logN, there exists a bounded degree

network of size N with expansion O(a) and routing number 0(~). Further-

more, for all log N/N < a < 1, there exists a bounded degree network of size

N with expansion O(a) and routing number O(I~

Ot P"

Proof. Let us start with constructing networks for the first case. According

to Corollary 5.3.1, the wrap-around butterfly (WBF) of size N has routing

number O(log N). Since for any d-dimensional WBF both of its two (d- 1)-

dimensional sub-butterflies have a size of d. 2 d-l, but only 2 d edges leaving

them, Theorem 5.4.2 yields that the expansion of a WBF of size N is bounded

by 1

O(~). If we replace each edge of the WBF by a path of length k, its

two (d - 1)-dimensional sub-butterflies have a size of O(kd. 24-1), but still

only 24 edges leaving them, that is, the expansion of the resulting network

is O(~). On the other hand, it is easy to show (by using, for instance,

the random rank protocol together with Valiant's trick, see Section 7.2) that

the worst case time for routing a permutation in this network, and hence its

routing number is O(k log N). This yields the first statement of the theorem.

Now we show how to construct networks for the second case. According

to Corollary 5.3.2, we know that every bounded degree expander of size N

has expansion O(1) and routing number O(logN). Let G be any of these

networks. If we replace each edge of G by a path of length k, it is easy to

see that the expansion of the resulting network is O(-~). On the other hand,

any permutation routing strategy in this network can be simulated by G in

asymptotically the same time (each node in G simulates k/2 nodes of each

path representing one of its edges). Hence, the worst case time for routing

a permutation in this network is at least the worst case time of routing a

k-relation in G, and therefore its routing number is Y2(k log N). This yields

together with Theorem 5.4.2 the second statement of the theorem. [3

54 5. The Routing Number

Theorem 5.4.3 shows that in general the expansion of a network can only

be used to describe its routing number to within a factor of log N. The ques-

tion therefore is whether there exist simple structural properties of networks

that yield a more accurate bound on their routing number.

5.5 Computing Efficient Path Systems

By using the routing number, we showed that path systems exist for arbitrary

networks that together with Valiant's trick allow the online construction of

efficient path collections for arbitrary permutation routing problems. How-

ever, we did not address so far the problem of how difficult it is to compute

such a path system. In the following, we will describe a polynomial time al-

gorithm for constructing efficient path systems for arbitrary networks, and

present a simple and fast algorithm for constructing efficient path systems

for node-symmetric networks.

5.5.1 An Algorithm for Arbitrary Networks

Consider any network G of size N with routing number R. The following

algorithm will serve as a basic building block for our algorithm.

For any L E 1~, let GL denote a leveled network of depth L that has N

nodes in every level. For each level, let its node set represent the set of all

nodes in G. Two nodes v and w in consecutive levels are connected iff v and

w represent the same node in G or the nodes represented by v and w are

connected in G. In the first case, assume the edge to have infinite capacity,

and in the second case, assume the edge to have capacity N. Let all edges

be directed downwards. Consider the problem of sending one unit of flow

from every node at the top level to every node at the bottom level. If we

allow fractional flows then linear programming can be used to find a solution

(or stop with the answer that no solution exists) in polynomial time (see

Section 1.4.3).

Now we are ready to formulate our algorithm for finding an efficient path

system.

1. Find the minimum L for which there is a solution for the multicommodity

flow problem for GL as stated above.

2. Transform the multicommodity flow for GL into a multicommodity flow

for G by identifying nodes in GL representing the same node in G. Since

every edge in GL representing an edge in G has capacity N, at most a

flow of L 9 N traverses any edge in G.

3. Use Raghavan's method IRa88] for converting fractional flows into inte-

gral flows. This results in a path system for G with dilation at most L

and expected congestion at most L + O(V/L l~ g).

5.6 Summary of Main Results 55

Clearly, the algorithm runs in polynomial time. It remains to show that L <_

For all i E [N], let Si denote the optimal schedule for routing permutation

Iri : [N] --+ [N] with 7ri(x) = (x + i) mod N. Since the runtime of Si is at

most R, Si can be easily used to construct a solution to the multicommodity

flow problem for GR, in which every node x in the top row wants to send

a unit of flow to node lri(x) in the bottom row, and every edge in GR that

simulates an edge in G has capacity 1. Hence the combination of all these

flows results in a solution to our multicommodity flow problem stated above.

Since we require L to be minimal, L _< R.

5.5.2 An

Algorithm for Node-Symmetric Networks

For node-symmetric networks, there exists a much faster algorithm than the

algorithm above. Consider any node-symmetric network G of size N with

diameter D. In the proof of Theorem 5.1.2 we have seen that, if for every

source-destination pair (u, w) a path from u to w is chosen uniformly at

random from all possible shortest paths that connect u with w, then w.h.p.

this results in a shortest path system with an expected congestion of D +

O(~/~). Let us replace this random experiment by the following strategy

for each node pair (u, w), which is much easier to implement:

Start the construction of the shortest path with u. Let v be the current

endpoint of the path. From all neighbors of v that can be used to extend the

shortest path, choose one uniformly at random, and continue the construc-

tion of the path at this neighbor. Repeat this random experiment until w is

reached.

Let the P~,w and E[Cv] be defined as in the proof of Theorem 5.1.2. Since

G is node-symmetric, there exists for every node v I in G an automorphism

that maps v to v I. As is easy to see, the uniform choice of a candidate for

extending a shortest path ensures that P~,wv = k'~(~),~(w)~(v) for all node pairs

(u,w).

This yields E[Cv] = E[Cv,] for all nodes v and v' in G (see the proof

of Theorem 5.1.2). Hence, E[Cv] is the same for every node v in G, namely

at most N 9 D. Thus we end up with a shortest path system with expected

congestion C = D + ~kV --~ j, w.h.p.

5.6 Summary of Main Results

At the end of this chapter we give a summary of its main results. After

defining the routing number we showed in Section 5.1 the following result

(see Theorem 5.1.1).

For any network of size N with routing number R there is a simple path

system with dilation at most R and expected congestion at most R.

56 5. The Routing Number

Hence

every

network has a simple path system with asymptotically op-

timal dilation and expected congestion. Using this together with Valiant's

trick, we could show the following result in Section 5.2 (see Corollary 5.2.2).

For any network of size N with routing number R there exists a sim-

ple path system 7), such that routing any h-relation along paths in 7 ) using

Valiant's trick has dilation at most 2R and congestion at most 2h 9 R +

O(~/max(h. R,

logn}, logn),

w.h.p.

This implies that, if there is an online protocol that can route packets

along an arbitrary simple path collection with dilation D and congestion

C in time

O(C + D)

then a combination of the path selection strategy in

Corollary 5.2.2 and this protocol would yield an online routing scheme that

reaches the optimal routing performance of permutation routing in arbitrary

networks. Leighton

et al.

[LMR88, LMR94] have demonstrated that at least

offiine this is always possible. In Chapter 7 we will show how close oblivious

routing protocols can get to this bound.

In Section 5.3, we determined the routing number of arbitrary node-

symmetric networks and bounded degree expanders. Moreover, we showed

in Section 5.4 that the expansion of a network of size N in general can only

be used to describe its routing number to within a factor of log N. Finally,

we described in Section 5.5, how efficient path systems can constructed in

polynomial time for arbitrary networks.

6. Of[line Routing Protocols

In Section 5.2 we saw that for any network G of size N with routing number

R there exists a simple path system :P, such that routing any permutation

along paths in :P using Valiant's trick has dilation at most 2R and conges-

tion 2R + O(x/max{R, log n}. log n), w.h.p. On the other hand we saw that,

on average, a permutation can not be routed below ~(R) steps, whatever

protocol used. Hence, in order to get an (asymptotically) optimal average

permutation routing time for arbitrary networks, we need a protocol that

can route packets along any simple path collection with congestion C and

dilation D in O(C + D) steps. In a celebrated paper, Leighton, Maggs and

Rao [LMR88] could prove the following result.

Theorem 6.0.1. For any set o] packets with simple paths having congestion

C and dilation D, there is an oJ~ine schedule that needs O(C + D) steps to

route all packets, using buyers o/ constant size.

The proof of this theorem can be found in [LMR88] (see also [LMR94]).

In [LMR96] it is furthermore shown that there is an algorithm that computes

such a schedule in time O(P. loglog P. log P) steps, where P is the sum of

the lengths of the paths.

The proof Leighton et al. used, however, has several disadvantages: It is

very difficult to understand, and it makes no attempt to reduce the constants

hidden in the runtime bound and the bound for the buffer size. (In fact, the

constants hidden are beyond one million.)

In this chapter, we present alternative proofs for the existence of offline

protocols with runtime O(C + D), that are much easier to understand. The

first two aim at keeping the runtime small, and the third aims at keeping the

buffer size small. As in [LMR88], the basic argument used in the proofs is the

Lov~sz Local Lemma (see [AES92], p.55).

Lemma 6.0.1 (Lov~isz Local Lemma). Let A1,... ,An be a set of "bad"

events in an arbitrary probability space. Suppose that each event Ai is mutu-

ally independent of all other events Aj but at most b, and that PrIAm] < p. If

ep(b + 1) < 1 then, with probability greater than zero, no bad event occurs.

Besides presenting proofs for efficient offiine protocols, we also show how

these protocols can be applied to network simulations. In particular, we