Matching From the First Iteration: An Iterative Switching Algorithm for an Input Queued Switch

摘要

An iterative switching algorithm for an input queued switch consists of a number of iterations in every time step, where each iteration computes a disjoint matching. If input $i$ is matched to output $j$ in a given iteration, a packet (if any) is forwarded from $i$ to $j$ in the corresponding time step. Most of the iterative switching algorithms use a Request Grant Accept (RGA) arbitration type (e.g. iSLIP). Unfortunately, due to this particular type of arbitration, the matching computed in one iteration is not necessarily maximal (more input and output ports can still be matched). This is exactly why multiple iterations are needed. However, multiple iterations make the time step larger and reduce the speed of the switch.