Scheideler C. Universal Routing Strategies for Interconnection Networks
Подождите немного. Документ загружается.
7.6 The TriM-and-Failure Protocol 99
7.6.1 Description of the Protocol
Consider an arbitrary simple path collection of size n with dilation D and link
bandwidth B. Initially, each packet pi chooses uniformly and independently
from the other packets a random rank ri E [K] (K will be specified later)
and a random delay di E [/9]. Additionally,
Pi
stores an identification number
id(pi) E In] in its routing information that is different from all identification
numbers of the other packets. Let us define the following contention resolution
rule.
B-priority rule:
If more than B packets attempt to use the same link during the
same time step, then those B with lowest rank win.
If two or more packets have the same rank then, in order to break ties,
the ones with the lowest id's win. Then the protocol works as follows.
repeat
9
forward pass:
Each active packet p~ waits for di steps. Then it
is routed along its path, obeying the B-priority rule.
, backward pass: For each packet that reached its destination
during the forward pass, an acknowledgment is sent back to the
source. Upon receipt of the acknowledgment, the source declares
the packet inactive.
until no packet is active
Clearly, the forward pass needs 2D steps to be sure that every packet that has
not been discarded during the routing reaches its destination. These packets
are called
successful.
In the backward pass, the forward pass is run in reverse
order. Therefore, no collisions can occur in the backward pass, and 2D steps
suffice to send all acknowledgments back.
Theorem
7.6.1.
Suppose we are given an arbitrary simple path collection
P of size n with link bandwidth B, congestion C, and dilation D. Further let
K >_ 4C. D -1+1/B. Then the trial-and-failure protocol needs
O( C" DI/B + DI~ +
steps, w.h.p., to finish routing in P without using buffers.
Proof.
In order to prove the time bound, we again use a delay sequence
argument.
Definition 7.6.1 ((s, B)-delay sequence).
An
(s, B)-delay sequence
con-
sists of
100 7. Oblivious Routing Protocols
1. s 9 B + 1 delay packets Pl,...
,Ps.B+I
such that during the forward pass
of round i > 1, packet pi.B+l is prevented from using a link by packets
P(i-1)B+I, . . . ,Pi.B;
2. s. B + I integer keys rl,. . . ,rs.B+l such that O < rl < ... <_ rs.B+l < K.
A delay sequence is called
active
if
rank(pi)
= ri for all 1 < i < s. B + 1.
Lernma 7.6.1.
If the routing takes more than s rounds, there exists an active
( s, B )-delay sequence.
Proof.
In the following we will give a construction for such a delay sequence.
If the routing takes more than s rounds then there is a packet
ps.s+l
that
did not reach its destination in round s. In such a case there must have
been packets
P(s-1)B+I,...,Ps.B
that prevented Ps.B+x from using some
link in round s. According to the routing protocol, P(s-1)B+I,...
,Ps.B
can
be chosen such that
rank(p(s_l)B+l) < ... < rank(ps.B) <
rank(ps.B+l).
But if
P(s-1)B+I
was still active in round s, there must have been packets
P(s-2)B+I,... ,P(s-1)B
in round s - 1 that prevented P(s-1)B+I from using
some link, where rank(P(s-2)s+l) < ... < rank(p(s-1)B) < rank(p(s-1)B+l).
Continuing this argument back to round 1 yields the lemma with ri :=
rank(pi) for all 1 < i < s. B + 1. []
Lemma 7.6.2.
The number of different (s, B)-delay sequences is at most
n . (O . C.)s (s " B +
\s.B+l]
Proof.
We count the number of possible choices for the components:
- There are at most n 9 (D 9 CB) s choices for the delay packets. This is
because there are at most n possibilities to determine the packet P,.B+I,
and if Pi.B+I is fixed, there are at most D 9 C B choices for the packets
P(~-I)B+I,... ,Pi.B for all 1 < i < s.
- There are
t{(s'B+l)+g-l~s.B+l
]
possibilities to choose the ri's such that 0 _< rt <_
9 "" <_ rs.B+l < g.
Multiplying these terms yields the lemma. []
Since each packet chooses a random rank and a random delay, and
the contention resolution rule of the above routing protocol requires that
in any active delay sequence the packets have to be pairwise distinct,
the probability that a particular (s, B)-delay sequence is active is at most
K -(s'B+D (1/D) s'B.
Therefore, if we choose
K > 4C.D 1/B K + (a +
1) logn
and T> +1
- D B
for some arbitrary constant a > 0 then
7.6 The Trial-and-Failure Protocol 101
Pr[the routing takes more than T rounds]
Lemma 7.6.1
< Pr [a (T, B)-delay sequence is active]
( )
Lemma 7.6.2
B T T 9 B + K -(T.B+I)
< n.(D.C ) T.B+I K
~_ n. 2 T'B+K 9 .
< n.2T.S+ K .2_2T. B ~ n.2_(a+l)log n _ 1
-- not
This yields Theorem 7.6.1. [3
Since f2(~ +D) is a lower bound for any protocol that routes packets along
a simple path collection P of size n with link bandwidth B, congestion C,
and dilation D, the runtime of the trial-and-failure protocol gets optimal for
C _> Dlogn and B _> logD, or B _> log(riD). Note that in case of
C = O(D)
and B > log D the range from which the ranks have to be chosen reduces to
a constant. In particular, if C. D -1+1/B _< 1/4 then the above protocol does
not require random ranks any more. That is, only random delays are needed
in this case to get the time bound in Theorem 7.6.1.
7.6.2
Applications
If we simulate link bandwidth by buffers we arrive at the following result.
Corollary
7.6.1.
Given any simple path collection of size n with buffer size
B, congestion C, and dilation D, the trial-and-failure protocol requires O( C.
D1/B +
Dlogn)
time to route all packets, w.h.p.
This result is optimal if C _> D log n and B _>
Valiant's trick we get the following result.
log D. Together with
Corollary
7.6.2.
Let G be an arbitrary network of size N with buffer size
B and routing number R. Then the trial-and-failure protocol routes packets
according to an arbitrary h-relation in time O( (h. R 1/B +
logN)R),
w.h.p.
In case of shortcut-free path collections, Theorem 7.6.2 provides the fol-
lowing tradeoff between routing time and buffer size for oblivious routing.
Theorem
7.6.2.
Given any shortcut-free path collection of size n with con-
gestion C, dilation D, and buffer size B <_ C there exists an online routing
protocol that requires
O( C'D1/B+l~176
time to route all packets, w.h.p.
102 7. Oblivious Routing Protocols
Proof.
Consider routing n packets along a shortcut-free path collection with
congestion C and dilation D in a network with buffer size B. Each packet pi
is chosen as in the trial-and-failure gets two random ranks: the first rank r~
g is chosen as in the growing rank protocol.
protocol, and the second rank r i
The new protocol then works as follows
t and
rq
all n packets are
for each packet p~, choose random ranks r i ~,
declared active
repeat
9 forward pass: route packets according to the growing rank pro-
tocol; in case of overfull buffers use the B-priority rule (that is,
those B packets with lowest ranks r~ survive, the others are elim-
inated)
9 backward pass: successful packets become inactive via acknowl-
edgments by reversing the forward pass
until no packet is active
From Theorem 7.4.1 we know that the growing rank protocol requires at
most
O(C + D +
logn) time, w.h.p., to be sure that packets either reached
their destination or have been discarded because of an overfull buffer. Using
a similar delay sequence argument for eliminations of packets as in the proof
of Theorem 7.6.1 yields that
O(-~(C. D 1/B +
logn)) rounds suffice to route
all packets, w.h.p. (leave out the probability ~ for the delay). This completes
the proof of Theorem 7.6.2. []
7.6.3 Limitations
The runtime bound of the trial-and-failure protocol holds for arbitrary, even
non-simple, path collections. However, the definition of C must be changed
for non-simple path collections in a way that if a packet traverses an edge e
q times then it has to count q times for
Ce.
7.7 The Duplication Protocol
In this section we present an efficient protocol for routing packets along an
arbitrary simple path collection of size n with congestion C, dilation D,
and bandwidth O(log(C.
D)/loglog(C. D))
without buffering. It is called
duplication 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 duplication protocol is similar to that of the trial-and-
failure protocol, with the difference that each new trial the number of copies
7.7 The Duplication Protocol 103
sent out for a packet is duplicated. This significantly increases the chance
that finally one of the copies will be able to reach the destination. In the
following we again assume that every link has bandwidth B _> 1.
7.7.1 Description of the Protocol
We define the following rule in case of contention between packets:
B-collision rule:
If more than B packets attempt to use the same link during the
same time step, then all of them are discarded.
The duplication protocol consists of k + 1 rounds (the parameters k, Cr, and
B will be determined later).
Duplication Protocol:
all n packets are declared active
for r -- 0 to k do
9 forward pass: for each active packet, send 2 r copies of it with
random startup delays in [Cr], route the copies according to the
contention resolution rule above
9 backward pass: successful packets become inactive via acknowl-
edgments
Clearly, the forward pass of round r requires Cr + D steps to be sure that
either a packet reaches its destination or has been discarded. The backward
pass can be organized in such a way that acknowledgments of successful copies
are not delayed or discarded by running the forward pass in reverse order. A
packet becomes inactive if it receives an acknowledgment of at least one of
its copies.
Theorem 7.7.1. Given any simple path collection 7 9 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 ~C + D loglogn +
]
time, w.h.p., to finish routing in 79 without buffering.
Proof. Our line of proof will be to show that the congestion is reduced enough
from round to round such that more and more copies of each active packet can
be sent out, until the probability that none of its copies reaches its destination
gets polynomiaUy small in the number of packets.
We first need the following definitions. A site is an ordered pair (e, s)
where e is an edge and s is a step in the forward pass (of the round currently
being considered). A packet p aims for a site (e, s) if p selects a random
104 7. Oblivious Routing Protocols
delay such that it will be present in edge e at step s of the forward pass,
provided that it is not discarded before reaching edge e. Note that whether
or not a packet aims for a site is strictly a function of its starting time and
its path, and is independent of the starting times of other packets. A packet
p is discarded at a site (e, s)
if p attempts to enter edge e at step s but is
discarded because of edge contention. Note that if y packets are discarded at
a site (e, s), then at least y > B packets aim for site (e, s). Given any packet
p, p's conflicting packets
consist of all packets with paths that intersect p's
path (including p itself). A packet's
region
consists of all sites its conflicting
packets could aim for.
We will begin by analyzing the forward pass of round 0. Let Co = C
and B = 101n(C 9
D)/lnln(C. D).
Consider any packet p and mark any m
sites in p's region. Let the random variable X denote the number of distinct
packets that aim for any of the marked sites. Note that the expected number
of packets which aim for any one site is at most one (because at most C
packets can have the possibility of aiming for the site, and the probability
that such a packet does aim for the site is
1/C).
Therefore, E[X] _< m.
Because X is the sum of independent Bernoulli trials, we can use Chernoff
bounds to bound the probability that X is larger than B 9 m:
Pr[X
> B. m] < (e/B) B'm
= e -m'B(lnB-1).
Since packet p has at most C. D conflicting packets, and for each of these
packets there are at most
D(C + D)
sites (e, s) it could visit, there are at
most
(C'D2(Cm +D))< - (eC'D~C+D))<em(~,n(C.D)+t)
different ways of marking m sites in p's region. Therefore, the probability
that more than B. m distinct packets aim for
any
set of m sites in p's region
is at most
em(a ln(C.D)+l-B(ln B-l)) .
Let m = (a + 2) In
n/2
ln(C. D). Because
lnB - 1
we have
= In(lO/e) + Inln(C. D) - Inlnln(C. D)
>_ (1/2)Inln(C. D) + l ,
em(3tn(C'D)+l-B(lnB-1)) ~
n -(a+2).
Note that if more than B 9 m packets are discarded at sites in p's region,
then more than B 9 m distinct packets must aim for some set of m sites in
p's region. (This can be argued as follows: Let z be the number of sites in
7.7 The Duplication Protocol 105
p's region at which packets were discarded. If z < m, let S be a set of any m
sites including these z sites. If z > m, let S be a set of any m of these z sites.
Note that more than B packets were discarded at each of them. Therefore
ISI -- m, more than B. m packets were discarded at sites in S, each of these
discarded packets aimed for the site at which it was discarded, and these
discarded packets must be distinct because a packet can only be discarded
once.) As a result, the probability that more than B. m packets are discarded
at sites in
any
packet's region is at most n -(a+l). We will say that round 0
succeeded iff for every packet p, at most B. m = 5(a + 2)
lnn/lnln(C.
D) of
p's conflicting packets were not successfully delivered to their destinations.
Now consider round 1. It is identical to round 0 in terms of the number
of (copies of) packets that are discarded, except that it has congestion at
most 2B. m (assuming that round 0 succeeded) because two copies are made
of each of the at most B 9 m packets that were discarded at sites in each
packet's region, and because the paths are simple, each of these packet copies
can contribute at most one to the congestion of an edge. Therefore, we will
set C1 -- 2B 9 m and an analysis identical to the analysis of round 0 shows
that the probability that more than B-m packet copies are discarded at sites
in
any
packet's region during round 1 is at most n -(a+l). Because both copies
of a packet must be discarded in order for the packet to fail to be delivered,
it follows that the probability that there exists a packet p such that more
than
B 9 m/2
of p's conflicting packets were not successfully delivered after
round 1 is at most n -(~+1).
In general, for any round r, 1 < r < k, 2 r copies are made of each active
packet, which results in a copy congestion of at most Cr = 2B 9 m. We
will say that round r succeeded iff for every packet p, at most
B. m/2 r
of p's
conflicting packets were not successfully delivered to their destinations during
the first r rounds. Using an analysis identical to that given for round 1, it
follows that for any round r, 1 < r < k, if all rounds i < r succeeded then the
probability that round r fails is at most n -(a+l). Setting k = log(B .m)4-1 --
O(loglogn), it follows that if all k 4- 1 rounds 0...k succeed, then every
packet has been successfully delivered, since at round k every active packet
gets 2B 9 m copies. The probability that all k 4- 1 rounds succeed at least
(1 -
1~ha+l) k+l ~ 1 - (k +
1)/n a+l > 1 - n -a.
Finally, note that the algorithm requires link bandwidth B = O(log(C 9
D)/loglog(C 9 D))
and takes 2(C
+ D) + 2k(C1 + D) = O(Dloglogn +
C 4- log n loglogn/loglog(C- D)) time, w.h.p. This completes the proof of
Theorem 7.7.1. D
7.7.2 Applications
If we simulate bandwidth B by buffer size B, we arrive at the following result.
Corollary 7.7.1.
Given any simple path collection 7 ~ of size n with conges-
tion C and dilation D, the duplication protocol can be used to finish routing
106 7. Oblivious Routing Protocols
in 7 a in
(( logn : loglogn~ log(C.D_) '~
O C + Dloglogn + loglog(C. D) ] " loglog(C. D)]
time, w.h.p., using buffers of size O(log(C 9 D)/loglog(C. D)).
Corollary 7.7.1 and Corollary 5.2.2 together yield the following result.
Corollary 7.7.2. For any network G of size N with routing number R =
f2(log N), the duplication protocol can be used to route any permutation in
time
(log R_: log log N )
0 \ log log R 9 R_ ,
w.h.p., using buffers of size O(log R~ loglog R).
Using the fact that expanders of size N have routing number O(log N) im-
mediately yields the following corollary.
Corollary 7.7.3. For any bounded degree expander with N processors, N
packets, one per processor, can be routed online according to an arbitrary
permutation in
(log N: (loglogNl2 ~
0 \ log log log N ]
time, w.h.p., using buffers of size 0(loglogN/logloglogN).
7.7.3 Limitations
Note that non-simple path systems cause problems for the duplication proto-
col, since in this case a duplication of the copies for each active packet might
increase the congestion and therefore the collision probability by more than
a factor of two.
7.8 The Protocol by Rabani and Tardos
In the following we present another protocol for routing packets along an
arbitrary simple path collection of size n with congestion C and dilation D,
using buffers of size poly(log n). It has been presented in [RT96].
7.8.1 Description of the Protocol
The main idea of the protocol follows the lines in the papers of Leighton et
al. [LMR88, LMR94]. Instead of using the Lovs Local Lemma for refining
a routing schedule, Rabani and Tardos developed techniques to guarantee
the delivery of packets w.h.p, by using a simple version of Chernoff bounds
7.8 The Protocol by Rabani and Tardos 107
for events with limited correlation. During the execution of their protocol it
might happen that packets get delayed more than allowed by some (randomly
chosen) schedule. In this case some special time is reserved for packets that
are "far" behind where they are "supposed to be" in the schedule. This extra
reserved time allows the delayed packets to catch up and continue on their
paths, where they were "supposed to be".
Theorem 7.8.1.
Given any simple path collection 7 ~ of size n with conges-
tion C and dilation D, the protocol by Rabani and Tardos requires
O(C) +
(log*
n) O(l~
n)D + poly(logn)
time, w.h.p., to finish routing in 7 ~, using buffers o] size poly(logn).
Since the proof of this theorem is quite complicated, we refer to [RT96]
and do not present it here. Instead, we present a proof of the following theo-
rem, which contains many of the basic building blocks for the proof of The-
orem 7.8.1 (see also [RT96]).
Theorem 7.8.2.
Given any simple path collection ~ of size n with conges-
tion C and dilation D, there is a protocol that requires
O(C + D
log log
n + poly(log n))
time, w.h.p., to finish routing in 7 ~, using buffers o] size poly(logn).
Proo].
Let us assume in the following that C _< Dlogn. Otherwise, the ran-
dom delay protocol in Section 7.1 can already be used to obtain a runtime
of
O(C).
Furthermore, we assume that D < n. Otherwise, we choose the
strategy of the random delay protocol to cut paths into pieces of length n
and use the algorithm below for each round instead of Route(~). As we will
see, this ensures a runtime of
O(C + D
log log n).
Before we start with a proof for the remaining cases, let us introduce some
terminology. A
t-~rame
is defined as a sequence of t consecutive time steps
that starts at an integer multiple of t. Given a t-frame F, the
F-segment
of a
scheduled path is defined as the part of it that is scheduled within F. Given a
schedule S, the
contention
at edge e in S is defined as the maximum number
of packets that want to pass e at the same time step.
Our strategy for constructing a protocol with the time bound above is
to make a succession of refinements to an initial schedule So, in which each
packet is forwarded at every time step until it reaches its final destination. The
first step is to assign an initial delay to each packet, chosen independently and
uniformly at random from
[2C/u],
where u = log log n. Then the following
lemma can easily be shown with the help of Chernoff bounds.
Lemma 7.8.1.
For any constant c > 0 there is a constant a such that with
probability at least 1 - n -c the congestion in any T-]tame with T =
~vlogn
is at most vT.
108 7. Oblivious Routing Protocols
Let $1 be a schedule that fulfills Lemma 7.8.1 with a suitably chosen a,
depending on the probability bounds needed later. Our aim is to show that
each T6-frame in $1 can be scheduled independently from the other frames
in time
O(v)T 6,
w.h.p. This produces a schedule of total length
T6 +1.0(vT 6)=O(C+Dloglogn+Teloglogn)
,
w.h.p., as desired. Let us therefore consider some fixed T6-frame F in the
following. Consider a T-frame f of F. We attempt to schedule all path seg-
ments in f by inserting an initial random delay from [T] in front of every
segment. Then the expected number of packets crossing an edge at any time
step is bounded by v. Hence the following lemma can easily be shown by
using Chernoff bounds.
Lemma 7.8.2.
For any edge e and T-frame f in F it holds that for any
constant c > 0 there is a constant (~ ]or T such that with probability at least
1 - T -c the contention at e in f is at most 2v.
Consider, for some T-frame f, the schedule for f after inserting the initial
random delays. We attempt to schedule all f-segments in this new schedule
in an interval of length 2T- 2v by allowing 2v steps for the simulation of
each step. Let an edge be called
blocked
in f if it does not fulfill Lemma 7.8.2
for f. An f-segment is called
successful
if it does not cross an edge that is
blocked in f. Otherwise the f-segment
fails.
From Lemma 7.8.2 we get that
the probability of an F-segment to fail in some T-frame in F is bounded by
an inverse polynomial in T. However, we would like each F-segment to fail
only with probability bounded by an inverse exponential in T. This is where
we have to use a catch-up track to help packets catch up with the schedule
after they fail. The key feature of the catch-up track is that the congestion
there is much lower with sufficiently high probability, as the following analysis
shows.
First we bound the number of failed F-segments that cross any particular
edge e. Note that this includes not only segments that fall at e, but also all
segments that were supposed to cross e, but fall due to some edge e ~. Hence
the failure of different F-segments through e may be highly correlated. In
order to cope with the correlations, we introduce the following lemma, which
extends the Chernoff bounds.
Lemma
7.8.3.
Assume that the maximum degree in the dependency graph
of N binary random variables X1,..., XN is at most k, and suppose that for
N X
all i, E[Xi] < p. Let X = ~i=l i and 5 ~ l. Then,
Pr IX > 4eJpN] <
4ek2 -6pN/k
Proof.
By Theorem 3.3.2, the dependency graph can be partitioned into at
most k § 1 independent sets, and therefore into m _ 4ek independent sets,