Mathematics for Computer Science

10.9. Bene ̆s Network 295

in 0

in 1

in 2

in 3

out 0 out 1 out 2 out 3

the first layer to the corresponding switch in the second layer. The inputs of the
2-Layer Array enter the left side of the first layer, and thenoutputs leave from the
bottom row of either layer.

(a)For any given input-output permutation, there is a way to route packets that
achieves congestion 1. Describe how to route the packets in this way.

(b)What is the latency of a routing designed to minimize latency?

(c)Explain why the congestion of any minimum latency (CML) routing of packets
through this network is greater than the network’s congestion.

Problem 10.5.
A5-pathcommunication network is shown below. From this, it’s easy to see what
ann-path network would be. Fill in the table of properties below, and be prepared
to justify your answers.

network # switches switch size diameter max congestion

5-path

n-path

Problem 10.6.
Tired of being a TA, Megumi has decided to become famous by coming up with a