 Parallel maximal matching algorithms (adapted for switching) appear to have stricken the best such tradeoff. On one hand, they provide the following Quality of Service (QoS) guarantees: Using maximal matchings as crossbar schedules results in at least 50\% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes. On the other hand, using N processors (one per port), their per-port computational complexity can be as low as O( \log ^2N) (more precisely O(\log N) iterations that each has O(\log N) computational complexity) for an N\times N switch . In this work, we propose QPS-r, a parallel iterative switching algorithm that has the lowest possible computational complexity: O(1) per port. Yet, the matchings that QPS-r computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable throughput and delay guarantees as using maximal matchings, as we show using Lyapunov stability analysis . Although QPS-r builds upon an existing add-on technique called Queue-Proportional Sampling (QPS), we are the first to discover and prove this nice property of such matchings. We also demonstrate that QPS-3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running \log _2 N iterations), a refined and optimized representative maximal matching algorithm adapted for switching.
In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed in each switching cycle, or time slot. Designing switching algorithms with very low computational complexity, that lead to high throughput and small delay is a challenging problem. There appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the resultants throughput and delay. Parallel maximal matching algorithms (adapted for switching) appear to have stricken a sweet spot in this tradeoff, and prior work has shown the following performance guarantees. Using maximal matchings in every time slot results in at least 50\% switch throughput and order-optimal (i.e., independent of the switch size N) average delay bounds for various traffic arrival processes. On the other hand, their computational complexity can be as low as O( log ^2N) per port/processor, which is much lower than those of the algorithms such as maximum weighted matching which ensures better throughput performance . In this work, we propose QPS-r, a parallel iterative switching algorithm that has the lowest possible computational complexity: O(1) per port. Using Lyapunov stability analysis, we show that the throughput and delay performance is identical to that of maximal matching algorithm . Although QPS-r builds upon an existing technique called Queue-Proportional Sampling (QPS), in this paper, we provide analytical guarantees on its throughput and delay under i.i.d. traffic as well as a Markovian traffic model which can model many realistic traffic patterns. We also demonstrate that QPS-3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running log _2 N iterations), a refined and optimized representative maximal matching algorithm adapted for switching.
A
In an input-queued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed in each switching cycle, or time slot. Designing switching algorithms with very low computational complexity, that lead to high throughput and small delay is a challenging problem. There appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the resultants throughput and delay.
R
the best such tradeoff. On one hand, they provide the following Quality of Service (QoS) guarantees:
a sweet spot in this tradeoff, and prior work has shown the following performance guarantees.
R
as crossbar schedules
in every time slot
R
using N processors (one per port), their per-port
their
R
\log
log
R
(more precisely O(\log N) iterations that each has O(\log N) computational complexity) for an N\times N switch
per port/processor, which is much lower than those of the algorithms such as maximum weighted matching which ensures better throughput performance
R
Yet, the matchings that QPS-r computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable
Using Lyapunov stability analysis, we show that the
R
guarantees as using maximal matchings, as we show using Lyapunov stability analysis
performance is identical to that of maximal matching algorithm
D
add-on
R
we are the first to discover and prove this nice property of such matchings.
in this paper, we provide analytical guarantees on its throughput and delay under i.i.d. traffic as well as a Markovian traffic model which can model many realistic traffic patterns.
R
\log
log