北京邮电大学学报

  • EI核心期刊

北京邮电大学学报 ›› 2013, Vol. 36 ›› Issue (4): 90-94.doi: 10.13190/jbupt.201304.91.gaoy

• 研究报告 • 上一篇    下一篇

Clos交换网络中随机化的加权匹配调度算法

高雅1, 邱智亮1, 张茂森1, 黎军2   

  1. 1. 西安电子科技大学 综合业务网理论与关键技术国家重点实验室, 西安 710071;
    2. 中国空间技术研究院 空间微波技术国家重点实验室, 西安 710100
  • 收稿日期:2012-09-04 出版日期:2013-08-31 发布日期:2013-05-22
  • 作者简介:高雅(1987—),女,博士生,E-mail:yagao@stu.xidian.edu.cn;邱智亮(1965—),男,教授,博士生导师.
  • 基金资助:

    国家高技术研究发展计划项目(2011AA01A106);国家科技支撑计划项目(2012BAH02B02)

Randomized Weight Matching Dispatching Scheme for Clos-Network Switches

GAO Ya1, QIU Zhi-liang1, ZHANG Mao-sen1, LI Jun2   

  1. 1. State Key Laboratory of Integrated Service Networks, Xidian University, Xi'an 710071, China;
    2. Science and Technology on Space Microwave Laboratory, China Academy of Space Technology, Xi'an 710100, China
  • Received:2012-09-04 Online:2013-08-31 Published:2013-05-22

摘要:

为达到100%的吞吐率,传统MSM型Clos网络调度算法通常是以高算法复杂度为代价,为避免这一现象,提出了一种低复杂度的分布式调度算法,即随机加权匹配调度,可利用缓存的信息和到达过程的随机性来寻找匹配. 该算法中,输入级模块将请求信息均匀分布到中间级模块,由各中间级模块独立分布式地执行匹配算法. 由于不需要迭代,且级间传递信息少,算法降低了调度过程中的通信开销. 仿真结果表明,新算法在多种业务下都能达到100%吞吐率.

关键词: Clos网络, 吞吐率, 最大权重匹配, 随机调度算法

Abstract:

The current dispatching schemes for memory-space-memory (MSM) Clos-network switches provide 100% throughput under admissible traffics but with higher algorithm complexity. A low-complexity and distributed scheduling algorithm, called randomized weight matching dispatching scheme (RWMD), is proposed. Under this approach, each input module balances requests among central modules, and each central module can carry out scheduling algorithm concurrently and independently, where the memory and the randomness of the arrival process are used for matching. With single iteration and less information exchange between stages, RWMD reduces the communication overhead greatly. Simulation shows that RWMD can achieve 100% throughput under uniform and non-uniform traffics.

Key words: Clos network, throughput, maximum weight matching, randomized algorithm

中图分类号: