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 is matched to output in a given iteration, a packet (if any) is forwarded from to 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. We present a new iterative switching algorithm (based on the RGA arbitration) called with the underlying assumption that the number of iterations is possibly limited to one, hence reducing the time step and allowing the switch to run at a higher speed. We prove that achieves throughput and delay guarantees with a speedup of 2 and one iteration under a constant burst traffic model, which makes as good as any maximal matching algorithm in the theoretical sense. We also show by simulation that achieves relatively high throughput in practice under uniform and non-uniform traffic patterns with one iteration and no speedup.