Section 13.10. Exercises | Computer and Communication Networks (paperback)

13.10. Exercises

1.	Compare the complexity of crossbars and Delta networks in one plotting chart, in which the network size varies over the range n = 2 ² , 2 ⁴ , and 2 ⁵ . For the Delta networks, assume that d = 2.
2.	For the following switching networks D _16,2 and D _16,4 . Sketch the networks. Compare D _16,2 and D _16,4 in terms of complexity and communication delay.
3.	For the following switching networks _16,2 and _16,4 : Sketch the networks with the minimum number of stages that provide all possible input/output connections. Compare the two networks in terms of complexity and communication delay.
4.	Using the blocking-probability estimation method, derive an expression for the internal blocking of the two networks _16,2 and _16,4 .
5.	For the following switching networks, B _16,2 and B _16,4 : Sketch the networks. Compare B _16,2 and B _16,4 in terms of complexity and communication delay.
6.	Using Lee's method (discussed in Chapter 7), derive an expression for the internal blocking of B _16,2 and B _16,4 networks.
7.	For the following switching networks Y _16,2 and Y _16,4 : Sketch the networks. Is there any self-routing rule existing for Banyan networks?
8.	For the following switching networks B _9,3 and ‰ _9,3 : Sketch the networks. Compare B _9,3 and ‰ _9,3 in terms of complexity, internal blocking, and communication delay.
9.	Delta networks can be improved by extending stages of switching. For d , s , and h with h < s and n = d ^s , we define the extended Delta network as . Sketch a picture of an extended Delta network with eight inputs/outputs, using switch elements of size 2. Derive an equation for the complexity of this network. Derive an equation for the blocking probability.
10.	Design an n = 8 port three-stage Clos switching network. Find d and k that meet the minimum nonblocking condition, and sketch the network. To design a nonblocking Clos network, the network is nonblocking as long as k = 2 d - 1. Why would anyone want to design a network with k> 2 d - 1?
11.	Compare the complexity of large-scale three-stage and five-stage Clos switching systems, where the number of ports varies from 1,000 ports to 2,000 ports.
12.	For any nonblocking switching network, Lee's method can still estimate some blocking. Justify this contradiction.
13.	There are two ways to design a three-stage Clos network with six inputs and six outputs yielding the "minimum" nonblocking operation. Select dimensions for both types of crossbars used in either of the two types of networks, and sketch the networks. Show a Lee's model for both networks, and find the total blocking probability for any of the networks. Which choice is better? (Compare them from all possible aspects.)
14.	To design a five-stage Clos network with n = 8 and d = 2 yielding "minimum" nonblocking operation: Select dimensions for all three types of crossbarsno complexity optimizations neededand sketch the network. Show a Lee's model. Assuming the probability that any link in the networks is busy is p = 0.2, find the total blocking probability for the network.
15.	To increase the speed and reliability of the five-stage Clos network using , we form three multiplexed parallel planes, each of which contains this network. Sketch the overview of the network. Show a Lee's model. Assuming the probability that any link in the networks including multiplexing links is busy is p = 0.2, find the total blocking probability for the network.
16.	To design a five-stage Clos switching network with n inputs and n outputs: Give dimensions for all five types of crossbars to yield nonblocking operations. Select dimensions for all five types of crossbars to yield nonblocking operation and minimum crosspoint count. (No optimizations is needed.)
17.	Design a shared-memory switching system that supports up to 16 links and uses a multiplexer, RAM, and a demultiplexer . The multiplexer output carries 16 channels, each as wide as a segment (packet fragment). Each segment is as large as 512 bytes, including the segment header for local routing. A total of 0.4 µ s form a frame at each multiplexer. RAM is organized in 32-bit words with 2 ns write-in time, 2 ns read-out time, and 1 ns access time (controller process) per word. Find the minimum required size of RAM. Find the size of a RAM address. Find the maximum bit rate that can be supported at the output of RAM. Find the speed of this switch, which is the segment-processing rate per second per switch port.
18.	Computer simulation project . Write a computer program to simulate a 2 x 2 crossbar switch. Assign each packet a switch-output destination at random. Construct and simulate a single crosspoint. Clearly demonstrate how it switches on and off, using a central crossbar controller. Extend your program to construct a four-crosspoint crossbar.
19.	Computer simulation project . Carry the program you developed for a single buffer in Chapter 11 (computer simulation project) and extend the preceding 2 x 2 crossbar switch to a switch with a simple buffered input port. Each of the two inputs of the switch has a buffer with K = 64 buffer slots, and each slot can fit only in a packet of size 1,000 bytes. Dynamically assign packets of different size every 1 ms, and send out a packet to the switch every t seconds from the buffer. Assign each packet a switch-output destination at random. Construct, simulate, and test each of the two buffers individually. Integrate these two buffers with the switch, and measure the performance metrics of both buffers together, given different values of t . Measure average delay for a packet.