iSLIP Stalls at 80% Throughput; Spectral Scheduling and OT Keep Up With MWM

Under an unbalanced traffic pattern at load 0.9, iSLIP hits a throughput ceiling of 80%, with bottleneck queues growing without bound and delay climbing to two orders of magnitude above exact maximum weight matching (MWM). That is not a corner case: the paper tests four traffic patterns, and under non-uniform admissible traffic at high load, iSLIP simply breaks.

The 80% Ceiling: iSLIP's Failure Mode

The authors built a C++ discrete-event simulator for an N-by-N SoC crossbar, where each clock cycle permits at most one cell transfer per input-output port pair. They used exact MWM solved by the Hungarian algorithm as the performance reference. For iSLIP and spectral scheduling, they fixed the iteration budget at r=3 rounds per cycle. For entropy-regularized optimal transport (OT), they used r_sink=10 Sinkhorn normalization rounds.

Under uniform traffic, iSLIP holds up better: at rho_load=0.99, its delay is 3.7x MWM. That is manageable. But under the unbalanced pattern (w=0.5, rho_load>=0.9), iSLIP's throughput caps at roughly 80%. Inside the switch, bottleneck queues grow without bound, and delay skyrockets. The paper's linear-algebraic framework (queue matrix Q, matching matrix P, Lyapunov energy V=||Q||^2) explains why: iSLIP's Grant-Accept row-column decoupling cannot achieve the same service matrix P-bar under skewed load patterns.

Spectral Scheduling and OT: Close to Ideal, at a Cost

Spectral scheduling and entropy-regularized OT track MWM closely across all tested traffic patterns, both in throughput and delay. For a switch architect, that is remarkable because MWM is known to be throughput-optimal but computationally expensive. These two approximate algorithms essentially deliver MWM-level performance with bounded iteration budgets.

The catch: spectral scheduling and OT require O(r*N^2) multiply-accumulate or exponential operations per cycle. iSLIP, by contrast, uses simple bitwise operations and pointer updates. Whether that compute overhead is feasible in real hardware, given die area, power, and timing closure constraints, is the open question.

What This Means for Real Crossbar Design

If your next switch design targets uniform workloads, iSLIP remains a solid choice. But for non-uniform traffic patterns, the paper makes a strong case that spectral scheduling or OT are worth the hardware cost. I expect chip architects to start evaluating whether an O(r*N^2) MAC array can fit into the crossbar scheduler's timing budget, especially as N grows in modern SoCs. The answer will determine whether iSLIP's 80% ceiling becomes a legacy footnote or a lasting constraint.

Source: From MWM to iSLIP: A Linear-Algebraic Tutorial on Input-Queued Switch Scheduling
Domain: arxiv.org