next up previous
Next: 2.3.2 Variable-length messages Up: 2.3 Analysis Previous: 2.3 Analysis

2.3.1 Packet combining

For simplicity, we have heretofore ignored the possibility of combining multiple packets with the same destination. In many routing applications, there is a simple rule that allows two packets with the same destination to be combined to form a single packet, should they meet at a node. For example, one of the packets may be discarded, or the data carried by the two packets may be added together. Combining is used in the emulation of concurrent-read concurrent-write parallel random-access machines [29] and distributed random-access machines [23].

If the congestion is to remain a lower bound when combining is allowed, then its definition must be modified slightly. The new congestion of an edge is the number of different destinations for which at least one packet's path uses the edge. Thus, several packets with the same destination contribute at most one to the congestion of an edge.

In order to efficiently combine packets, we will use a random hash function to give all of the packets with the same destination the same rank. Since ties in rank are broken according to destination, a node will not send a packet in one of its queues unless it is sure that no other packet for the same destination will arrive later in another queue. Thus, at most one packet for each destination traverses an edge.

We assign ranks using the universal hash function [7]


which maps a destination tex2html_wrap_inline2477 to a rank in tex2html_wrap_inline2479 with k-wise independence. Here P is a prime number greater than the total number of destinations, and the coefficients tex2html_wrap_inline2485 are chosen at random. We show below that it suffices to choose tex2html_wrap_inline2487 . The random coefficients use tex2html_wrap_inline2489 random bits. In most applications, only tex2html_wrap_inline2491 -wise independence is needed and the number of possible different destinations is at most polynomial in N, so the hash function requires only tex2html_wrap_inline2495 bits of randomness.

In the proof of Theorem 2.9, the ranks of the w packets in a delay sequence were chosen independently, i.e., with w-wise independence. In order to use a hash function with m-wise independence, where m may be much smaller than w, we need the following lemma, which shows that in any delay sequence there are smaller subsequences of many different sizes.


Proof: Suppose that an tex2html_wrap_inline2513 -delay sequence occurs. Divide the packet sequence tex2html_wrap_inline2515 into tex2html_wrap_inline2517 contiguous subsequences such that each subsequence has at least tex2html_wrap_inline2519 packets. This also partitions the delay path into subpaths. Let tex2html_wrap_inline2521 denote the length of the ith subpath and let tex2html_wrap_inline2525 denote the range of ranks for the ith subsequence, i.e., tex2html_wrap_inline2529 is the difference between the largest rank in subsequence i and the largest rank in subsequence i-1. We know that there must be fewer than tex2html_wrap_inline2535 segments with tex2html_wrap_inline2537 , since tex2html_wrap_inline2539 . Furthermore there must be fewer than tex2html_wrap_inline2541 segments satisfying tex2html_wrap_inline2543 , since tex2html_wrap_inline2545 . Thus there must exist some segment for which tex2html_wrap_inline2547 and tex2html_wrap_inline2549 .

to .667emto .667em


Proof: The proof is similar to that of Theorem 2.9. If some packet is not delivered by step L+w then by Lemma 2.5 an tex2html_wrap_inline2573 -delay sequence occurs. By Lemma 2.10, for any tex2html_wrap_inline2575 a tex2html_wrap_inline2577 -delay sequence also occurs. The hash function will be tex2html_wrap_inline2579 -wise independent. We will show that for the right choices of w and tex2html_wrap_inline2583 , it is unlikely that any such sequence occurs.

The number of different tex2html_wrap_inline2585 -delay sequences is bounded as follows. A delay path starts at node on some packet's path. Thus, there at most tex2html_wrap_inline2587 starting points for the path. At each node on the path, there are at most tex2html_wrap_inline2589 choices for the next node on the path. Thus, the total number of ways to choose the path is at most tex2html_wrap_inline2591 . The number of ways of choosing tex2html_wrap_inline2593 switches on the path is at most tex2html_wrap_inline2595 . The number of ways of choosing tex2html_wrap_inline2597 packets that pass through those switches is at most tex2html_wrap_inline2599 . The number of ways of choosing the ranks for the packets is at most tex2html_wrap_inline2601 since there are R choices for the rank of the first packet, and the ranks of the other tex2html_wrap_inline2605 differ from the first by at most tex2html_wrap_inline2607 .

If the ranks of the packets are chosen using a tex2html_wrap_inline2609 -wise independent hash function, then the probability that any particular delay sequence occurs is at most tex2html_wrap_inline2611 . Thus, the probability that any delay sequence occurs is at most


Using the inequality tex2html_wrap_inline2615 to bound tex2html_wrap_inline2617 , and tex2html_wrap_inline2619 to bound tex2html_wrap_inline2621 by tex2html_wrap_inline2623 , and tex2html_wrap_inline2625 , tex2html_wrap_inline2627 , and tex2html_wrap_inline2629 to bound tex2html_wrap_inline2631 by tex2html_wrap_inline2633 , our upper bound becomes


Removing constants so that we can better understand the expression, we have


If tex2html_wrap_inline2639 , then for any constant tex2html_wrap_inline2641 there are constants tex2html_wrap_inline2643 and tex2html_wrap_inline2645 such that for tex2html_wrap_inline2647 and tex2html_wrap_inline2649 , the probability is at most tex2html_wrap_inline2651 . If tex2html_wrap_inline2653 then for any tex2html_wrap_inline2655 there is a tex2html_wrap_inline2657 such that tex2html_wrap_inline2659 and tex2html_wrap_inline2661 and for tex2html_wrap_inline2663 , and tex2html_wrap_inline2665 , the probability is at most tex2html_wrap_inline2667 .

to .667emto .667em

next up previous
Next: 2.3.2 Variable-length messages Up: 2.3 Analysis Previous: 2.3 Analysis

Bruce Maggs
Mon Jul 22 22:57:44 EDT 1996