Scalable central-stage buffered clos-network packet switches with QoS

In our previous work [1], we proposed a scalable packet switch architecture based on the Central-stage Buffered Clos-network (CBC). We analyzed the memory requirements for the CBC to emulate an output-queued (OQ) switch and left the corresponding scheduling algorithms unexplored. In this paper¹, we set out to find a practical algorithm to schedule packets in order for the CBC to emulate an OQ switch supporting Quality of Service (QoS). We observe that the CBC surprisingly extend the well-known Birkhoff-von Neumann input-queued switches [IS], making it able to scale to large switches with many input/output ports. In particular, as far as we know, the most efficient scheduling algorithm for a Birkhoff-von Neumann switch has a time complexity of O(N^4.5), where N is the number of switch ports. We show in this paper that we can reduce it to O(N^2.25) by employing a multi-stage multi-layer switch implementation.