MCKEOWN: THE ISLIP SCHEDULING ALGORITHM FOR INPUT-QUEUED SWITCHES bernoulli_lid_uniform train科 3E∽3 z Offered Load (%) of average latency for the iSLIP algorithm an Offered Load(%)80 M/D/I the iSliP algorithm. ar Fig. 14. Comparison of analytical approximation and simulation results for the average number of sy To see how close isLIP approximates to time-division modulated by a two-state I multiplexing under heavy load, Fig. 13 compares the average cells. The analytical approximation is shown in (3) latency for both iSLIP and an M/D/1 queue (2). Above an offered load of approximately 70%, iSLIP behaves very where similarly to the m/D/I queue, but with a higher latency. This N number of ports is because the service policy is not constant; when a queue A arrival rate averaged over all inputs changes between empty and nonempty, the scheduler must adapt to the new set of queues that require service. Thi daptation takes place over many cell times while the arbiters le have found that this approximation is quite accurate desynchronize again. During this time, the throughput will be over a wide range of uniform workloads. Fig. 14 compares worse than for the MD/I queue and the queue length will the approximation in(3)with simulation results for both i.i.d ncrease. This in turn will lead to an increased latency Bernoulli arrivals and for an on-off arrival process modulated by a two-state Markov-chain B. Desynchronization of Arbiters ye have argued that the performance of isLIP is dictated vl. the iSLIP ALGORITHM WITH MULTIPLE ITERATIONS by the degree of synchronization of the output schedulers. In this section, we present a simple model of synchronization for Until now, we have only considered the operation of SLIP a stationary and sustainable uniform arrival process with a single iteration. We now examine how the algorithm must change when multiple iterations are performed In[24, Appendix 1], we find an approximation for E[S(t)], With more than one iteration, the iterative iSLIP algorithm the expected number of synchronized output schedulers at time t. The approximation is based on two assumptions improves the size of the match; each iteration attempts to add inputs that are unmatched at time t are uniformly dis. connections not made by earlier iterations. Not surprisingly, tributed over all inputs, we find that the performance improves as we increase the number of iterations(up to about log N, for an NXN switch) 2)the number of unmatched inputs at time t has zero Once again, we shall see that desynchronization of the outp ariano arbiters plays an important role in achieving low latency This leads to the approximation When multiple iterations are used, it is necessary to modify ES(切]≈N-N(N-1)4 the isLIP algorithm. The three steps of each iteration operate 22A/AN- in parallel on each output and input and are as follows Step 1: Request. Each unmatched input sends a request (3)every output for which it has a queued cellMCKEOWN: THE iSLIP SCHEDULING ALGORITHM FOR INPUT-QUEUED SWITCHES 195 Fig. 13. Comparison of average latency for the iSLIP algorithm and an M/D/1 queue. The switch is 16 16 and, for the iSLIP algorithm, arrivals are uniform i.i.d. Bernoulli arrivals. To see how close approximates to time-division multiplexing under heavy load, Fig. 13 compares the average latency for both and an M/D/1 queue (2). Above an offered load of approximately 70%, behaves very similarly to the M/D/1 queue, but with a higher latency. This is because the service policy is not constant; when a queue changes between empty and nonempty, the scheduler must adapt to the new set of queues that require service. This adaptation takes place over many cell times while the arbiters desynchronize again. During this time, the throughput will be worse than for the M/D/1 queue and the queue length will increase. This in turn will lead to an increased latency. B. Desynchronization of Arbiters We have argued that the performance of is dictated by the degree of synchronization of the output schedulers. In this section, we present a simple model of synchronization for a stationary and sustainable uniform arrival process. In [24, Appendix 1], we find an approximation for the expected number of synchronized output schedulers at time The approximation is based on two assumptions: 1) inputs that are unmatched at time are uniformly dis￾tributed over all inputs; 2) the number of unmatched inputs at time has zero variance. This leads to the approximation (3) Fig. 14. Comparison of analytical approximation and simulation results for the average number of synchronized output schedulers. Simulation results are for a 16 16 switch with i.i.d. Bernoulli arrivals and an on–off process modulated by a two-state Markov chain with an average burst length of 64 cells. The analytical approximation is shown in (3). where number of ports; arrival rate averaged over all inputs; . We have found that this approximation is quite accurate over a wide range of uniform workloads. Fig. 14 compares the approximation in (3) with simulation results for both i.i.d. Bernoulli arrivals and for an on–off arrival process modulated by a two-state Markov-chain. VI. THE SLIP ALGORITHM WITH MULTIPLE ITERATIONS Until now, we have only considered the operation of with a single iteration. We now examine how the algorithm must change when multiple iterations are performed. With more than one iteration, the iterative algorithm improves the size of the match; each iteration attempts to add connections not made by earlier iterations. Not surprisingly, we find that the performance improves as we increase the number of iterations (up to about for an switch). Once again, we shall see that desynchronization of the output arbiters plays an important role in achieving low latency. When multiple iterations are used, it is necessary to modify the algorithm. The three steps of each iteration operate in parallel on each output and input and are as follows: Step 1: Request. Each unmatched input sends a request to every output for which it has a queued cell.