|CS-534: Packet Switch Architecture
|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 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.
SIM is a slotted-time switch simulator developed in ANSI C by the High-Performance Networking Group at Stanford University. It provides implementations for iSLIP, PIM, and for many other scheduling algorithms, but not for DRRM. So, for PIM and iSLIP you may just run simulations using the ready implementations of SIM, while for DRRM you have to submit your own implementation as well.
We are concerned with (VOQ) crossbars with a single priority level, unicast traffic, and unit-length packets (cells). Traffic may be feasible (Bernoulli iid uniform) or infeasible (some outputs are hot spots). SIM implements Bernoulli iid uniform traffic, but not hot-spot traffic; thus, you also have to submit your own implementation of hot-spot traffic. SIM also implements multiple priority levels and multicast, but you will not be using this functionality in this exercise set.
Generate the load-delay 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 load-delay 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?
How does DRRM compare to iSLIP? Compare DRRM to iSLIP under infeasible traffic. An example is the following. Inputs 1, 2, 3, 4 have a load of 0.25 for output 0; input 0 has a load of 0.25 and L for outputs 0 and 1 respectively. 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 397-436: 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
 N. McKeown: "The iSLIP Scheduling Algorithm for Input-Queued Switches", IEEE/ACM Trans. on Networking, vol. 7, no. 2, April 1999, pp. 188-201.
 J. Chao, "Saturn: A Terabit Packet Switch using Dual Round-Robin", IEEE Commun. Mag., vol. 38, Dec. 2000, pp. 78-84.
 High Performance Networking Group, Stanford University: "SIM : A Fixed Length Packet Simulator", http://klamath.stanford.edu/tools/SIM/
|Up to the Home Page of CS-534
University of Crete, Greece.
Last updated: 13 April 2011, by G. Passas and M. Katevenis.