Clos交换结构中采用贯序匹配的高效调度算法  

Sequential Matching Scheme in Clos Multi-stage Interconnected Switch Fabric

作　　者：汪洋[1] 罗婷[2] 余少华[2] 

机构地区：[1]华中科技大学电子与信息工程系湖北省智能互联网技术重点实验室,湖北武汉430074 [2]武汉邮电科学研究院光纤通信技术和网络国家重点实验室,湖北武汉430074

出　　处：《小型微型计算机系统》2009年第9期1709-1714,共6页Journal of Chinese Computer Systems

基　　金：国家"八六三"高技术研究发展计划项目(2005AA121411)资助

摘　　要：使用Clos结构的多阶段互联是构建大规模分布式交换系统重要的解决方案,而如何在Clos拓扑上进行高效的调度成为业界和学术界一直感兴趣的问题.现有的调度算法CRRD存在两个不足而制约了其调度效率,首先是它采用接力式的匹配算法,导致匹配成功率以串行方式降低,其次是调度按照多对一的方式匹配,容易浪费调度机会.本文提出的贯序匹配算法SM-ACN在这两个方面进行了改进.SMACN采用直通式匹配,整个匹配过程一次完成,同时采取多对多的接受方式,最大程度利用了调度机会.数值模拟显示SMACN在各种流量场景下都比传统的CRRD有较高的吞吐率.Clos type multistage interconnected network （MIN） is the most promising approach to build large-scale switch fabric, and the scheduling problem therein has been widely addressed both in industry and in academics. The current scheduling scheme CRRD suffers from two drawbacks： fast it follows a relayed matching procedure, resulting in tandem degrading of matching rate; second it adopts a many-to-one matching paradigm, causing a waste of scheduling chance. This paper proposes a sequential matching scheme SMACN. The run-through style of SMACN completes the matching in a single round, and the many-to-many acceptance allows a full-most utilization of scheduling chance. The numerical study shows that SMACN outperforms CRRD in various traffic scenarios.

关 键 词：SMACN Clos多阶段互联 CRRD 吞吐率 调度 虚拟输出队列 

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