## ''Input-Queued Switches with Logarithmic Delay: Necessary Conditions and a Reconﬁgurable Scheduling Algorithm''

### Krishnendu Roy

### Ramachandran Vaidyanathan

### Jerry L. Trahan

*Proc. 4th ACM/IEEE Symposium on Architectures for Networking and
Communications Systems* (ANCS 2008), pp. 121-122.

#### 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 suﬃcient to transmit a packet. If a
scheduling round requires t_r > t_p time, then the switch can
transmit multiple packets, up to s =
floor(t_r / t_p), between each
mapped input-output pair under the current mapping. If
s = 1, there exists a frame-based scheduling algorithm with
Theta(log n) delay. For uniform random traﬃc, 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.
Given the importance of achieving a low s, it is imperative
to develop extremely fast scheduling algorithms (that reduce
t_r) on a mesh-based structure (corresponding to the cross-
bar topology of the switch). We present results for a fast
scheduling algorithm that runs on a mesh-of-trees topology
that can be overlaid on the crossbar switching fabric.

This work was supported in part by
the National Science Foundation under grant numbers CCR-0310916 and CCR-0073429.