Average case analysis of routing on Butterfly networks

Lecturer: Abhiram Ranade Note-taker : Milind Joshi CS 292 K, Fall 89

October 20, 1989

Topics: Single pass routing

• unbuffered

• buffered

1 Unbuffered Routing

When two packets collide at a link one of them is just dropped and other is let through.( collisions at nodes are allowed)

Worst case: Only \sqrt{N} packets get through. Consider the \sqrt{N} leaf trees we saw in the last lecture. Only one packet from each such group can get through, for a total of \sqrt{N} packets.

Average case: Assume each packet is destined for a random output node.

• How many packets get through in one pass?

• How many passes do we need to deliver all packets?

A good answer to the second question is not known. We examine the first question here.

Assume that probability of arrival of packet on a link entering a node at level i is P_{i}.

Now each input packet has equal probability of ending up on any of the links going out of the node. Thus, P_{i+1} = prob(receiving packet on the top link OR receiving packet on the bottom link)

= prob(receiving on the top link) +prob(receiving on the bottom link) −prob(receiving on both the links)

= \frac{P_{i}}{2} + \frac{P_{i}}{2} − \frac{P_{i}^{2}}{4}

= P_{i}(1 − \frac{P_{i}}{4} )

Thus we get the result

P = P_{log N} = \frac{4P_{1}}{4 + P_{1} log N}

Suppose P_{0} = 1, in which case we get

P_{1} = 0.5

P_{2} = 0.43

P_{3} = 0.39

P_{4} = 0.35

P_{5} = 0.32

P_{6} = 0.30

This means that, no. of packets delivered

= 2P_{log N}N = \frac{8P_{1}N}{4 + P_{1} log N} = \frac{8P_{0}N}{8 + P_{0} log N}

⇒ fraction of packets delivered

= \frac{8}{8 + P_{0} log N}

if P_{0} = \frac{1}{log N} then expected fraction delivered = 8/9 ≈ 90%

In the BBN butterfly we have capacities associated with the links. If the no.of packets is more than the capacity then the extra packets get dropped.

when capacity is q, throughput

= O(\frac{N}{(log N)^{q/2}} )

⇒ When the capacity is 2, throughput

= O(\frac{N}{(log N)^{1/2}} )

In the actual programs the addresses generated are not random. Hence average case analysis is not very useful. It is possible to use hash functions to randomize memory accesses, though. However, the above analysis does not place bounds on the amount of time it takes for a single set of packets to get through.

1.1 Unbounded Queues at the Nodes

Theorem 1 N = 2^{r} packets with random destinations can be transmitted with delay k log N with probability ≥ 1 − N^{−k} for k ≥ 3.

STRATEGY :

• Estimate expected delay μ for a fixed packet P.

• Show that total delay = sum of the independent contributions

• Use independence to show that prob(delay≥ 8μ) → 0.

• Show that this happens for every packet.

Lemma 1 Whenever some packet P waits for time δ then there exist δ packets that share an edge with p.

Proof:We know that δ = ∑_{i} δ_{i} where δ_{i} is the waiting time at level i. A packet waited for time δ_{i} in a queue means there were δ_{i} packets in queue when it reached node i. But this is not enough to prove that ∑_{i} δ_{i} is the no. of packets in front because same packet can keep delaying again and again.

But the queue has length δ_{i} means that at some time that many packets came from the other link, as otherwise the queue would not have formed. This means that at each node at level i these δ_{i} packets which came from the other link when the queue formed are in front of our packet. Since these different δ_{i} packets get added at each node in level i , there must be ∑_{i} δ_{i} packets in front.

Lemma 2 The expected number of packets entering the path of a packet P is \frac{1}{4} log N.

Proof:The expected number of packets passing through any edge in any level is the same, since all edges are symmetrical. This number is therefore \frac{1}{2}, since there are N packets traversing each level containing 2N edges.

The expected number of packets that pass through the log N nodes on the path of P is thus \frac{1}{2} log N; the number which actually share an edge with p is thus \frac{1}{4} log N.

1.2 Proof of main theorem

We shall use a theorem due to Hoeffding which says that with independent trials, the probability of significant deviation from the expected value is small. This is true even if the trials are not identical.

Theorem 2 (Hoeffding) If we have N independent Poisson trials with respective probabilities p_{1}, …, p_{N}, with Np = ∑ p_{i}, and m ≥ Np + 1 is an integer, the probability of at least m successess is at most B(m, N, p) =

∑_{i=m}^{N} \binom{N}{m}(1−p)^{N−m}p^{m} ≤ (\frac{Np}{m})^{m} (\frac{N−Np}{N−m})^{N−m} ≤ (\frac{Np}{m})^{m} e^{m−Np} ≤ (\frac{Npe}{m})^{m}, where e is the base of the natural logarithm.

In our case, each packet corresponds to a single independent trial. The trial succeeds if it shares an edge with packet P. All packets are not equally likely to succeed, but the expected number of successes Np = \frac{1}{4} log N. Thus the probability that a packet faces delay of m = k log N is at most

( \frac{\frac{1}{4}e log N}{k log N} )^{−k log N} ≤ (\frac{4k}{e} )^{−k log N}

Thus the probability that no packet has delay k log N is at most

N (\frac{4k}{e} )^{−k log N} = (\frac{2k}{e} )^{−k log N} ≤ N^{−k}

for k ≥ e.