高性能三级Clos交换网络结构及调度算法研究

摘要

以分组交换为基础的Internet已经成为通信网络的重要组成部分。随着光纤通信技术以及光传送网络的快速发展，Internet中现有路由器、交换机等网络设备的容量及可扩展性已无法满足要求。另一方面，分组交换逐渐被用于在卫星通信中替代传统的弯管式转发、以及承载电路交换中的实时话音等其它业务，这对网络设备的硬件复杂度、吞吐率、时延及时延抖动等方面提出了新的要求。以crossbar为代表的单级交换网络由于在容量、扩展性等方面受到限制，无法用于构建大容量交换网络。Clos交换网络使用小规模交换芯片互联组成，具有模块化、可扩展、无内部阻塞等优点，是下一代大容量路由器和交换机的主要解决方案。本文在三级Clos交换网络的基础上针对上述需求进行了研究，论文主要工作和取得的创新性成果如下：
　　1.针对memory-space-memory(MSM)型三级 Clos交换网络在不均衡业务输入时吞吐率下降的问题，提出了在多种业务模型下都具有较高吞吐率的分治调度算法。该算法首先把输入级的队列划分为若干个冲突域，分别对应于每个输出级模块，则MSM型Clos交换网络中的调度问题就可以被分解为不同冲突域内的信元选择问题；然后采用串行匹配的策略，限制了冲突发生的范围，达到了较高的吞吐率，同时减少了仲裁器和级间连线的数目，简化了交换网络的硬件设计。仿真表明，该算法可以在多种业务输入时均达到较高的的吞吐率，并具有较低的平均时延；
　　2.针对MSM型三级Clos交换网络中调度算法执行时间较长的问题，提出了一种基于流水线操作的逆向调度算法，以及一种可以降低计算复杂度的 LGMSM(Line-Grouping MSM)交换结构。
　　与传统调度算法按模块排列顺序执行匹配操作不同，逆向调度算法首先按固定的轮转顺序将信元请求发送到各中间级模块并分别进行内部匹配，然后将中间级的匹配结果返回给输入级，用于指导后续信元的转发。调度过程中信元请求的发送不依赖于前一次匹配的结果，从而实现了整个调度过程的流水线操作，同时将三级Clos交换网络的调度问题简化为了单级crossbar结构的匹配问题。理论分析证明，逆向调度算法在不增加硬件开销的前提下，有效地减少了完成一次调度所需要的时间。
　　LGMSM结构通过将连接两个交换单元的一条链路扩展为多条并行链路，在交换规模相同的情况下有效减少了交换网络中仲裁器的数目以及每个仲裁器的规模，并降低了调度算法的计算复杂度。同时，LGMSM结构在输入和输出级模块中采用多个独立缓存代替常用的共享缓存，消除了缓存加速。仿真表明，在采用相同调度算法的情况下，LGMSM结构可以获得比传统MSM型Clos交换网络更高的吞吐率。
　　3.针对分组交换网络如何有效承载电路业务的问题，在MSM型Clos交换网络的基础上提出了具有严格QoS保证的电路与分组混合交换网络及调度算法。该交换网络将内部链路分为准静态链路和动态链路两类，分别用于承载电路业务和分组业务。调度算法为电路业务建立具有一定带宽的虚拟通道，并将其映射为周期性重复的准静态链路，同时利用剩余带宽为分组业务提供尽力而为的转发服务。两种业务可以在同一交换平面上进行转发，并避免了分组业务对电路业务的干扰。仿真表明，混合交换能够满足电路业务对QoS的要求，并为分组业务提供了较高的吞吐率。
　　4.针对space-memory-memory(SMM)和memory-memory-memory(MMM)型Clos交换网络中出现的信元乱序的问题，分别提出了低复杂度的负载均衡Clos交换网络和基于交叉点带缓存crossbar结构的Clos交换网络。
　　负载均衡Clos交换网络在中间级采用两级负载均衡交换机，并采用交错对称的连接模式和基于反馈的调度算法，保证同一流的信元在中间级有相同的排队时延，并可以按序到达输出级模块。同时，该算法避免了中间级缓存的溢出问题，提高了缓存的利用率。仿真表明，负载均衡Clos交换网络在多种业务模型下均可达到较高的吞吐率，并且在输入负载较重时可以获得较低的平均时延。
　　基于交叉点带缓存crossbar结构的Clos交换网络中，所有交换单元采用了相同的交叉点带缓存的crossbar结构。输入级模块首先将同一流的信元按固定的轮转顺序依次发往所有中间级模块，然后在中间级各输出端口处采用基于最早信元优先的选择机制，最后输出级模块采用和输入级相同的轮转顺序从各交叉点缓存读出信元。理论分析证明该算法避免了交换网络的信元乱序，同时仿真表明该交换网络在避免信元乱序的同时，达到了较高的吞吐率及较低的时延。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1研究背景及意义

1.2分组交换设备的基本结构

1.3常见分组交换网络介绍

1.4 Clos交换网络的结构及存在的主要问题

1.5本文研究的主要内容及创新成果

第二章 MSM型Clos交换网络中具有较高吞吐率的分治调度算法

2.1 MSM型Clos交换网络内部路由的数学表示

2.2常用调度算法介绍

2.3 MSM型Clos交换网络中的冲突域

2.4分治调度算法

2.5性能仿真

2.6本章小结

第三章 MSM型Clos交换网络中具有较低时间复杂度的调度算法和互联结构

3.1 MSM型Clos交换网络中缓解匹配时间限制的常见策略

3.2逆向调度算法

3.3 Line-grouping互联结构

3.4本章小结

第四章 具有严格QoS保证的电路与分组混合交换网络及调度算法

1.1 Crosspath交换机和path switching算法

1.2混合交换网络的链路设置

1.3混合交换网络的结构和调度算法

1.4性能仿真

1.5本章小结

第五章 SMM和MMM型Clos交换网络的结构和按序调度算法

5.1乱序问题的产生

5.2常见按序调度算法的介绍

5.3基于负载均衡结构和反馈调度的SMM型Clos交换网络

5.4基于交叉点带缓存结构和输出级重排的Clos交换网络

5.5本章小结

第六章 结论与展望

6.1研究结论

6.2研究展望

参考文献

致谢

作者简介