![Sample our Mathematics & Statistics journals, sign in here to start your FREE access for 14 days]({"type":"image" , "src" : "/sda/5943/TOC-Subject-Sample-2021-Mathematics-Statistics.jpg"})
Abstract
Combined input-crosspoint-queued (CICQ) switch structure decouples the inputs and outputs matching and enables totally distributed arbitration. CICQ switch cannot achieve 100% throughput under non-uniform traffic if Round-Robin (RR-RR) algorithm is used. The other existing schemes require quite a bit of hardware and time complexity. In this paper, we theoretically prove that the RR-RR can achieve 100% throughput under uniform traffic, but it would be instable under non-uniform traffic. Our quantitative analysis also points out that the throughput will be < 91.7% under the weak diagonal traffic model with f = 0.5 and k = 2, where f is the packet arrival rate along the main diagonal of the traffic matrix and k is the number of buffers used in each crosspoint. Moreover, our formula shows that the k must be at least 4 and 24, respectively, if we wish to improve the throughput to 95 and 99%. Based on our theoretical study, we propose the Differential Round-Robin (DRR) algorithm. Simulations have demonstrated that DRR can achieve 100% throughput under arbitrary traffic using only one buffer cell in each crosspoint. DRR algorithm keeps the high simplicity and efficiency of RR-RR with O(1) complexity while overcoming the instability problem of RR-RR.
Acknowledgements
This work is supported by National Natural Science Foundation of China under Grants No. 90204009 and 90412014 and China Specialized Research Fund for the Doctoral Program of Higher Education under Grants No. 20030286014.
Notes
†Email: [email protected]
‡Email: [email protected]