EEE/ACM TRANSACTIONS ON NETWORKING. VOL 7. NO. 2. APRIL 1999 heavy load lies once again in the degree of synchronization of the arbiters. Under low load. arriving cells find the arbiters in Burstein random positions and isLIP performs in a similar manner to Bu-32 the single iteration version of PIM. The probability that the cell scheduled to be transmitted immediately is proportional to he probability that no other cell is waiting to be routed to the same output. Ignoring the(small) queueing delay under low offered load, the number of contending cells for each output is approximately X(1-(N-1/N)A-), which converges with increasing N to A(1-(1/e). Hence, for constant small A the queueing delay converges to a constant as N increases Under heavy load, the algorithm serves each FIFO once every N cycles, and the queues will behave similarly to an M/D/1 queue with arrival rates A/N and deterministic service time N cell times. For an M/G/1 queue with random service times S, arrival rate A, and service rate u, the queueing delay is given by 入E(S2) (1) for the isLiP switch under a heavy load of bernoulli arrivals, the delay will be approximately Fig. 12. Average burst length at switch output as a function of offered load. odulated by a two-state DTMC. Results are for a 16x 16 switch using the isliP scheduling algorithm which is proportional to M bursts are interleaved at the output. In fact, if the offered load D Burstiness reduction exceeds approximately 70%, the average burst length drops to Intuitively, if a switch decreases the average burst length exactly one cell. This indicates that the output arbiters have become desynchronized and are operating as time-division of traffic that it forwards, then we can expect it to improve multiplexers, serving each input in turn the performance of its downstream neighbor. We can expect any scheduling policy that uses round-robin arbiters to be burst-reducing this is also the case for isLIP isLIP is a deterministic algorithm serving each connection V. ANALYSIS OF ESLIP PERFORMANCE in strict rotation. We therefore expect that bursts of cells at In general, it is difficult to accurately analyze the per different inputs contend ing for the ame output will become formance of a isLIP switch, even for the simplest traffic interleaved and the burstiness will be reduced. This is indeed models. Under uniform load and either very low or very high the case, as is shown in Fig. 12. The graph shows the average offered load, we can readily approximate and understand the burst length at the switch output as a function of offered way in which iSLIP operates. When arrivals are infrequent, bad. Arrivals are on-off processes modulated by a two-state we can assume that the arbiters act independently and that Markov chain with average burst lengths of 16. 32. and 64 arriving cells are successfully scheduled with very low delay At the other extreme, when the switch becomes uniformly Our results indicate that iSLIP reduces the average burst backlogged, we can see that desynchronization will lead the length, and will tend to be more burst-reducing as the offered arbiters to find an efficient time division multiplexing scheme load increases. This is because the probability of switching and operate without contention. But when the trafic is nonuni between multiple connections increases as the utilization in- form, or when the offered load is at neither extreme, the creases. When the offered load is low, arriving bursts do not interaction between the arbiters becomes difficult to describe encounter output contention and the burst of cells is passed The problem lies in the evolution and interdependence of the unmodified. As the load increases. the contention increases and state of each arbiter and their dependence on arriving traffic 7 Note that the convergence is quite fast, and holds approximately even for mall N. For example, 1-I(N-1)/N]N-I equals 0.6073 when 8, A. Comergence to Time-Division Multiplexing and 0.6202 when N=16 and 0. 63 when N is infinite Under Heavy load definitions of burstiness, for example the coefficient of variation [36], burstiness curves andwidth (21. In this section, ne sameourst length [10], or effective Under heavy load, isLIP will behave similarly to an M/D/1 burst length. We define a burst of queue with arrival rates A/N and deterministic service time cells at the output of a switch as the number of consecutive cells that entered cell times. So, under a heavy load of Bernoulli arrivals,the the switch at the same input delay will be approximated by(2)194 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 7, NO. 2, APRIL 1999 heavy load lies once again in the degree of synchronization of the arbiters. Under low load, arriving cells find the arbiters in random positions and performs in a similar manner to the single iteration version of PIM. The probability that the cell is scheduled to be transmitted immediately is proportional to the probability that no other cell is waiting to be routed to the same output. Ignoring the (small) queueing delay under low offered load, the number of contending cells for each output is approximately which converges with increasing to 7 Hence, for constant small the queueing delay converges to a constant as increases. Under heavy load, the algorithm serves each FIFO once every cycles, and the queues will behave similarly to an M/D/1 queue with arrival rates and deterministic service time cell times. For an M/G/1 queue with random service times arrival rate and service rate the queueing delay is given by (1) So, for the switch under a heavy load of Bernoulli arrivals, the delay will be approximately (2) which is proportional to D. Burstiness Reduction Intuitively, if a switch decreases the average burst length of traffic that it forwards, then we can expect it to improve the performance of its downstream neighbor. We can expect any scheduling policy that uses round-robin arbiters to be burst-reducing8 this is also the case for is a deterministic algorithm serving each connection in strict rotation. We therefore expect that bursts of cells at different inputs contending for the same output will become interleaved and the burstiness will be reduced. This is indeed the case, as is shown in Fig. 12. The graph shows the average burst length at the switch output as a function of offered load. Arrivals are on–off processes modulated by a two-state Markov chain with average burst lengths of 16, 32, and 64 cells. Our results indicate that reduces the average burst length, and will tend to be more burst-reducing as the offered load increases. This is because the probability of switching between multiple connections increases as the utilization in￾creases. When the offered load is low, arriving bursts do not encounter output contention and the burst of cells is passed unmodified. As the load increases, the contention increases and 7Note that the convergence is quite fast, and holds approximately even for small N: For example, 1 ￾ [(N ￾ 1)=N] N￾1 equals 0.6073 when N = 8, and 0.6202 when N = 16 and 0:63 when N is infinite. 8There are many definitions of burstiness, for example the coefficient of variation [36], burstiness curves [20], maximum burst length [10], or effective bandwidth [21]. In this section, we use the same measure of burstiness that we use when generating traffic: the average burst length. We define a burst of cells at the output of a switch as the number of consecutive cells that entered the switch at the same input. Fig. 12. Average burst length at switch output as a function of offered load. The arrivals are on–off processes modulated by a two-state DTMC. Results are for a 16 16 switch using the iSLIP scheduling algorithm. bursts are interleaved at the output. In fact, if the offered load exceeds approximately 70%, the average burst length drops to exactly one cell. This indicates that the output arbiters have become desynchronized and are operating as time-division multiplexers, serving each input in turn. V. ANALYSIS OF SLIP PERFORMANCE In general, it is difficult to accurately analyze the per￾formance of a switch, even for the simplest traffic models. Under uniform load and either very low or very high offered load, we can readily approximate and understand the way in which operates. When arrivals are infrequent, we can assume that the arbiters act independently and that arriving cells are successfully scheduled with very low delay. At the other extreme, when the switch becomes uniformly backlogged, we can see that desynchronization will lead the arbiters to find an efficient time division multiplexing scheme and operate without contention. But when the traffic is nonuni￾form, or when the offered load is at neither extreme, the interaction between the arbiters becomes difficult to describe. The problem lies in the evolution and interdependence of the state of each arbiter and their dependence on arriving traffic. A. Convergence to Time-Division Multiplexing Under Heavy Load Under heavy load, will behave similarly to an M/D/1 queue with arrival rates and deterministic service time cell times. So, under a heavy load of Bernoulli arrivals, the delay will be approximated by (2).