Next: 5 Acknowledgments Up: Fast Algorithms for Bit-Serial Previous: 3 Emulating the routing

# 4 Lower bounds on oblivious routing

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

Next: 5 Acknowledgments Up: Fast Algorithms for Bit-Serial Previous: 3 Emulating the routing

Bruce Maggs
Mon Jul 22 17:37:10 EDT 1996