In this section we prove that any randomized oblivious routing algorithm takes

bit steps with high
probability for almost all permutations, where *M* is the minimum
packet size not including addressing information, *N* is the size of
the network and *d* is the maximum degree of the network. The proof
is similar to the classic Borodin-Hopcroft lower bound proof
[7] but extends their method and result in two ways.
First, the lower bound applies to almost all permutations, and second,
it applies to a wider class of algorithms: randomized oblivious
algorithms as opposed to deterministic oblivious algorithms. Our only
assumption is that each packet has at least bits of
addressing information if it is still a distance away from
its destination. Without this assumption, the lower bound is
bit steps.

Let us first define the notion of a randomized oblivious routing
algorithm. We shall assume that our network is a directed graph
, where *|V|=N* and the in-degree and out-degree of every
node is at most *d*. Let *p* denote a sequence of edges which form a
path (not necessarily simple) in the graph; let be the set
of all paths from *u* to *v*. For a given randomized routing
algorithm let be the random variable denoting the
path from *u* to *v* chosen by the algorithm. Using this notation,
for any node or edge *x* and for all nodes *u* and *v* we have the
following:

and

A *randomized oblivious* routing algorithm is one
in which all distinct random variables are
independent.

We should discuss how the definition of obliviousness applies to networks which have multiple edges. We consider each edge of a bundle of multiple edges to be distinct so that paths which use different edges in the same bundle are considered to be different. This implies that oblivious algorithms on networks with multiple edges must be oblivious to the choice of edges within bundles of edges. Hence, even though our routing algorithm for the dilated butterfly chooses the nodes along a packet's path obliviously, it is not an oblivious algorithm because the choices of edges within a bundle depended upon the choices made by other packets. This is what allows us to achieve bit steps and beat the lower bound.

Networks where edges have capacity *c* (and degree ) are
considered to be networks with multiple edges and degree .
Hence, for an *N* node hypercube with capacity on its edges,
i.e., , we find that any randomized oblivious algorithm
takes bit steps
with high probability, even if . In fact, messages typically
have length . For , the bound
is . More generally, if , the bound is .

Given a randomized oblivious routing algorithm for a network we would
like a measure of how likely it is for a node or edge to be in a
randomly selected set of paths. For any node *v*, any set of nodes
*T*, and any node or edge *x*, we define the *weight* of *x*
with respect to *v* and *T* to be

Note that the weight of a node is equal to the sum of the weights of its incoming (or outgoing) edges.

Observe that if we choose a random destination and a random
path from *v* to *t* according to the , then *x* will
be contained in the path with probability
. Similarly, if we choose a random path
from *v* to a randomly selected destination in *V*, then *x* will be
contained in the path with probability at least
.

The goal of the proof is to show that there are many edges *e* that
have many nodes *v* for which is large for some
*T*. Then we will be able to argue that many edges have at least
some chance of having many packets pass through them. (We will also
argue that these packets still have a long way to go after using the edge
in order to show that many bits are likely to pass through the
edge.) Then we will conclude that at least one of these
edges has high congestion with very high probability.

We start by proving that for any node *v* and any large set *T*, there
are many pairs for which is
large
and *u* is far away from . Henceforth, we use the notation
to denote the minimum distance between
*x* and any element of *T* in the graph.

**Proof:**
Consider the set of nodes
where .
Observe that is a lower bound for ,
since and
for all *t*. Now we will derive
an upper bound for in terms of *|U|*. This in turn will
imply a lower bound for *|U|*. By
definition,

Observe that . For any path in the preceding sum from *v*
to a node in *T-U* let *y* be the first node not in *U* and let
*Y* be the set of all *y*. We can partition the paths according to
*Y* as follows:

This is bounded by
since the size of *Y* is at most *d|U|* and the
weight of any node not in *U* is at most *k*.
Thus,

Combining the two inequalities for reveals that .

For each , define to be the subset of nodes in *T* that
are not within distance of *u*. Since the maximum node degree is *d*,
there are at most nodes within distance *h* of a node.
Hence, there are at most nodes within distance
of *u*, and thus

to .667emto .667em

The above lemma allows us to show that there is an edge with large weight.

**Proof:**
By Lemma 4.1 and the fact that , we
know that there are pairs of nodes , where ,
and each pair has an associated subset
such that
and
Recall that the weight of a node is equal to the sum of the
weights of its incoming edges and that
every node has maximum in-degree *d*. Hence, there
are at least node-edge pairs for which
, , , and .
Since there are at most *dN* edges, we can therefore conclude that
there is at least one edge *e* for which there are at least
nodes for which , , and .

to .667emto .667em

We are now ready to prove the lower bound on randomized oblivious algorithms.

**Proof:**
We will show that for a random permutation, the probability
that every edge has fewer than
packets passing through it that are steps away
from their destination is at most for a sufficiently
small constant *c*. In this case, the probability is taken over the
choice of permutations as well as the choice of paths. This directly
implies the theorem since if more than an fraction of
the possible permutations finished in fewer than bit steps with probability
exceeding , then we would have more than a
chance of finishing in fewer steps with a random
permutation which is not possible.

We will construct the random permutation by determining one path at a time.
We will randomly select a path for each node *v* in a specified sequence,
selecting paths from the distributions for where *u* is
randomly selected from the nodes not already designated to receive a packet.
(The constraint of constructing a random *permutation* rather than
a random destination requires that at most one packet be delivered to
any node. The argument for random destinations is somewhat easier.)

We start by selecting an edge *e* and nodes
, where *S=T=V*, such that for ,

where and .
Such an edge and set of nodes is guaranteed to exist by
Lemma 4.2. We first select a random destination from
and a random path from for . Since
,
we know that
the path contains *e* and continues afterward for at least
steps with probability at least
.

We next select a random destination from and a random path from for . Since

we know that uses *e* and continues afterward for at least
steps with probability at least
. Moreover, we know that this probability is independent
of the probability that uses *e* and
continues afterward for steps.

Arguing in a similar fashion, we can show that
each use *e* and continue afterward for at least
steps with probability , and that
these probabilities are independent. Since there are
paths, each using *e* and continuing afterwards for
steps with probability ,
the probability that at least

paths use *e* and continue afterwards for steps
is at least

for some constant and sufficiently large *N*.
By selecting *c* to be a small enough constant, this
probability can be made to be at least . In other words, at least
bits
pass through *e* from packets starting at nodes
with probability at least .

We now start over again, setting and . Since , , and we can apply Lemma 4.2 to find an edge and nodes such that for

where and . Arguing just as before (except that now is selected uniformly from ) we can prove that at least

bits pass through from packets starting at nodes with probability at least .

We can repeat this whole process
times before violating our condition that *S* and
*T* have more than nodes.
Each repetition we select destinations and paths for *m* more
nodes. Each time we severely congest an edge with probability at least
. Since these probabilities are all independent, the
probability that none of the edges is severely congested is at most

Hence for a random permutation and random path selection, the running time will be with probability .

to .667emto .667em

Mon Jul 22 17:37:10 EDT 1996