A New Scheduling Algorithm with O(logN) Control Messages Complexity for High-Speed Crossbars
Wendong Zhao · Dianzi xuebao · 2006
This paper presents a scalable scheduling scheme,called iterative request-grant-based round-robin(iRGRR),for high-speed crossbars.It overcomes limitation that most traditional scheduling schemes(such as iSLIP,PIM) suffer from poor scalability by simplifying the execution process and reducing the scheduling overhead.iRGRR dramatically reduces the complexity of control messages from an order of O(N) to O(logN),and thus provides fine scalability,and can be used in terabit switches/routers.The simulation results show that iRGRR can achieve nearly the same performance as iSLIP under various traffic models,including uniform and non-uniform destination distributions.In addition,iRGRR provides better fairness and has lower implementation complexity than iSLIP.