Exercise Set 8:
Input Queueing and Crossbar Scheduling

8.1 Saturation Throughput in a 3x3 Input Queued Switch

Using the same technique, calculate the saturation throughput of a 3x3 input queued switch. The head-of-line cells of the three input queues may form 27 combinations. List these combinations; compute the probability of each; compute the average per-output throughput of the switch in each of these cases (and briefly explain); and, finally, compute the average saturation throughput.

8.2 Hand-Simulation of a CIOQ Switch with a Speedup of 2

The simulation will proceed in steps of one "time-slot" each. One time-slot is the time it takes for one cell to arrive through an input port or one cell to depart through an output port. Since the crossbar uses a speedup of 2, the crossbar operates twice per time-slot: in the first phase of each time-slot it can transfer up to one cell from each input buffer and up to one cell to each output queue, and in the second phase it can again transfer up to one cell from each input buffer (same or different queue in the buffer) and up to one cell to each output queue; each time-slot contains both of these phases.

Use the "form" below to simulate the operation of the switch. In this form, what follows the number (8) represents the events, the state, and the operation during the 8th time-slot, and what follows the number (9) represents the 9th time-slot (the queue state just before the 8th time-slot was created artificially, and may not result from any real sequence of switch inputs and operation steps).

        (8)
          inputs: a8y; b8y; c8z;
          inQs a: -; a4y,a8y; a5z,a6z,a7z;
          inQs b: -; b5y,b8y; b6z,b7z;
          inQs c: c7x; c6y; c8z;

          xbar 1: c7x; a4y; b6z;
          xbar 2: -; c6y; b7z;

          outQ's: b4x,c7x; a4y,c6y; c5z,b6z,b7z;
          outputs: b4x; a4y; c5z;
        (9)
          inputs: a9z; b9y; c9z;
          inQs a: -; a8y; a5z,a6z,a7z,a9z;
          inQs b: -; b5y,b8y,b9y; -;
          inQs c: -; -; c8z,c9z;

          xbar 1: -; b5y; c8z;
          xbar 2: -; a8y; c9z;

          outQ's: c7x; c6y,b5y,a8y; b6z,b7z,c8z,c9z;
          outputs: c7x; c6y; b6z;

After listing the arriving cells, we list the contents of the 9 input queues. Line "inQs a" lists the contents of the 3 VOQ's contained in input buffer a; line "inQs b" contains the queues of input buffer b, and similarly for "inQs c". Each line contains first the queue of cells destined to x, then the queue for y, and lastly the queue for z. The head of each queue is on the left, and the tail is on the right. The cells that just arrived from the inputs, at the beginning of the current time-slot, are assumed to have already been enqueued into the proper queue, and are listed here.

Next, we list the crossbar activity during the two phases of the current time-slot: the line "xbar 1" lists the phase-1 transfers, and the line "xbar 2" is for phase-2. In each phase, we list the cell that is transferred to output-queue x, if any, followed by the cell transferred to y, if any, followed by the cell going to z, if any. Obviously, each of these cells must come from the head of a VOQ; the cells transferred during phase-1 are assumed to have been dequeued right away, so phase-2 sees the updated heads of the VOQ's.

Below the crossbar activity, we list the contents of the 3 output queues; again, the head is on the left and the tail is on the right. The cells just delivered by the crossbar, during both phases of the current time-slot, are assumed to have already been enqueued into these queues. After that, we list the departing cells, which obviously are the heads of each output queue (when non-empty). Note that this simulation style is able to transfer an arriving cell to its output queue and from there to the departure port, all within a single time-slot, if the proper queues were in a favorable state and the crossbar made favorable decisions. In a real switch, these steps normally take many clock cycles, corresponding to multiple time-slots, but these activities are pipelined, so that the net link throughput is 1 cell per time-slot, and the net crossbar throughput (in the case of speedup of 2) is 2 cells per time-slot per port.

(a) Simulate, by hand, the above switch, using the above "form", for the following input traffic. Assume that all queues were empty before time-slot 1, and all inputs remain idle after time-slot 6. continue your simulation until all queues drain out.

        (1) inputs: a1x; b1x; c1x;
        (2) inputs: a2x; b2x; c2x;
        (3) inputs: a3x; b3x; c3x;
        (4) inputs: a4x; b4x; c4x;
        (5) inputs: a5y; b5z; c5y;
	(6) inputs: a6z; b6z; c6z;
	(7) inputs: -; -; -;

(b) Repeat your simulation, under the same input traffic pattern above, but using different crossbar scheduling decisions. Do continue using maximal (not necessarily maximum) matchings. However, change in an arbitrary and "bad" manner the matchings that the crossbar scheduler "happens" to make, so that some queues "happen" to be served more frequently than others, in such a way that the switch ends up not being work-conserving anymore (I believe that this can be made to "happen", at least for cell b5z, for one time-slot; I am not sure if it can happen any more than that --may be you want to play with other input patterns or with larger switches, and see if you can make it happen for longer delays or in a sustained manner that affects throughput as well, not just delay... -:)).