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 to a rank in
with *k*-wise independence. Here *P* is a prime number
greater than the total number of destinations, and the coefficients
are chosen at random. We show below that it suffices to
choose . The random coefficients use random bits. In most applications, only -wise
independence is needed and the number of possible
different destinations is at most polynomial in *N*, so the hash
function requires only 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 -delay sequence occurs.
Divide the packet sequence into contiguous
subsequences such that each subsequence has at least packets. This also partitions the delay path into
subpaths. Let denote the length of the *i*th subpath and let
denote the range of ranks for the *i*th subsequence, i.e.,
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 segments with , since .
Furthermore there must be fewer than segments satisfying
, since . Thus there must exist some
segment for which and .

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 -delay sequence
occurs. By Lemma 2.10, for any a
-delay sequence also occurs.
The hash function will be -wise independent.
We will show that for the right choices of *w* and , it is
unlikely that any such sequence occurs.

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

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

Using the inequality to bound , and to bound by , and , , and to bound by , our upper bound becomes

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

If , then for any constant there are constants and such that for and , the probability is at most . If then for any there is a such that and and for , and , the probability is at most .

to .667emto .667em

Mon Jul 22 22:57:44 EDT 1996