|CS-534: Packet Switch Architecture
|Department of Computer Science
© copyright: University of Crete, Greece
|[Lecture: 1. Basic Concepts, Q.Arch.]||[printer version - PDF]|
(a1) Network (a) is called a banyan. Is this a single-path or a multi-path network, i.e. are there input-output port pairs (flows) for which multiple paths through the network exist, or is it that a single possible path exists for any packet, given its input and output ports?
(a2) Banyan networks, (a), exhibit internal blocking: Show a feasible (for the overall network, as observed "from the outside") traffic pattern (Chapter 1, slide 7) that cannot be routed by this network, due to internal blocking (Chapter 1, slide 8).
(a3) The fact that internal blocking exists for some traffic patterns does not mean that all ("demanding") traffic patterns will encounter internal blocking. Show a non-trivial traffic pattern for the banyan network (a) that does not encounter internal blocking; to qualify as "non-trivial", make this traffic pattern such that all (external) network ports are fully loaded, i.e. the sum of all flow rates at each port is 1.
(b1) Network (b) consists of two banyans connected back-to-back, with their middle stages merged; this is a Benes network. Is this a single-path or multi-path network? How many different routes are there from a given input port to a given output port, for the different input-output port pairs (flows)?
(b2) Try finding a feasible traffic pattern that cannot be sustained by this network. You will find none, because Benes networks are internally non-blocking. Show some "difficult" traffic patterns (e.g. some for which the banyan (a) exhibited internal blocking) and how the Benes network can route them.
(b3) When all packets of a flow follow a same, single path, show that flows in the Benes network (b) may need rerouting in order for the non-blocking property to be satisfied. Consider, for simplicity, flows of rate 1 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; in some cases, the flows that have already been established will dictate the 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.
|Up to the Home Page of CS-534
University of Crete, Greece.
Last updated: 1 Mar. 2013, by M. Katevenis.