Figure 1
1.1
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.
1.1.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).
1.1.b
Show a traffic pattern that canNOT be sustained by this network,
although it does not violate the capacity limits of the I/O links;
in other words, give a traffic pattern that proves
that this network has internal blocking.
Figure 1
1.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 1.1.a for this network
(show that more "non-local" traffic can be supported this time).
1.1.d
Answer question 1.1.b for this latter network of figure 1(b),
i.e. show that this network too has internal blocking.
1.2
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).
1.2.a
Prove that this network of figure 2(a) has no internal blocking.
Figure 2
1.2.b Now, consider the network of figure 2(b), which is inspired by that of figure 2(a), but whose links all 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 one, because this network has NO internal blocking, if I am not mistaken.
Next, however, show that connections in this network of figure 2(b) may need rerouting in order for the non-blocking property to be satisfied. Imagine, for simplicity, that this is a 4x4 telephony network, i.e. the connections (traffic patterns) that we will consider have a rate of 1.0 each, connecting one input port to one output port (connections among identically numbered ports are allowed). Start setting up connections, one by one, using one of the two possible routings for each new connection (in some cases, the connections that have already been established will only allow one routing choice for the new connection). Give a sequence of such connection set-up's and routing choices such that when a request for a new connection arrives (between two non-busy ports), this new connection can only be satisfied if some previously established connection(s) is(are) rerouted (i.e. previous routing decision(s) is(are) revised). We call non-blocking networks that have this limitation: re-arrangeably non-blocking networks .