MCKEOWN: THE ISLIP SCHEDULING ALGORITHM FOR INPUT-QUEUED SWITCHES Cell 1. Iteration 1: Rh…则G→AA Ouput A Cell 2. iteration 1 R G A er g. 17. Performance of iSLIP for 1, 2, and 4 iterations compared with FI R…→G A d output queueing for i.i.d. Bernoulli arrivals with destinations uniformly switch. The graph shows the average delay per cell, measured in cell times between arriving at the input buffers and departing from the switch. avily loaded N XN switch. All inp duration of the example. In the first cel After N cell times. all arbiters are d 二吧 match is found in a single iteration. where I is the number of iterations that pim takes to converge For all the stationary arrival proc es we have tried E[≤lg2 for iSLIP. However, we have not been able to prove that this relation holds in general B. With Benign Bernoulli Arrivals To illustrate the improvement in performance of iSLIP when the number of iterations is increased, Fig. 17 shows the average queueing delay for one, two, and four iterations nder uniform i.1.d. Bernoulli arrivals. We find that multiple iterations of isLIP significantly increase the size of the match and, therefore, reduce the queueing delay. In fact, isLIPcan achieve 100% throughput for one or more iteration with uni form i i.d. Bernoulli arrivals. Intuitively, the size of the match increases with the number of iterations. each new iteration potentially adds connections not made by earlier iterations This is illustrated in Fig. 18, which compares the size of iSLIP Comparison of the match size for iSLIP with the size of a maximum matching with the size of the maximum matching for the same atch for the same set of requests. Results are for a 16 x 16 switch instantaneous queue occupancies. Under low offered load, the IP arbiters move randomly and the ratio of the match size to the maximum match size decreases with increased offered with the number of iterations indicating that the matching gets load. But when the load exceeds approximately 65%, the ratio closer to the maximum-sized match, but only up to a point begins to increase linearly. As expected, the ratio increases For a switch under this traffic load, increasing the numberMCKEOWN: THE iSLIP SCHEDULING ALGORITHM FOR INPUT-QUEUED SWITCHES 197 Fig. 16. Example of the number of iterations required to converge for a heavily loaded N N switch. All input queues remain nonempty for the duration of the example. In the first cell time, the arbiters are all synchronized. During each cell time, one more arbiter is desynchronized from the others. After N cell times, all arbiters are desynchronized and a maximum sized match is found in a single iteration. where is the number of iterations that PIM takes to converge. For all the stationary arrival processes we have tried for However, we have not been able to prove that this relation holds in general. B. With Benign Bernoulli Arrivals To illustrate the improvement in performance of when the number of iterations is increased, Fig. 17 shows the average queueing delay for one, two, and four iterations under uniform i.i.d. Bernoulli arrivals. We find that multiple iterations of significantly increase the size of the match and, therefore, reduce the queueing delay. In fact, can achieve 100% throughput for one or more iteration with uni￾form i.i.d. Bernoulli arrivals. Intuitively, the size of the match increases with the number of iterations; each new iteration potentially adds connections not made by earlier iterations. This is illustrated in Fig. 18, which compares the size of matching with the size of the maximum matching for the same instantaneous queue occupancies. Under low offered load, the arbiters move randomly and the ratio of the match size to the maximum match size decreases with increased offered load. But when the load exceeds approximately 65%, the ratio begins to increase linearly. As expected, the ratio increases Fig. 17. Performance of iSLIP for 1, 2, and 4 iterations compared with FIFO and output queueing for i.i.d. Bernoulli arrivals with destinations uniformly distributed over all outputs. Results obtained using simulation for a 16 16 switch. The graph shows the average delay per cell, measured in cell times, between arriving at the input buffers and departing from the switch. Fig. 18. Comparison of the match size for iSLIP with the size of a maximum sized match for the same set of requests. Results are for a 16 16 switch and uniform i.i.d. Bernoulli arrivals. with the number of iterations indicating that the matching gets closer to the maximum-sized match, but only up to a point. For a switch under this traffic load, increasing the number