CS-534: Packet Switch Architecture
Spring 2006		 Department of Computer Science
© copyright: University of Crete, Greece

Exercise Set 9:
Internal Blocking in Switching Fabrics

Assigned: Mon. 3 Apr. 2006 (week 8) - Due: Mon. 10 April 2006 (week 9)

[Lecture: 5.1 Inverse Multiplexing] [printer version - PDF]

9.1   Tree Networks and Internal Blocking

Consider the 8x8 network with a binary tree internal topology shown in figure 1(a), below. All links shown have a transmission capacity of 1.0, each. All boxes shown are switch elements with no internal blocking.

(a) Show a traffic pattern that saturates the 8+8=16 I/O links (the links connected to the ports P0 through P7), yet can be supported by this network; do not use the trivial traffic pattern where all traffic is among odd-even port pairs (neighbors) -- let some portion of the traffic go through the upper levels of the tree.

(b) Show a traffic pattern that canNOT be sustained by this network, although the capacity limits of the I/O links are not violated; in other words, give a traffic pattern that proves that this network exhibits internal blocking.

Binary Tree Network
Figure 1

(c) Now, consider the network of figure 1(b), which is identical to the one of figure 1(a) except that the links shown in thick lines (the upper two levels of links) have a transmission capacity of 2.0, each. Answer question (a) for this network (show that more "non-local" traffic can be supported this time).

(d) Answer question (b) for this latter network of figure 1(b), i.e. show that this network too has internal blocking.


9.2   Banyans, Dual Banyans, and Rearrangeably Non-blocking Fabrics

Consider the 4x4 network of figure 2(a), below. The 4+4=8 I/O links (the links connected to the ports P0 through P3) have a transmission capacity of 1.0, each. The 4 "internal" links, which are shown in thick lines, have a capacity of 2.0, each. All boxes shown are switch elements with no internal blocking (the switch element in the middle has twice the capacity of any one of the "outer" switch elements).

(a) Prove that the network of figure 2(a) has no internal blocking.

Dual banyan
Figure 2

(b) Now, consider the network of figure 2(b), which consists of two banyans connected back-to-back with their middle stages merged. This network can be thought of as resulting from that of figure 2(a), using inverse multiplexing for the double-rate links and switch. Here, all links have a capacity of 1.0, each. Notice that this is a multi-path network: there are more than one paths --actually two paths-- from any given input port to any given output port. Try finding a traffic pattern that cannot be sustained by this network although it is within the capacity limits of the I/O links; you will probably not find any, because this network has no internal blocking, when routing (path selection) in done in an appropriate way.

(c) When all packets of a flow follow a same, single path, show that flows in the dual-banyan network of figure 2(b) may need rerouting in order for the non-blocking property to be satisfied. Consider, for simplicity, flows of rate 1.0 each; in this case, there is a single flow per input port and a single flow per output port (flows among identically numbered ports are allowed). Start setting up flows, one by one, using one of the two possible routings for each new flow (in some cases, the flows that have already been established will dictate a single routing choice for the new flow). Give a sequence of such flow set-up's and routing choices such that when a request for a new flow arrives (between two non-busy ports), this new flow can only be satisfied if some previously established flow(s) are rerouted, i.e. previous routing decisions are revised. We call these rearrangeably non-blocking networks.

(d) The proper definition of inverse multiplexing differs from the routing assumption made in the first sentence of question (c). How would the routing choices of question (c) differ if proper inverse multiplexing is used? Would rerouting (revision of previous routing decisions) ever be needed if proper inverse multiplexing is used?

Up to the Home Page of CS-534
 		 © copyright University of Crete, Greece.
Last updated: 3 Apr. 2006, by M. Katevenis.