Design and analysis of scheduling algorithms for switches with reconfiguration overhead

Hybrid architectures with electronic buffering/processing and optical switching fabric are receiving a lot of attention as potential candidates for the design of scalable high-performance switches/routers. However, the reconfiguration overhead of optical fabrics introduces new challenges for traffic scheduling across these switches. Existing algorithms proposed for this architecture can be classified as either batch-scheduling or single-scheduling. The paper analyzes and compares the performance of these two scheduling classes. The comparison is based on speedup requirement, average and worst-case delay and algorithm efficiency. Moreover, analytical models for the stability and average delay of single-scheduling algorithms are introduced. We demonstrate that these results are helpful in determining the right type of algorithm and choosing the appropriate algorithm parameters for a given switch system.