一种具有O信息复杂度的高速crossbar调度算法

本文提出一种可扩展性强的高速crossbar调度算法——iRGRR(iterative request-grant-based round-robin),它通过简化处理流程和减小调度开销,克服了传统算法(例如iSLIP^1]、PIM^2])可扩展性差的缺陷.iRGRR将控制信息复杂度从O(N)级大大减小到O(logN)级,具有良好的可扩展性,可应用于太比特交换机/路由器中.仿真结果表明,在各种不同的均匀和非均匀业务流下,iRGRR能够获得与iSLIP几乎相同的性能.另外,iRGRR比iSLIP具有更好的公平性以及更加易于用硬件实现.

A New Scheduling Algorithm with O(logN) Control Messages Complexity for High-Speed Crossbars

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.