多级分组交换网络中基于负载均衡的调度算法研究

摘要

网络的高速发展特别是新一代数据中心及云计算应用的出现,对构建互联网基础架构的交换机和路由器提出了更高要求。作为网络设备核心的交换架构,需要向更大容量、更优性能、更好的可扩展性和更精细的QoS保障等方向发展,以满足不断涌现的各种新型业务和应用。单级Crossbar交换网络是目前核心路由器主流交换网络结构,但是受工程实现的限制(如机架供电、芯片面积、端口密度等),无法做到更大容量。采用小型的交换模块搭建大容量的多级交换网络,可以避免上述问题。这其中三级Clos交换网络由于模块化、可扩展、无内部阻塞的优点获得广泛关注。
　　目前针对三级Clos交换网络调度算法的研究是对单级Crossbar交换网络研究成果的简单推广,存在调度算法复杂度高、级间通信开销大、多路径均衡负载时信元发生乱序、缺乏对多播业务的支持等问题。在Clos交换网络中,一对输入输出端口之间存在多条中间路径,如何有效地在这多条路径中均衡业务以便获得高吞吐率性能,但同时又不引起乱序问题和增加复杂度,这一点需要深入研究。同样是均衡负载,两级负载均衡交换虽然与单级Crossbar交换网络一样,存在端口数目限制的问题,但是其在简化调度过程、提供稳定吞吐率性能等方面的优势仍然值得借鉴。因此本文基于负载均衡的思想,对不同结构三级Clos网络调度算法的关键技术进行了研究。主要创新点包括:
　　1.研究了各级带缓存Clos网络的乱序问题。MMM结构Clos交换网络中间级缓存的存在缓解了输出端口的冲突,但是当不同路径上的缓存队列长度不一致时,会引起输出端口信元乱序。传统的按序调度算法或者引入复杂的匹配调度过程,或者需要逐信元反馈流控信息,限制了MMM交换的可扩展性,并且这些算法均不能达到100％吞吐率。本文提出了两种基于填补帧技术的按序调度算法(EPF算法和FIM3算法),具有复杂度低、灵活性高的优点,可在按序调度的同时提供100%吞吐率性能。所提调度算法将到达业务逐流逐帧均匀分布到所有中间级模块,通过使信元经过的中间级缓存队列长度一致来保证信元不发生乱序。一帧信元的数目与中间级模块数目相等。为避免低负载队列的饥饿问题,不满一帧的队列可通过填补空信元的方式获得发送机会。EPF算法在输入和输出级交换模块采用周期确定性轮转配置,不需要执行调度算法。在此基础上,FIM3算法在输出级采用交叉点缓存交换结构,结合最老信元优先调度算法,进一步改善了低负载时算法的时延性能。理论分析和仿真验证结果均表明在可允许业务下,所提算法无乱序、同时可提供100%的吞吐率性能。
　　2.研究了各级带缓存Clos网络的多播支持问题。现有的多播调度算法在中间级和输出级采用输入排队FIFO结构,其吞吐率性能受多播队头阻塞影响较大;并且,以分组为粒度的调度虽然避免了分组内信元的乱序,但未能消除分组间的乱序,且总的乱序程度未被有效降低。尽管已有大量按序单播调度算法,但是考虑到多播业务扇出分布的特点,难以采用逐流业务均衡。本文提出了一种基于填补帧技术的多播调度算法(FMClos),具有较高的吞吐率和较低的乱序比例。该调度算法以信元为调度粒度,多播信元在输入级和输出级采用地址复制扇出机制进行入队操作,消除多播队头阻塞影响,提高了交换网络的吞吐率。所提算法输入级和中间级基于输出模块排队并进行逐帧调度,结合中间级模块采用的交叉点带缓存Crossbar交换单元,有效地控制了信元乱序影响的范围。仿真结果表明,所提多播调度算法的吞吐率性能接近100%,并且相比已有的多播调度算法,其乱序比例以及重排所需时延被大幅降低。
　　3.研究了输入输出级带缓存Clos网络的加权匹配调度算法,提出了MSM结构Clos网络一种分布式加权匹配调度算法(DWMD),具有复杂度低、级间通信开销小、匹配效率高的优点。在分布式加权匹配调度算法中,每个输入模块将请求令牌均衡到所有中间级模块。各中间级模块依据本地维护的虚拟令牌计数器值执行基于权重的匹配算法,如启发式的加权匹配或随机化的加权匹配,不需要了解全局请求信息或其它中间级模块的匹配信息。该调度算法继承了负载均衡交换和加权匹配算法的优点,但既没有引起信元乱序,也没有增加通信开销。仿真结果表明,分布式加权匹配调度算法在多种业务类型下均可达到100%吞吐率,并且相比已有的加权匹配调度算法,新算法具有更高的匹配效率。
　　4.研究了输入输出级带缓存Clos网络的多播支持问题,提出了一种基于静态轮询的单多播集成调度算法(MUSRRD)。所提算法对单多播信元分开入队,隔离了两种业务之间的影响;且多播信元在输入级基于输出模块地址复制扇出入队,消除了多播排头阻塞。由于该单多播集成调度算法不增加模块间调度信息,因此在静态轮询单播调度算法的基础上,只需对输入模块内的从判决器进行重新设计。研究表明,该算法继承了静态轮询单播调度算法中指针初始化和更新方式简单高效的特点,可提供业务类型级和流级的公平,并且算法复杂度低、硬件实现简单。

目录

封面

声明

中文摘要

英文摘要

目录

缩略词

第一章 绪论

1.1 研究背景与意义

1.2 单级交换网络研究概述

1.3 多级分组交换网络主要存在问题

1.4 论文的主要贡献及结构安排

第二章 交换网络结构及调度算法研究基础

2.1 三级Clos交换网络研究

2.2 两级负载均衡交换的按序调度算法

2.3 Crossbar交换网络的多播调度算法

2.4 交换机仿真业务模型

2.5 本章小结

第三章 各级带缓存Clos网络的按序调度算法研究

3.1 MMM结构Clos网络已有的按序调度算法

3.2 输入输出级周期轮转的按序调度算法（EPF）

3.3 输入级周期轮转的按序调度算法（FIM3）

3.4 本章小结

第四章 各级带缓存Clos网络的多播调度算法研究

4.1 中间级带缓存Clos网络已有的多播调度算法

4.2 MMM结构Clos网络基于帧的多播调度算法（FMClos）

4.3 仿真结果和性能分析

4.4 本章小结

第五章 输入输出级带缓存Clos网络的加权调度算法研究

5.1 MSM结构Clos网络已有的加权匹配调度算法

5.2 MSM结构Clos网络分布式加权匹配调度算法（DWMD）

5.3 算法特性分析

5.4 仿真结果和性能分析

5.5 本章小结

第六章 输入输出级带缓存Clos网络的多播调度算法研究

6.1 现有Clos网络多播调度研究及存在问题

6.2 基于静态轮询的单多播集成调度算法（MUSRRD）

6.3 仿真结果和性能分析

6.4 本章小结

第七章 总结与展望

7.1 全文总结

7.2 后续工作展望

参考文献

致谢

在学期间的研究成果