6. In Figure 1.4, observe that the paths from input 000 to output 111 and from input...
Question:
6. In Figure 1.4, observe that the paths from input 000 to output 111 and from input 101 to output 110 have a common edge. Therefore, simultaneous transmission over these paths is not possible; one path blocks another. Hence, the Omega and Butterfly networks are classified as blocking interconnection networks.
Let (n) be any permutation on {0 . . . n−1}, mapping the input domain to the output range.
A nonblocking interconnection network allows simultaneous transmission from the inputs to the outputs for any permutation.
Consider the network built as follows. Take the image of a butterfly in a vertical mirror, and append this mirror image to the output of a butterfly. Hence, for n inputs and outputs, there will be 2log2n stages. Prove that this network is nonblocking.
Step by Step Answer:
Distributed Computing Principles Algorithms And Systems
ISBN: 9780521876346
1st Edition
Authors: Ajay D. Kshemkalyani, Mukesh Singhal