一种基于最长队列预测的CICQ交换结构调度算法  

A Novel Scheduling Algorithm Based on Longest Queue Detecting for CICQ Switching Fabrics

作　　者：彭来献[1] 恽姿[1] 赵文栋[1] 田畅[1] 

机构地区：[1]解放军理工大学通信工程学院,南京210007

出　　处：《电子与信息学报》2010年第6期1457-1462,共6页Journal of Electronics & Information Technology

基　　金：江苏省自然科学基金(BK2007001)资助课题

摘　　要：CICQ(Combined Input Crosspoint Queued)是一种在crossbar交叉点加入少量缓存的交换结构,具有无需内部加速比及分布并行调度的特性。为了自适应网络环境中各种业务流量,提高在非均匀流量下的性能,该文提出了一种基于最长队列预测的高效CICQ交换结构调度算法——RR-LQD(Round Robin with Longest Queue Detecting)。RR-LQD算法复杂度为O(1),具有良好的可扩展性;通过预测局部"最长"队列并尽力为其服务,保持调度中队列长度的均衡,能够适应各种非均匀流量的网络环境。仿真结果表明:在各种均匀和非均匀流量下,RR-LQD算法均能达到100%的吞吐量,并且具有优良的时延性能。该文使用FPGA芯片实现了RR-LQD算法仲裁器,能够满足高速、大容量交换结构的设计需要。CICQ（Combined Input Crosspoint Queued） is a switch fabric with buffers in crosspoints,which brings its nice distributed parallel scheduling property with no internal speedup required.In order to adapt to various traffics in the network environment,and improve performance under nonuniform traffics,a novel efficient scheduling algorithm with longest queue detecting——RR-LQD（Round Robin based on Longest Queue Detecting） is proposed.RR-LQD provides fine scalability with the complexity of O（1）.The local longest queue being detected and serviced all along guarantees length balance among input queues,which makes RR-LQD adapt to the network environment of nonuniform traffic automatically.The simulation results show that the RR-LQD can achieve 100% throughput and low delay under various uniform and non-uniform traffics.In this paper,the arbiter of RR-LQD is implemented by a FPGA chip.That proves RR-LQD can meet the demands of high-speed and large capacity switching fabrics.

关 键 词：调度算法 CICQ 非均匀流量 最长队列预测 

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