J4 ›› 2013, Vol. 40 ›› Issue (4): 42-47.doi: 10.3969/j.issn.1001-2400.2013.04.007

• 研究论文 • 上一篇    下一篇

一种低复杂度的单多播集成调度算法

蒋泳波1;杨春2;高雅1;邱智亮1   

  1. (1. 西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安  710071;
    2. 北京大学 信息科学技术学院,北京 100871)
  • 收稿日期:2012-04-18 出版日期:2013-08-20 发布日期:2013-10-10
  • 通讯作者: 蒋泳波
  • 作者简介:蒋泳波(1983-),男,西安电子科技大学博士研究生,E-mail: ybjiang@stu.xidian.edu.cn.
  • 基金资助:

    长江学者和创新团队发展计划资助项目(IRT0852);国家863计划资助项目(2011AA01A106);国家科技支撑计划资助项目(2012BAH02B02)

Integration of unicast and multicast scheduling with low complexity

JIANG Yongbo1;YANG Chun2;GAO Ya1;QIU Zhiliang1   

  1. (1. State Key Lab. of Integrated Service Networks, Xidian Univ., Xi'an  710071, China;
    2. School of Electronic Engineering and Computer Science, Peking Univ., Beijing  100871, China)
  • Received:2012-04-18 Online:2013-08-20 Published:2013-10-10
  • Contact: JIANG Yongbo

摘要:

针对目前支持单多播混合业务交换的调度算法复杂度高,可扩展性差的问题,提出一种基于多播负载均衡的两级交换结构及其UMCSA(Unicast and Multicast Concurrent Scheduling Algorithm)集成调度算法.该结构采用两级输入排队Crossbar交换单元,第1级交换单元完成单播业务交换,同时对多播业务进行负载均衡,第2级交换单元完成多播业务交换.UMCSA算法两级均采用“请求-许可”机制,本身不需要迭代,简化了执行流程,同时将控制信息复杂度降低到O(logN); 两级采用VOQ(Virtual Output Queuing)进行排队,消除了HoL(Head-of-Line)阻塞,提高了吞吐率;单多播业务分两级进行调度,并行交换,且采用简单的Round-Robin仲裁机制,具有更小的时间复杂度,更适合在高速环境中应用.仿真结果表明,在各种业务模型下,该算法均具有良好的时延和吞吐率性能.

关键词: 分组交换机, 负载均衡, 调度, 多播, 两级交换结构

Abstract:

This study focuses on the scalability problems for very large, high-speed switches, and presents a two-stage integrated scheduling algorithm named UMCSA(Unicast and Multicast Concurrent Scheduling Algorithm)which supports both unicast and multicast traffic simultaneously. The first stage of the switching fabric performs switching for unicast traffic and load-balancing for multicast traffic, while the second stage performs switching for load-balanced multicast traffic. With a two-phase(request-grant)scheme, the proposed algorithm performs without iteration, and at the same time reduces the scheduling overhead to O(logN) significantly. By using the VOQ(Virtual Output Queuing)technique for unicast and multicast traffic separately at different stages, the HoL(Head-of-Line)blocking is eliminated and therefore a good throughput performance could be achieved. UMCSA performs scheduling for unicast and multicast traffic in parallel at different stages with simple Round-Robin arbitration, which is more suitable for high-speed applications. Simulation results show that the proposed integrated algorithm exhibits a good performance in terms of throughput and average delay, at different traffic compositions under various traffic patterns.

Key words: packet switches, load-balancing, scheduling, multicast, two-stage switch architectures

中图分类号: 

  • TN915.01