Mathematics for Computer Science

Chapter 10 Communication Networks296

in 0 in 2 in 4

out 0 out 1 out 2 out 3 out 4

in 1 in 3

Figure 10.5 5-Path

new, better communication network design. Her network has the following specifi-
cations: every input node will be sent to a butterfly network, a Benes network andˇ
a 2-d array network. At the end, the outputs of all three networks will converge on
the new output.
In the Megumi-net a minimum latency routing does not have minimum conges-
tion. Thelatency for min-congestion(LMC) of a net is the best bound on latency
achievable using routings that minimize congestion. Likewise, thecongestion for
min-latency(CML) is the best bound on congestion achievable using routings that
minimize latency.

2-d Array

Butterfly

Beneš

.

.

.

.

.

.

out 1

out 3

out 2

outN

in 1

in 3

in 2

inN

Fill in the following chart for Megumi’s new net and explain your answers.

network diameter # switches congestion LMC CML

Megumi’s net