An iterative switching algorithm with (possibly) one iteration

We present a new iterative switching algorithm called π-RGA for an input queued switch. In an iterative switching algorithm, each iteration matches some input and an output port for packet transmission, i.e. each iteration computes a matching, therefore, if input i is matched to output j, a packet (if any) is forwarded from i to j. The matching computed in one iteration is not necessarily maximal (more input and output ports can still be matched), and hence, the size of the matching may grow with more iterations. Therefore, multiple iterations are generally performed in each matching phase of the switch to achieve a high throughput. The reason why an iteration computes a non-maximal matching is efficiency: the matching is computed in a distributed manner without a global state of the switch. This is done using a Request Grant Accept handshake in each iteration, and we restrict our attention in This work to this family of algorithms. PIM based on T. E. Anderson et al. (1993), iSLIP based on N. McKeown (1999), iLQF and iOCF based on N. McKeown (1995), DRR based on Y. Li et al. (2000), and pDRR as stated in Fast scheduler solutions to the problems of priorities for polarized data traffic by G. Damm et al. are examples of such iterative switching algorithms found in the literature. The work on n-RGA is motivated by the assumption that the number of iterations is (possibly) limited to only one iteration, and that high throughput is to be maintained for an arbitrary traffic pattern, even with that one and only iteration. The limit to one iteration emanates from the need to make a matching phase as short as possible for the switch to scale at very high speeds. The key concept behind n-RGA is the stabilization of the matching by keeping parts of the previously computed matching. This stabilization makes it possible to maintain an eventually good size matching with one iteration only. Unlike other approaches, however, n-RGA does not maintain information about the quality of the matching. TT-RGA provides high throughput in practice under uniform and non-uniform traffic patterns with one iteration. We also prove that n-RGA provides throughput and delay guarantees with a speedup of 2 and one iteration under a constant burst traffic model.