可扩展多级多平面交换网络及调度算法研究

摘要

随着Internet的快速发展，数据流量与网络应用呈爆炸式增长，传输系统的传输速率随着DWDM技术的成熟提高很快，而交换技术（包括交换结构及调度算法）发展却相对滞后，日渐成为通信网络的性能瓶颈。单级结构（crossbar）在核心路由器/交换机中占有非常重要的位置，其研究成果十分丰富，对交换结构的发展起到了举足轻重的推动作用，但它的不足在如今的网络环境中也是致命的。由于单级结构先天缺乏可扩展性，因其实现成本随交换容量 N呈平方增长，很难在有限的芯片上实现大容量交换系统。
　　Log2N网络与Clos网络是两种完全不同的多级结构，无论是拓扑结构还是路由属性都有很大的区别，但有一点却是相同的，那就是它们都具有良好的可扩展性，很容易构建高速、大容量交换结构。本论文以多级多平面交换结构（包括log2N, Multi-log2N, Clos, Multi-Clos）为研究重点，主要的研究内容及研究成果包括以下几个方面：
　　?分析研究了单级结构（crossbar）及相应的调度算法
　　因可扩展性原因，单级结构无法适应信息容量急剧膨胀和网络应用复杂多样的实际需求，但它是其它可扩展交换结构的基础，无论从拓扑结构，还是从调度算法都如此。因此，我们首先分析研究了单级结构及相应的调度算法，主要分析讨论各种形式的单级结构及各自的优缺点，包括 OQ，IQ和 CIOQ等。其次，分析研究了针对单级结构的经典的调度算法，如PIM算法，iSLIP算法等。
　　?分析研究了多级结构Log2N，Multi-log2N及调度算法
　　就拓扑结构而言，log2N网络的相邻级采用部分连接，这导致log2N网络的路由路径唯一性。路径唯一性产生两个方面的结果：自选路由和内部阻塞。自选路由简化了路由控制，而内部阻塞却影响了交换性能。为了解决内部阻塞，通过将多个log2N网络构建Multi-log2N结构来破坏路径唯一性。由于HC型（水平级连）的Multi-log2N增加了网络直径，不利于光交换，因此我们在论文中重点研究 VS（垂直堆叠）型Multi-log2N结构。为了实现真正的无阻塞路由，本论文提出了基于冲突链路集的控制算法（CA-CLS）。CA-CLS算法解决了内部阻塞的问题，但未解决SE的共享问题，以至于在光交换过程产生光串扰，严重影响交换性能，于是又提出基于置换多重分解的控制算法（CA-MDP），并详细分析了CA-MDP算法性能及解决光串扰问题的有效性。
　　?分析研究Clos，Multi-Clos结构及调度算法
　　Clos网络的相邻级采用完全互连模式，因此 Clos是多路径网络，任意输入-输出之间都存在多条路由路径，因此路由控制较log2N复杂，当然可通过适当的网络配置来实现严格无阻塞，可重排无阻塞等的无阻塞结构。Clos网络中输入-输出之间的路径条数是由中间级（CS）的交换模块（CM）数来决定的，即 Clos网络中路径的选择（或分配）问题可等价地转化为 CM的分配问题，于是本文提出基于矩阵分解的并行路由控制算法（PRD-MD）。PRD-MD算法不同于已有的矩阵分解算法，它采用了逐行分解，不仅实现路径的选择，而且解决了其它同类算法的不完全性，能彻底分解满足条件的任意业务矩阵。另外，针对 CRRD算法存在的不足，本论文提出了主动授权的CRRD算法（CRRD-AG）。CRRD-AG不仅能有效降低额外的仲裁信息量，而且充分利用CS级的链路带宽，可提高吞吐率。
　　Multi-Clos结构具有很强的可扩展性，很容易通过添加平面来实现大容量交换系统。我们在TrueWay的基础上也提出了关于Multi-Clos的一些基本思路，目前虽无成熟的研究成果，但将是我们后续的研究目标。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究工作的背景和意义

1.2 可扩展交换结构及调度算法概述

1.3 本论文的主要贡献

1.4 本论文的结构安排

第二章 单级交换结构及调度算法

2.1 单级交换结构(Crossbar)

2.2 高性能路由器的调度算法

2.3 本章小结

第三章 Multi-log2N交换结构及调度算法

3.1 Log2N自选网络

3.2 Multi-log2N交换网络

3.3 VS-Multi-log2N网络的路由控制算法

3.4 VS-Multi-log2N网络性能分析模型

3.5 本章小结

第四章 Multi-Clos交换结构及调度算法

4.1 Clos网络模型及路由特性

4.2 Clos网络控制算法相关研究

4.3 基于矩阵分解的并行路由指派算法

4.4 带自主授权的CRRD控制算法

4.5 Multi-Clos交换网络结构

4.6 Multi-Clos网络的分组调度

4.7 本章小结

第五章 Log2N网络与Clos网络的比较

5.1 结构属性

5.2 路由属性

5.3 阻塞属性

5.4 阻塞问题的解决方案

5.5 本章小结

第六章 全文总结与展望

6.1 全文总结

6.2 可扩展交换网络的应用前景

6.3 后续研究工作展望

致谢

参与文献

攻读博士学位期间取得的成果