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 the traffic scheduling across these switches. Existing algorithms proposed for this architecture can be classified as either batch-scheduling or single-scheduling. This paper is the first which 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 in this paper. We will demonstrate that these results are helpful in determining the right type of algorithm and choosing the appropriate algorithm parameters for a given switch system