 ## Exercises On Switching Architectures-Free PDF

• Date:16 Oct 2020
• Views:0
• Pages:112
• Size:5.48 MB

Share Pdf : Exercises On Switching Architectures

Report CopyRight/DMCA Form For : Exercises On Switching Architectures

Transcription:

1 Interconnection networks 2,1 1 Clos networks 2,1 1 1 Recursive construction 13. 1 1 2 Non interruptible networks 21,1 2 Benes networks 24. 1 3 Banyan networks 29,1 4 Cantor networks 33,1 5 Comparison among networks 35. 1 6 Lee method 38,1 7 Space time switching 45,2 Data centers 47. 2 1 Cloud computing 47,2 2 Design of data center networks 48.
3 Packet switches 59,3 1 Theoretical performance 59. 3 1 1 Bufferless switches 59,3 1 2 Input queued switch with single FIFO 63. 3 1 3 Generic switches with input and or output queueing 66. 3 2 Packet Scheduling in Input Queued Switches 68, 3 2 1 Scheduling algorithms for unicast traffic 68. 3 2 2 Scheduling algorithms for variable size packets 76. 3 2 3 Scheduling algorithms for QoS support 78, 3 2 4 Scheduling algorithms for multicast traffic 84. 4 Fast packet classification and SDN 92,4 1 Lookup tables for packet forwarding 92.
4 2 Software Defined Networking 96,5 Probabilistic data structures 99. 5 1 Hash tables and fingerprinting 99,5 2 Bloom filters 106. 5 3 Cuckoo filters 110,Interconnection networks,1 1 Clos networks. Exercise 1, Design a Clos network strictly non blocking of size 100 100 using modules 10 10 Compute. the final complexity in function of the complexity C 10 of the 10 10 module. p 10 N q 10,The resulting network is shown in figure 1 1.
To build a 10 19 module it is possible to use two modules 10 10 in parallel of which. the first 19 outputs are connected to the following 19 modules of the second stage as shown. in figure 1 2 The last output of the second 10 10 module in parallel will be idle but it will be. included in the computation of the total complexity of the network. CSN B 100 10 2C 10 19C 10 10 2C 10 59C 10,Exercise 2. Design a Clos network strictly non blocking 1000 1000 using only 10 10 modules Compute. the final complexity in function of C 10, Figure 1 1 Strictly non blocking Clos network 100 100. Figure 1 2 Architecture of a 10 19 module,100 19 100. Figure 1 3 Strictly non blocking Clos network 1000 1000. The resulting network is shown in figure 1 3,CSN B 1000 100 2C 10 19CSN B 100 100 2C 10. CSN B 1000 400C 10 19 59C 10 400 1121 C 10 1521C 10. Exercise 3, Design a Clos network rearrangeable 100 100 using modules 10 10 Compute the final.
complexity in function of C 10,The resulting network is shown in figure 1 4. CREARR 100 30C 10,Figure 1 4 Rearrangeable Clos network 100 100. 100 10 100,Figure 1 5 Rearrangeable Clos network 1000 1000. Exercise 4, Design a Clos network rearrangeable 1000 1000 using modules 10 10 Compute the final. complexity in function of C 10, Solution Rearrangeable REARR Clos network total inputs and outputs N 1000 10 10.
The resulting network is shown in figure 1 5, CREARR 1000 200C 10 10CREARR 100 200 10 30 C 10 500C 10. Exercise 5, Consider a Clos network rearrangeable 9 9 with p 3 and the following Paull matrix. being the modules of the second stage a b e c, 1 Draw the active connections in the network and write a possible set of input output con. nections satisfying the Paull matrix, Figure 1 6 Active connections according to the initial Paull matrix. IN P U T OU T P U T, 2 Connect module 1 of the first stage with module 1 of the third stage Recompute the Paull.
matrix and draw the corresponding connections Should the network be reconfigured Is. the solution unique, 3 Connect again module 1 of the first stage with module 1 of the third stage Recom. pute the Paull matrix and draw the corresponding connections Should the network be. reconfigured Is the solution unique, 1 Figure 1 6 shows the network with the active connections of the initial Paull matrix A. possible set of input output connections is the following. 2 No there exists an unique solution and the network is not reconfigured The Paull matrix. The final network is shown in figure 1 7, 3 Yes in this case the network is reconfigured and there exist two possible solutions The. first corresponds to P1 Paull matrix, The final network is shown in figure 1 8 The second solution corresponds to P2 Paull. Figure 1 7 Active connections according to the new Paull matrix. Figure 1 8 Network corresponding to P1,Figure 1 9 Network corresponding to P2.
The final network is shown in figure 1 9,Exercise 6. Consider a rearrangeable 9 9 Clos network with three modules at the first and third stages. and the following Paull matrix,being the modules of the second stage a b and c. 1 Draw the whole network with all the interconnection links. 2 Draw the active connections in the network and write a possible set of input output con. nections satisfying the Paull matrix, 3 Connect module 1 of the first stage with module 1 of the third stage Recompute the Paull. matrix and draw the corresponding connections Should the network be reconfigured Is. the solution unique, 4 Connect again module 1 of the first stage with module 1 of the third stage Recom. pute the Paull matrix and draw the corresponding connections Should the network be. reconfigured Is the solution unique, 5 In such Clos network independently from the specific Paull matrix above.
what is the minimum and the maximum number of second stage modules that can. be involved in any rearrangement, what is the minimum and the maximum number of pre existing connections that. could be rearranged, This exercise is almost identical to Ex 5 Regarding the last two questions the number of. second stage modules that are involved in any rearrangment is always 2 Thus the number of. pre existing connections that could be rearranged is between 1 and 4. Exercise 7, Design a Clos network rearrangeable 24 25 with n 6 and m 5 where n is the number. of inputs of the first stage modules and m is the number of outputs of the third stage modules. Consider the following Paull matrix, being a b c d e and f the modules of the second stage. 1 Draw the active connections in the network, 2 Connect module 1 of the first stage with module 1 of the third stage Recompute the Paull.
matrix and draw the corresponding connections Should the network be reconfigured Is. the solution unique, 3 Connect again module 1 of the first stage with module 1 of the third stage Recom. pute the Paull matrix and draw the corresponding connections Should the network be. reconfigured Is the solution unique,6x6 4x5 6x5,Figure 1 10 Rearrangeable Clos network 24 25. Solution The number of necessary modules is r1 4 and r3 5 respectively for the first and. third stage, 1 Figure 1 10 shows the network with the active connections corresponding to the initial. Paull matrix, 2 No there exists just one solution for which the network should not be reconfigured Paul. matrix becomes, where it was sufficient to add a link through f to connect the first module of the first stage.
to the third stage, 3 Yes in this case the network should be reconfigured There exist two equivalent solu. tions indeed from figure 1 10 it is possible to observe that the required connection can. be realized through two different modules c and d of the central stage By rearranging. the network and choosing to route the connection through c the following Paull matrix is. c f a b e d, By choosing instead to route the connection through d the following Paull matrix is ob. d f a b e c,Exercise 8, Compare the complexity of two symmetric Clos networks the first one that is strictly non block. ing and the second one that is rearrangeable Let N be the number of total ports and p be the. number of inputs for the first stage, 1 Compute the complexity in terms of contact points. 2 In the case of the rearrangeable network compute the value of p minimizing the com. plexity what is the final complexity, 3 Draw both Clos networks in the cases p 1 and p N.
Solution By setting q N p in the formulas of the Clos networks complexity. CSNB 2p 1 2N N 2 p2 CREARR 2pN N 2 p, Consider now the rearrangeable Clos network The minimum of CREARR is obtained for p. that can be computed by setting,CREARR N2 N,Hence the minimum complexity is. CREARR 2 2N N, In the case p 1 the Clos network degenerates into a crossbar N N for p N the. Clos network degenerates into two tandem crossbars Hence the complexity for p 1 is equal. to N 2 whereas for p N it is equal to 2N 2 Note that the optimal complexity is lower in both. Exercise 9, Design a rearrangeable switch of size 900 450 using only modules of size 10 10 with the. aim of minimizing the number of modules,1 Describe the architecture.
2 Compute the total number of modules required,3 Describe the configuration algorithm. 4 Write the formula to compute the minimum theoretical number of modules to build the. switch and to compare the actual complexity to the optimal one question out of scope. for the program 2019 20, Solution The 900 450 switch can be built using a Clos network in the following way. C900 450 90C10 10C90 45 45C10, where the 90 45 switch can be also built using a Clos network. C90 45 9C10 10C9 5 5C10, in which the last module of the last stage has 5 unconnected outputs Now observe that a 9 5. switch can be built with a 10 10 module hence,C90 45 24C10.
and finally,C900 450 375C10, Paul s algorithm is used to configure the network and should be applied recursively twice. The total number of configurations X is,thus the minimum number of modules is. log2 900 log2 450, Now it is possible to exploit Stirling approximation. log2 n x log2 n 1 44n 0 5 log2 n 1 32,and numerically obtain. which is almost half than the actual number of modules adopted for the design. Exercise 10, Design a rearrangeable switch of size 600 800 using only modules of size 10 10 with the.
aim of minimizing the number of modules,1 Describe the architecture. 2 Compute the total number of required modules,3 Describe the configuration algorithm. 4 Write the formula to compute the minimum theoretical number of modules to build the. switch and to compare the actual complexity to the optimal one question out of scope. for the program 2019 20,Exercise 11, Design a rearrangeable switch of size 400 800 using only modules of size 10 10 with the. aim of minimizing the number of modules,1 Describe the architecture. 2 Compute the total number of required modules,3 Describe the configuration algorithm.
4 Write the formula to compute the minimum theoretical number of modules to build the. switch and to compare it with the actual number of adopted modules question out of. scope for the program 2019 20,Exercise 12, Design a rearrangeable switch of size 500 1000 using only modules of size 10 10 with the. aim of minimizing the number of modules,1 Describe the architecture. 2 Compute the total number of required modules,3 Describe the configuration algorithm. Exercise 13, Design a rearrangeable switch of size 400 500 using only modules of size 10 10 with the. aim of minimizing the number of modules,1 Draw the architecture.
2 Compute the total number of required modules, 3 What is the simplest routing algorithm that can be adopted. C400 500 40 C10 10 C40 50 50 C10, Now the middle stage modules can be built as follows. C40 50 4 C10 10 C4 5 5 C10 4 C10 5 C10 5 C10 14 C10. C400 500 40 C10 10 14 C10 50 C10 230 C10,Exercise 14. Design a rearrangeable switch of size 2000 4000 using only basic modules of size 10 10. with the aim of minimizing the number of modules,1 Describe the architecture. 2 Compute the total number of required basic modules. 3 Describe the configuration algorithm, 4 What would have been the approximated number of modules if the switch was designed.
to be strictly non blocking,C4000 2000 600C10 10C400 200 2300C10. C400 200 60C10 10C40 20 170C10,C40 20 11C10, The corresponding strictly non blocking network is expected to have roughly twice the number. of basic modules,Exercise 15, Design a rearrangeable switch of size 4096 4096 using only modules of size 8 8 with the. aim of minimizing the number of modules, 1 What is the theoretical minimum number of modules needed For the sake of easy. computation use the following approximation N N N question out of scope for. the program 2019 20,2 Describe the proposed architecture.
3 Compute the total number of required modules, 4 Compare the total number of required modules with the minimum one obtained in ques. tion 1 question out of scope for the program 2019 20. 5 Describe how to configure the overall network, Solution One possible solution is to use 8 as factor for the recursive construction In this. C4096 1024C8 8C512 3584C8,C512 128C8 8C64 320C8, Another possible solution is to use N for the recursive construction In this case. C4096 3 64C64 4608C8, which is worse than the alternative solution with 8 as factor. The minimum number of modules C can be computed,Given the approximation.
log2 N N log2 N 0 5 log2 N,By simple computations by hand. log2 4096 49158 log2 8 25 5,and finally, Hence the devised architecture with factor 8 shows less than twice the number of modules. than the minimum one,Exercise 16 out of scope for the program 2019 20. Consider the design of an asymmetric N N switch with 0 1. 1 Compute the number of switching configurations supported by the switch. 2 What is the complexity reduction with respect to an N N switch when adopting an. optimal theoretical architecture What is the complexity reduction obtained by adopting. 1 2 3 3 2 1 c b a Figure 1 6 Active connections according to the initial Paull matrix INPUT OUTPUT 1 4 4 7 5 5 6 6 8 3 9 8 2 Connect module 1 of the rst stage with module 1 of the third stage