00000cab a22000003a 4500 UP-99796217609350617 Buklod 20231007234445.0 m |o d | ta 100621s xx d | ||r ||||| || DENGII eng Shang-Tse Chuang Matching output queueing with a combined input output-queued switch. pp. 1030-1039 The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: switches and routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using weighted-fair queueing (WFQ)-based packet scheduling. Until now, however, the two solutions have been mutually exclusive-all of the work on WFQ-based scheduling algorithms has required that switches/routers use output-queueing or centralized shared memory. This paper demonstrates that a combined input/output-queueing (CIOQ) switch running twice as fast as an input-queued switch can provide precise emulation of a broad class of packet-scheduling algorithms, including WFQ and strict priorities. More precisely, we show that for an N×N switch, a ?speedup? of 2-1/N is necessary, and a speedup of two is sufficient for this exact emulation. Perhaps most interestingly, this result holds for all traffic arrival patterns. On its own, the result is primarily a theoretical observation; it shows that it is possible to emulate purely OQ switches with CIOQ switches running at approximately twice the line rate. To make the result more practical, we introduce several scheduling algorithms that with a speedup of two can emulate an OQ switch. We focus our attention on the simplest of these algorithms, critical cells first (CCF), and consider its running time and implementation complexity. We conclude that additional techniques are required to make the scheduling algorithms implementable at a high speed and propose two specific strategies CIOQ switches. Internet. OQ switches. QoS. WFQ-based packet scheduling. WFQ-based scheduling algorithms. Centralized shared memory. Combined input/output-queued switch. Combined input/output-queueing switch. Critical cells first. Emulation. Guaranteed qualities-of-service. High speed scheduling algorithms. Implementation complexity. Input-queued crossbars. Line rate. Output queueing. Packet switching. Running time. Speedup. Strict priorities. Switching/routing infrastructure. Traffic arrival patterns. Weighted-fair queueing. IEEE Journal on selected areas in communications 17, 6 (1999). FO UPD DENG-II Article