A Delay Bound and Speedup Guarantees for Scheduling in Input-Queued and Combined-Input-Output-Queued Switches

S.Kh. Al-Harthi (Saudi Arabia)


Packet scheduling, QoS, switching, speedup, CIOQ switches.


In this paper, we consider the fundamental problem of find ing a minimum speedup required for “combined input and output queued” (CIOQ) switches such that the quality of service (QoS) guarantees of these switches are identical or comparable to the QoS guarantees of the counterpart out put queued (OQ) switches. Due to limitations of current technologies of memories, reducing the minimum required speedup of high-end switches became an important issue in the architecture of switches. First, we consider a schedul ing policy using any maximal matching. It is shown that if the traffic input to the switch is (σ, ρ)-regulated, then any maximal matching guarantees that with any speedup factor of s > 4, independent of the switch size, the delay of pack ets through the switch is bounded and the switch achieves a 100% throughput. The delay bound in this paper is a refinement of a previously reported bound. Second, it is shown that if any maximal matching is used in conjunction with a simple frame-based scheduling policy and an appro priate admission conditions, the resulting scheme reduces the speedup factor to s ≥ 2, and guarantees a bound on packets’ delay.

Important Links:

Go Back