''Input-Queued Switches with Logarithmic Delay: Necessary Conditions and
a Reconfigurable Scheduling Algorithm''
Krishnendu Roy
Ramachandran Vaidyanathan
Jerry L. Trahan
submitted to
4th ACM/IEEE Symposium on Architectures for Networking and
Communications Systems (ANCS'08)
Abstract:
Typically, a scheduling algorithm for an n x n packet switch
with a crossbar as the data fabric divides time into slots,
each of duration t_p sufficient to transmit a packet. If a
scheduling round requires t_m > t_p time, then rather than
sitting idle waiting for the completion of the next input
output mapping, the switch can transmit multiple packets
for each input-output pair under the current mapping. In
general, during a round, it is possible to transmit up to
s = floor(t_m / t_p)
packets between each mapped input-output pair.
If s = 1, there exists a frame-based scheduling algorithm
with \Theta(log n) delay. For uniform random traffic, we
establish that the delay is \Omega(n) for any s > 1, hence, s = 1 is the
only case where a Theta(log n) delay is achievable. For bursty
traffic with a mean burst size b, we also show that the delay
is \Theta(log n) when s <= b, but quickly becomes \Omega(n) as s starts
to exceed b.
Given the importance of achieving a low s, it is imperative to
develop extremely fast scheduling algorithms (that
reduce t_m) on a mesh-based structure (corresponding to the
crossbar topology of the switch). We present a mesh-of-trees
based algorithm that is guaranteed to find a schedule
in O(log^6 n) time, which is much faster than the O(n log n)
time sequential alternative and comparable to other distributed algorithms.
This work was supported in part by
the National Science Foundation under grant number CCR-0310916.