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

Integration of unicast and multicast scheduling with low complexity

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

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 Multieast 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（log N） 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.