Dichotomy slot allocation: A low-jitter scheduling scheme for input-queued switches

Recently, jitter is becoming an important performance criterion in switch scheduling to accommodate many emerging real-time applications. Formerly proposed low-jitter scheduling algorithms decompose traffic demands into a weighted sum of permutation matrices and then schedule these decomposed permutation matrices. However, a port pair's appearance in these decomposed matrices may exceed their actual traffic demand. Such extra allocation may result in high jitter for a port pair. In order to smoothly schedule each port pair, we propose a novel scheduling algorithm termed as Dichotomy Slot Allocation (DSA). To achieve low jitter and small cell loss, DSA allocates slots to port pairs based on a designed Dichotomy Order. Both analysis and simulation results demonstrate that DSA achieves relatively lower jitter as compared to the state of the art.