Randomized batch scheduling with minimum configurations for switches and routers

As the technology advances, the speed and sizes of input-queued internet switches increase dramatically. The design of the switch scheduler becomes a primary challenge, because the time interval for making scheduling decisions becomes very small. One method to resolve this problem is to reduce the scheduling frequency for a batch of packets and pipeline the switching tasks. Such method is called batch scheduling. Since computing and setting up each switch configuration incurs a notable cost, it is preferred to have minimum number of configurations for every batch. We study in this paper approximation schemes for batch scheduling with minimum configurations. We propose three algorithms together with their (expected) approximation ratios. The NAIVE ROUND ROBIN algorithm runs in O(N²) time and has the worst possible approximation ratio. We try to improve the approximation ratio by randomization. The RANDOMIZED ROUND ROBIN algorithm has an expected approximation ratio of O(ln N). In the same fashion, we propose the BARELY RANDOM ROUND ROBIN algorithm that uses less random bits at a cost of worse approximation ratio. Finally, our simulation results indicate that a fabric speedup of 2 is sufficient for our batch scheduling algorithms to provide quality of service (QoS).