A pipelined maximal-sized matching scheme for high-speed input-buffered switches
Eiji Oki, Roberto Rojas‐Cessa, H. Jonathan Chao · IEICE Transactions on Communications · 2002
This paper proposes an innovative Pipelinebased Maximal-sized Matching scheduling approach, called PMM, for input-bu ered switches. It dramatically relaxes the limitation of a single time slot for completing a maximal matching into any number of time slots. In the PMM approach, arbitration is operated in a pipelined manner, where K subschedulers are used. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of the subschedulers provides the matching result. We adopt an extended version of Dual Round-Robin Matching (DRRM), called iterative DRRM (iDRRM), as a maximal matching algorithm in a subscheduler. PMM maximizes the eAEciency of the adopted arbitration scheme by allowing suAEcient time for the number of iterations. We show that PMM preserves 100% throughput under uniform traAEc and fairness for best-e ort traAEc of the nonpipelined adopted algorithm, while ensuring that cells from the same virtual output queue (VOQ) are transmitted in sequence. In addition, we con rm that the delay performance of PMM is not signi cantly degraded by increasing the pipeline degree, or the number of subschedulers, when the number of outstanding requests for each subscheduler from a VOQ is limited to 1. key words: Scheduling, pipeline, input-bu ered switch, maximal-sized matching