NXG06-4: Improving Scheduling Efficiency for High-Speed Routers with Optical Switch Fabrics

Aiming at providing 100% throughput with bounded packet delay, we consider traffic scheduling in high-speed routers with optical switch fabrics. Because of the switch reconfiguration overhead, a speedup in the switch fabric is essential. For a given packet delay bound, our objective is to minimize the overall speedup S = S_reconfigure times S_schedule so as to lower the implementation cost. Leveraging on the existing ADAPTIVE and DOUBLE algorithms, we show the speedup can be reduced by improving scheduling efficiency. Specifically, following the traffic matrix decomposition in ADAPTIVE and DOUBLE, we shift some packets from the residue matrix R to the quotient matrix Q, while keeping the number of configurations required to cover each matrix the same. We reduce the number of time slots required to send the diminished residue matrix. In case of DOUBLE, this translates into a 12.5% cut in S_schedule (from 2 to 1.75). We call the resulting algorithm Scheduling Residue First (SRF).