Achieving fair service with a hybrid scheduling scheme for CICQ switches  

作　　者：HU HongChao GUO YunFei YI Peng LAN JuLong 

机构地区：[1]Department of Broadband Information Networks,National Digital Switching System Engineering&Technological R&D Center(NDSC),Zhengzhou 450002,China

出　　处：《Science China(Information Sciences)》2012年第3期689-700,共12页中国科学（信息科学）（英文版）

基　　金：supported by National High-Tech Research & Development Program of China (Grant Nos. 2007-AA-01Z218, 2008AA01A323, 2008AA01Z214);National Basic Research Program of China (Grant No. 2007CB307-102);National Natural Science Foundation of China (Grant No. 60803153)

摘　　要：Providing performance guarantees for arriving traffic flows has become an important measure for today＇s routing and switching systems. However, none of current scheduling algorithms built on CICQ （combined input and cross-point buffered） switches can provide flow level performance guarantees. Aiming at meeting this requirement, the feasibility of implementing flow level scheduling is discussed thoroughly. Then, based on the discussion, it comes up with a hybrid and stratified fair scheduling （HSFS） scheme, which is hierarchical and hybrid, for CICQ switches. With HSFS, each input port and output port can schedule variable length packets independently with a complexity of O（1）. Theoretical analysis show that HSFS can provide delay bound, service rate and fair performance guarantees without speedup. Finally, we implement HSFS in SPES （switch performance evaluation system） to verify the analytical results.Providing performance guarantees for arriving traffic flows has become an important measure for today＇s routing and switching systems. However, none of current scheduling algorithms built on CICQ （combined input and cross-point buffered） switches can provide flow level performance guarantees. Aiming at meeting this requirement, the feasibility of implementing flow level scheduling is discussed thoroughly. Then, based on the discussion, it comes up with a hybrid and stratified fair scheduling （HSFS） scheme, which is hierarchical and hybrid, for CICQ switches. With HSFS, each input port and output port can schedule variable length packets independently with a complexity of O（1）. Theoretical analysis show that HSFS can provide delay bound, service rate and fair performance guarantees without speedup. Finally, we implement HSFS in SPES （switch performance evaluation system） to verify the analytical results.

关 键 词：switching fabric scheduling policy load balancing dynamical re-routing 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TV697.11[自动化与计算机技术—计算机科学与技术]