Question 3:

Consider a 16 16 packet switch. Assume the incoming traffic is i.i.d. (independent and identically distributed). Throughput is referring to the per output port throughput.

If the switch is a cross-bar switch, what is the maximum throughput? Assume there is no input buffering.

Now let the switch be a Banyan switch. No input or internal buffering included.

What is the packet loss probability of this Banyan switch if the input traffic load is 0.8?

Label the input and output ports from 0 to 15 (uppermost as port 0). Six packets arrive to the input side: packet 1 at input port 1, destined to output port 12; packet 2 at input port 3, destined to output port 4; packet 3 arrives at input port 5, destined to output port 10; packet 4 at input port 9, destined to output port 1; packet 5 at input port 12, destined to output port 5; packet 6 at input port 14, destined to output port 4. Please show the internal paths taken by these six packets. If contention occurs at one switch module, the packet from the upper input port of the switch module will win.

Now let the switch be a Batcher-Banyan switch. Consider the six (6) incoming packets described in part 2) ii). Which packets will be switched to the output side in the current operation round? Justify your answer.