Minimum Delay Scheduling for Performance Guaranteed Switches With Optical Fabrics
Bin Wu, Kwan Lawrence Yeung, Pin‐Han Ho, Xiaohong Jiang · Journal of Lightwave Technology · 2009
We consider traffic scheduling in performance guaranteed switches with optical fabrics to ensure 100% throughput and bounded packet delay. Each switch reconfiguration consumes a constant period of time calledreconfigurationoverhead, during which no packet can be transmitted across the switch. To minimize the packet delay bound for an arbitrary traffic matrix, the number of switch configurations in the schedule should be no larger than the switch sizeN. This is calledminimumdelayscheduling, where the ideal minimum packet delay bound is determined solely by the total overhead of theNswitch reconfigurations. A speedup in the switch determines the actual packet delay bound, which decreases toward the ideal bound as the speedup increases. Our objective is to minimize the required speedupSscheduleunder a given actual packet delay bound. We propose a novel minimum delay scheduling algorithm quasi largest-entry-first (QLEF) to solve this problem. Compared with the existing minimum delay scheduling algorithms MIN and alphai-SCALE, QLEF dramatically cuts down the requiredSschedulebound. For example, QLEF only requiresSschedule=17.89 forN=450, whereas MIN and alphai-SCALE requireSschedule=37.13 and 27.82, respectively. This gives a significant performance gain of 52% over MIN and 36% over alphai-SCALE.