一种面向MSM型Clos交换结构的启发式并发调度算法
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家高技术研究发展计划(863)(2013AA013302);国家重点基础研究发展计划(973)(2013CB329105);国家自然科学基金(61233007)


Heuristic Concurrent Dispatching Algorithm for MSM Clos-Network Switches
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    调度算法一直是交换系统中不可或缺的研究内容.为满足新型高速路由及交换系统的研究需求,提出一种主动授权并发轮询调度算法——CRRD-AG算法.多级交换结构Clos交换网络以其良好的可扩展性作为高速交换结构倍受关注,但与之相适应的调度算法却并不多.目前主流算法,如并发分派算法(CD)和基于轮询的并发分派算法(CRRD),不是吞吐率较低就是所处理的业务流单一.CRRD-AG算法以CRRD为基础,将经典的"请求-授权-接受"的匹配计算模式改进为"主动授权-接受"的匹配模式,不仅能够降低CRRD算法在第1阶段的仲裁信息量,而且充分利用了中间级链路带宽,从而降低了整个系统的平均延迟,提高了吞吐率.进行充分的实验后,其结果表明,无论是在均匀业务,还是在突发业务环境中,CRRD-AG算法都能保证100%的吞吐率,更为重要的是,在不降低吞吐率的情况下能够显著改善分组的平均延迟.

    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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2014-02-08
  • 最后修改日期:2014-05-09
  • 录用日期:
  • 在线发布日期: 2015-10-10
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号