next up previous
Next: 2.3 Improving the constant Up: 2 Routing without faults Previous: 2.1 The algorithm

2.2 The analysis


We will analyze the behavior of the greedy algorithm described in Section 2.1 by means of a potential function argument. In particular, we will assign each packet in wave i tex2html_wrap_inline1523 weight tex2html_wrap_inline1525 for some fixed tex2html_wrap_inline1527 to be determined later, and we will define the potential of a switch on level k tex2html_wrap_inline1531 to be tex2html_wrap_inline1533 if k is odd, and tex2html_wrap_inline1537 if k is even, where w < 1 is also a constant to be determined later. Thus, the potential of a packet in the ith wave at the kth level is tex2html_wrap_inline1547 if k is odd, and tex2html_wrap_inline1551 if k is even, and the potential of the system is the sum of potentials of the packets. By varying the values of tex2html_wrap_inline1555 and w, we can obtain different bounds on the running time of the algorithm as follows.




The key fact necessary to prove Theorem 2.1 is that the potential of the system drops by a constant fraction during each stage. In particular, we will need to prove the following claim.


The main idea behind proving Claim 2.4 is that during any stage of the algorithm, a reasonable number of the heaviest packets move forward, thereby decreasing the potential of the system by a constant fraction. To formalize this intuition, we will need the following series of lemmas.


Proof: Consider any edge e. At some step of the phase, the algorithm looks at the head and tail of e, and rearranges packets (if any) so that the heavier weight packet is sent to the head of e. In subsequent steps, only a packet with greater weight can be moved into the head of e, and only packets with lesser weight can move into the tail of e. Hence at the end of the phase, the weight of the packet at the head of e is at least as great as the weight of the packet at the tail of e, if any. (Nonexistent packets can be considered to have zero weight.)

to .667emto .667em

In what follows, let tex2html_wrap_inline1591 denote the sum of the weights of the r heaviest upward-destined packets left at the inputs of a splitter after a phase of routing through the splitter. If there are fewer than r upward-destined packets left at the inputs, then tex2html_wrap_inline1597 denotes the weight of all of them. A similar definition holds for tex2html_wrap_inline1599 and also for tex2html_wrap_inline1601 and tex2html_wrap_inline1603 , which denote the sum of the weights of the r heaviest packets in the upper and lower outputs, respectively.


Proof: For simplicity, we will only argue the result for upward destined packets. The proof for lower-destined packets is identical.

We will prove by induction on r that tex2html_wrap_inline1617 . For r=1, the result follows from Lemma 2.5 and the fact that every input is adjacent to tex2html_wrap_inline1621 upper outputs. Now assume the result is true for r=k-1, and look at the k heaviest upward-destined packets left at the inputs of the splitter. By the expansion property, we know that the inputs containing these packets are incident to at least tex2html_wrap_inline1627 upper outputs. By Lemma 2.5, each of these outputs contains a packet of weight at least tex2html_wrap_inline1629 (i.e., the weight of the kth heaviest upper-destined packet left at an input). Hence, there are tex2html_wrap_inline1633 or more upper outputs containing packets with weight at least tex2html_wrap_inline1635 , and by induction, the tex2html_wrap_inline1637 heaviest of these account for at least tex2html_wrap_inline1639 weight. Thus,


thereby verifying the inductive hypothesis.

to .667emto .667em


Proof: For simplicity, we will only consider upward-destined packets. The same argument holds for lower-destined packets. Arrange the packets at the inputs in order of decreasing weight. Since tex2html_wrap_inline1649 , at most tex2html_wrap_inline1651 of these packets can belong to any wave. Hence the weight of the tex2html_wrap_inline1653 th heaviest packet is at most tex2html_wrap_inline1655 times the weight of the ith heaviest packet for all i. Since the weight of the tex2html_wrap_inline1661 heaviest packets is tex2html_wrap_inline1663 by definition, the total weight of all the upper-destined packets at the inputs is at most


as claimed.

to .667emto .667em


Proof: By Lemma 2.6, the total weight of packets on the upper and lower outputs is at least tex2html_wrap_inline1673 . By Lemma 2.7, the total weight of packets left at the inputs is at most tex2html_wrap_inline1675 . Hence the total weight on the outputs is at least tex2html_wrap_inline1677 times the total weight on the inputs, and thus at least a tex2html_wrap_inline1679 fraction of the weight is on the outputs.

to .667emto .667em


We are now ready to prove Claim 2.4 and Theorem 2.1.

Proof of Claim 2.4: Let tex2html_wrap_inline1689 denote the weight at the beginning of the stage in levels l and l+1, where l is even. If V is the potential of the system at the beginning of the stage, then


During the first phase of the stage, packets move from even levels to odd levels. This does not change the potential of the system since each even level has the same potential as the next odd level. However, it does ensure that the weight in odd level l+1 is at least tex2html_wrap_inline1703 and the weight in even level l is at most tex2html_wrap_inline1707 .

During the second phase, the weight in odd level l+1 is rearranged with the weight in even level l+2 for each l. By Corollary 2.9, and the argument of the previous paragraph, we know that at least tex2html_wrap_inline1715 weight moves from level l+1 to level l+2 for any l. Hence, the potential at the end of the stage is at most



as claimed.

to .667emto .667em

Proof of Theorem 2.1: To compute an upper bound on the running time of the algorithm, we now need only to compute the initial potential of the system and the potential at which we will be guaranteed that every packet has reached its destination at level tex2html_wrap_inline1727 .

To compute the initial potential, we will assume without loss of generality that the first L waves start in level 0, the next L waves start in level -1, and so forth. The total weight in the first L waves is at most


Similarly the weight of the ith group ( tex2html_wrap_inline1743 of L waves is at most


Hence the total initial potential is at most


The potential of a packet from the last wave on level tex2html_wrap_inline1751 is at most tex2html_wrap_inline1753 . Hence, all of the packets must have reached level tex2html_wrap_inline1755 (their destinations) once the total potential falls below this amount. Since the total potential drops by a factor of tex2html_wrap_inline1757 at every stage, the total number of stages can be at most S, where


Hence, it suffices to choose


Since each stage takes 4d steps, we can multiply by 4d to obtain the bounded stated in the theorem.

In order to show that tex2html_wrap_inline1769 , we need to show that there exist constants d, tex2html_wrap_inline1773 , tex2html_wrap_inline1775 , w < 1, and tex2html_wrap_inline1779 such that tex2html_wrap_inline1781 and tex2html_wrap_inline1783 . The key, of course, is showing that tex2html_wrap_inline1785 (i.e., that the potential of the system drops during every stage). If tex2html_wrap_inline1787 , then we can always find a value of w < 1 for which tex2html_wrap_inline1791 . (In particular, we can choose tex2html_wrap_inline1793 , for then tex2html_wrap_inline1795 .) In order for tex2html_wrap_inline1797 to be greater than tex2html_wrap_inline1799 , it suffices that tex2html_wrap_inline1801 . This can be accomplished for any tex2html_wrap_inline1803 by setting tex2html_wrap_inline1805 to be sufficiently small. Making tex2html_wrap_inline1807 small also guarantees that tex2html_wrap_inline1809 . Hence, we only need to choose d, tex2html_wrap_inline1813 , and tex2html_wrap_inline1815 so that tex2html_wrap_inline1817 , which can be done for any tex2html_wrap_inline1819 by choosing tex2html_wrap_inline1821 to be sufficiently small.

For example, we could choose d=11, tex2html_wrap_inline1825 , tex2html_wrap_inline1827 , L = 16, tex2html_wrap_inline1831 , tex2html_wrap_inline1833 , tex2html_wrap_inline1835 , and tex2html_wrap_inline1837 , to show that tex2html_wrap_inline1839 permutations can be routed in at most tex2html_wrap_inline1841 steps using the algorithm.

to .667emto .667em

next up previous
Next: 2.3 Improving the constant Up: 2 Routing without faults Previous: 2.1 The algorithm

Bruce Maggs
Mon Jul 22 18:45:42 EDT 1996