Network Computing and Applications, Third IEEE International Symposium on (NCA'04)
An Iterative Switching Algorithm With (Possibly) One Iteration
Boston, Massachusetts
August 30-September 01
ISBN: 0-7695-2242-4
We present a new ieterative switching algorithm called π-RGA for an input queued switch. In an iterative switching algorithm, each iteration matches some input and output ports 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 paper to this family of algorithms. PIM, iSLIP, iLQF and iOCF, DRR, and pDRR are examples of such iterative switching algorithms found in the literature. The work on π-RGA is motivated by the assumption that the number of iterations is (possibly) limited to only one iteration, and that high throuhput is to be maintained for an arbitrary traffic pattern, even with that one and only iteration. The limited 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 π-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, π-RGA does not maintain information about the quality of the matching. π-RGA provides high throughput in practice under uniform and non-uniform traffic patterns with one iteration. We also prove that π-RGA provides throughput and delay guarantees with a speedup of 2 and one iteration under a constant burst traffic model.
Index Terms:
Switching, matching, number of iterations, speedup
Citation:
Saad Mneimneh, "An Iterative Switching Algorithm With (Possibly) One Iteration," nca, pp.223-231, Network Computing and Applications, Third IEEE International Symposium on (NCA'04), 2004