###
Journal of Software:2015.26(10):2644-2655

一种面向MSM型Clos交换结构的启发式并发调度算法
刘晓锋,赵有健,陈果
(电子科技大学 计算机科学与工程学院, 四川 成都 611731;清华大学 计算机科学与技术系, 北京 100084)
Heuristic Concurrent Dispatching Algorithm for MSM Clos-Network Switches
LIU Xiao-Feng,ZHAO You-Jian,CHEN Guo
(School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China;Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 1403   Download 1762
Received:February 08, 2014    Revised:May 09, 2014
> 中文摘要: 调度算法一直是交换系统中不可或缺的研究内容.为满足新型高速路由及交换系统的研究需求,提出一种主动授权并发轮询调度算法——CRRD-AG算法.多级交换结构Clos交换网络以其良好的可扩展性作为高速交换结构倍受关注,但与之相适应的调度算法却并不多.目前主流算法,如并发分派算法(CD)和基于轮询的并发分派算法(CRRD),不是吞吐率较低就是所处理的业务流单一.CRRD-AG算法以CRRD为基础,将经典的"请求-授权-接受"的匹配计算模式改进为"主动授权-接受"的匹配模式,不仅能够降低CRRD算法在第1阶段的仲裁信息量,而且充分利用了中间级链路带宽,从而降低了整个系统的平均延迟,提高了吞吐率.进行充分的实验后,其结果表明,无论是在均匀业务,还是在突发业务环境中,CRRD-AG算法都能保证100%的吞吐率,更为重要的是,在不降低吞吐率的情况下能够显著改善分组的平均延迟.
中文关键词: Clos网络  调度算法  交换结构  轮询迭代
Abstract:A dispatching algorithm is always indispensable research topic for a switching system. In studying the future-generation high-speed switching and routing system, a concurrent round-robin dispatching algorithm with active grants, called CRRD-AG, is proposed in this paper. As a multistage switching architecture, Clos-network has been receiving increasing attention due to its scalability and modularity, and yet it is not much that the corresponding dispatching algorithm can be applied to the multistage switching fabric. So far, some well-known dispatching algorithms, such as concurrent dispatching (CD) and concurrent round-robin dispatching (CRRD), either have low throughput or can not handle various traffic. CRRD-AG algorithm based on CRRD improves the typical request- grant-accept (R-G-A) matching model used by CRRD to the active grant-accept (AG-A) matching model. Consequently, not only the iterative messages of the request phase can be reduced significantly, but also the bandwidth of the central stage can be utilized sufficiently. Therefore, the average delay is decreased and the throughput is increased. Also, simulations show that CRRD-AG achieves 100% throughput under uniform traffic and bursty traffic. More importantly, the average delay performance of the whole switching system is improved significantly without reducing the throughput of the switching system.
文章编号:     中图分类号:    文献标志码:
基金项目:国家高技术研究发展计划(863)(2013AA013302);国家重点基础研究发展计划(973)(2013CB329105);国家自然科学基金(61233007) 国家高技术研究发展计划(863)(2013AA013302);国家重点基础研究发展计划(973)(2013CB329105);国家自然科学基金(61233007)
Foundation items:
Reference text:

刘晓锋,赵有健,陈果.一种面向MSM型Clos交换结构的启发式并发调度算法.软件学报,2015,26(10):2644-2655

LIU Xiao-Feng,ZHAO You-Jian,CHEN Guo.Heuristic Concurrent Dispatching Algorithm for MSM Clos-Network Switches.Journal of Software,2015,26(10):2644-2655