CS534: Packet Switch Architecture
Spring 2013 
Department of Computer Science
© copyright: University of Crete, Greece 
[Lectures: 4.2 Input Queueing, 4.4 CIOQ]  [print version, in PDF] 
Using the same technique, calculate the saturation throughput of a 3x3 input queued switch (single queue per input). The headofline cells of the three input queues may form 27 combinations. List these combinations; compute the probability of each; compute the average peroutput throughput of the switch in each of these cases (and briefly explain); and, finally, compute the average saturation throughput.
We are concerned with (VOQ) crossbars with a single priority level, unicast traffic, and unitlength packets (cells). Traffic may be feasible (Bernoulli iid uniform) or infeasible (some outputs are hot spots). SIM implements Bernoulli iid uniform traffic, but not hotspot traffic; thus, you also have to submit your own implementation of hotspot traffic. SIM also implements multiple priority levels and multicast, but you will not be using this functionality in this exercise set.
Generate the loaddelay curve of PIM and iSLIP with one iteration of the matching steps in a 4x4 crossbar with a single priority level and unicast Bernoulli iid uniform traffic. To do so, run a simulation for each load value, measure the average delay of cells in each simulation run, and plot the resulting loaddelay curve. You can run a simulation in this way:
> ./sim f config.txtwhere config.txt is a configuration file. For example, using the following configuration file, you can measure the average cell delay in a 4x4 crossbar scheduled by iSLIP with one iteration of the matching steps, when traffic load is 0.7 (70%). Average cell delay is reported in SIM's output as "Total Latency over all cells".
> cat config.txt Numswitches 1 Switch 0 Numinputs 4 Numoutputs 4 InputAction defaultInputAction OutputAction defaultOutputAction Fabric crossbar Algorithm islip n 1 0 bernoulli_iid_uniform u 0.7 1 bernoulli_iid_uniform u 0.7 2 bernoulli_iid_uniform u 0.7 3 bernoulli_iid_uniform u 0.7 Stats Arrivals Departures Latency Occupancy Histograms Arrivals Departures Latency OccupancyAlso generate PIM and iSLIP curves for 16x16, 64x64, and 256x256 crossbars and repeat for iSLIP and PIM with 2, 4, 6, and 8 iterations of the matching steps.
When running your simulations, consider and answer the following questions: (i) We are interested in average cell delay when the switch is stable. Practically, stability can be decided by checking the delay of cells: If during a simulation run delay keeps increasing linearly with simulated time, the switch is unstable a direct consequence of Little's law. How much time do you need to simulate to decide stability? Is this related to traffic load or switch size? How? How is stability related to the RAM utilization of your computer? In SIM, the simulated time when simulation stops is determined by the constant DEFAULT_SIMULATION_LENGTH in file sim.c. (ii) Which is the running time complexity of your simulations with respect to simulated time, switch size, and number of iterations?
Optionally also implement DRRM [3] on your simulator, and repeat exercise 8.2 for that scheduling algorithm. To implement DRRM you have to add to SIM a modification of iSLIP. iSLIP is implemented in file ALGORITHMS/islip.c. The main loop of the algorithm is in lines 172218. You have to modify mainly this part, reversing the order of arbitration (selection) in DRRM, first arbitrate the inputs and then the outputs. DRRM operates in the following two steps:
How does DRRM compare to iSLIP? Compare DRRM to iSLIP under infeasible traffic. An example is the following. Inputs 1, 2, 3, and 4 send traffic to output 0, at a rate of 0.25 each. Input 0 sends traffic to outputs 0 and 1: it sends to output 0 at a rate of 0.25, and to output 1 at a rate L. This pattern overloads output 0, but not output 1. Plot the delay of cells from input 0 to output 1, as L varies from 0.05 to 0.75. Observe and explain.
To implement the above traffic patttern, add to SIM a modification of file TRAFFIC/bernoulli_iid_uniform.c. The main part for traffic generation is in lines 397436: Variable "psend" determines the probability of generating a cell and variable "output" the destination output of the generated cell. Notice that you have to measure the delay of cells from input 0 to output 1 only (not all cels). So, you have to selectively stamp cells. This can be done by conditioning the update of the total latency variable in file latencyStats.c
[2] N. McKeown: "The iSLIP Scheduling Algorithm for InputQueued Switches", IEEE/ACM Trans. on Networking, vol. 7, no. 2, April 1999, pp. 188201.
[3] J. Chao, "Saturn: A Terabit Packet Switch using Dual RoundRobin", IEEE Commun. Mag., vol. 38, Dec. 2000, pp. 7884.
Up to the Home Page of CS534

© copyright
University of Crete, Greece.
Last updated: 2 May 2013, by G. Passas, A. Psathakis, and M. Katevenis. 