next up previous
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 tex2html_wrap_inline1659 bits of addressing information if it is still a distance tex2html_wrap_inline1661 away from its destination. Without this assumption, the lower bound is tex2html_wrap_inline1663 bit steps.

Let us first define the notion of a randomized oblivious routing algorithm. We shall assume that our network is a directed graph tex2html_wrap_inline1665 , 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 tex2html_wrap_inline1673 be the set of all paths from u to v. For a given randomized routing algorithm let tex2html_wrap_inline1679 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:




A randomized oblivious routing algorithm is one in which all distinct random variables tex2html_wrap_inline1695 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 tex2html_wrap_inline1697 bit steps and beat the lower bound.

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

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 tex2html_wrap_inline1739 and a random path from v to t according to the tex2html_wrap_inline1745 , then x will be contained in the path with probability tex2html_wrap_inline1749 . 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 tex2html_wrap_inline1757 .

The goal of the proof is to show that there are many edges e that have many nodes v for which tex2html_wrap_inline1763 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 tex2html_wrap_inline1771 for which tex2html_wrap_inline1773 is large and u is far away from tex2html_wrap_inline1777 . Henceforth, we use the notation tex2html_wrap_inline1779 to denote the minimum distance between x and any element of T in the graph.


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


Observe that tex2html_wrap_inline1821 . 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 tex2html_wrap_inline1841 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 tex2html_wrap_inline1853 reveals that tex2html_wrap_inline1855 .

For each tex2html_wrap_inline1857 , define tex2html_wrap_inline1859 to be the subset of nodes in T that are not within distance tex2html_wrap_inline1863 of u. Since the maximum node degree is d, there are at most tex2html_wrap_inline1869 nodes within distance h of a node. Hence, there are at most tex2html_wrap_inline1873 nodes within distance tex2html_wrap_inline1875 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 tex2html_wrap_inline1897 , we know that there are tex2html_wrap_inline1899 pairs of nodes tex2html_wrap_inline1901 , where tex2html_wrap_inline1903 , and each pair has an associated subset tex2html_wrap_inline1905 such that tex2html_wrap_inline1907 and tex2html_wrap_inline1909 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 tex2html_wrap_inline1913 node-edge pairs tex2html_wrap_inline1915 for which tex2html_wrap_inline1917 , tex2html_wrap_inline1919 , tex2html_wrap_inline1921 , and tex2html_wrap_inline1923 . 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 tex2html_wrap_inline1929 nodes tex2html_wrap_inline1931 for which tex2html_wrap_inline1933 , tex2html_wrap_inline1935 , and tex2html_wrap_inline1937 .

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 tex2html_wrap_inline1947 packets passing through it that are tex2html_wrap_inline1949 steps away from their destination is at most tex2html_wrap_inline1951 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 tex2html_wrap_inline1955 fraction of the possible permutations finished in fewer than tex2html_wrap_inline1957 bit steps with probability exceeding tex2html_wrap_inline1959 , then we would have more than a tex2html_wrap_inline1961 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 tex2html_wrap_inline1965 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 tex2html_wrap_inline1971 nodes tex2html_wrap_inline1973 , where S=T=V, such that for tex2html_wrap_inline1977 ,


where tex2html_wrap_inline1981 and tex2html_wrap_inline1983 . Such an edge and set of nodes is guaranteed to exist by Lemma 4.2. We first select a random destination tex2html_wrap_inline1985 from tex2html_wrap_inline1987 and a random path tex2html_wrap_inline1989 from tex2html_wrap_inline1991 for tex2html_wrap_inline1993 . Since tex2html_wrap_inline1995 , we know that the path tex2html_wrap_inline1997 contains e and continues afterward for at least tex2html_wrap_inline2001 steps with probability at least tex2html_wrap_inline2003 .

We next select a random destination tex2html_wrap_inline2005 from tex2html_wrap_inline2007 and a random path tex2html_wrap_inline2009 from tex2html_wrap_inline2011 for tex2html_wrap_inline2013 . Since


we know that tex2html_wrap_inline2015 uses e and continues afterward for at least tex2html_wrap_inline2019 steps with probability at least tex2html_wrap_inline2021 . Moreover, we know that this probability is independent of the probability that tex2html_wrap_inline2023 uses e and continues afterward for tex2html_wrap_inline2027 steps.

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


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


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

We now start over again, setting tex2html_wrap_inline2069 and tex2html_wrap_inline2071 . Since tex2html_wrap_inline2073 , tex2html_wrap_inline2075 , and we can apply Lemma 4.2 to find an edge tex2html_wrap_inline2077 and nodes tex2html_wrap_inline2079 such that for tex2html_wrap_inline2081


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


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

We can repeat this whole process tex2html_wrap_inline2101 times before violating our condition that S and T have more than tex2html_wrap_inline2107 nodes. Each repetition we select destinations and paths for m more nodes. Each time we severely congest an edge with probability at least tex2html_wrap_inline2111 . 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 tex2html_wrap_inline2113 with probability tex2html_wrap_inline2115 .

to .667emto .667em

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

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