TY - GEN
T1 - A Low complexity scheduling algorithm for a crosspoint buffered switch with 100% throughput
AU - Shen, Yanming
AU - Panwar, Shivendra S.
AU - Chao, H. Jonathan
PY - 2008
Y1 - 2008
N2 - Crosspoint buffered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms, and achieve better performance than a bufferless crossbar switch. Crosspoint buffered switches have a buffer at each crosspoint. A cell is first delivered to a crosspoint buffer, and then transferred to the output port. With a speedup of two, a crosspoint buffered switch has previously been proved to provide 100% throughput. In this paper, we propose a 100% throughput scheduling algorithm without speedup, called SQUID. With this design, each input/output keeps track of the previously served virtual output queues (VOQs)/crosspoint buffers. We prove that SQUID, with a time complexity of 0(log N), can achieve 100% throughput without any speedup. Our simulation results also show a delay performance comparable to output- queued switches. We also present a novel queuing model that models crosspoint buffered switches under uniform traffic.
AB - Crosspoint buffered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms, and achieve better performance than a bufferless crossbar switch. Crosspoint buffered switches have a buffer at each crosspoint. A cell is first delivered to a crosspoint buffer, and then transferred to the output port. With a speedup of two, a crosspoint buffered switch has previously been proved to provide 100% throughput. In this paper, we propose a 100% throughput scheduling algorithm without speedup, called SQUID. With this design, each input/output keeps track of the previously served virtual output queues (VOQs)/crosspoint buffers. We prove that SQUID, with a time complexity of 0(log N), can achieve 100% throughput without any speedup. Our simulation results also show a delay performance comparable to output- queued switches. We also present a novel queuing model that models crosspoint buffered switches under uniform traffic.
UR - http://www.scopus.com/inward/record.url?scp=60649111724&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=60649111724&partnerID=8YFLogxK
U2 - 10.1109/HSPR.2008.4734442
DO - 10.1109/HSPR.2008.4734442
M3 - Conference contribution
AN - SCOPUS:60649111724
SN - 9781424419821
T3 - 2008 International Conference on High Performance Switching and Routing, HPSR 2008
SP - 189
EP - 196
BT - 2008 International Conference on High Performance Switching and Routing, HPSR 2008
T2 - 2008 International Conference on High Performance Switching and Routing, HPSR 2008
Y2 - 15 May 2008 through 17 May 2008
ER -