CLOS网络可重排算法研究

摘要

配线架是网络及信息系统最基础的部分，其核心功能模块——开关网络的处理连接请求的能力决定了整个网络的性能。如果开关网络能够很好的处理多个连接请求，并使这些请求不发生冲突，那么整个网络的丢失请求率将会大大降低，网络性能也比较好。如果开关网络对于多个连接请求不能很好的处理，及时有效的为其寻找到正确的路由，那么网络就会总是处于阻塞的状态，网络性能大大降低，将影响网络用户的使用。
　　从开关网络的阻塞特性来看，一般将开关网络分为无阻塞网络和有阻塞网络。无阻塞网络又可以分为三种：严格不阻塞网络，广义不阻塞网络和可重排不阻塞网络。严格不阻塞网络对于网络硬件的要求比较高，在工程上不利于实现。广义不阻塞网络目前研究尚少。可重排不阻塞网络对网络的要求不高，利于实现，网络不阻塞的关键是其路由算法。衡量有阻塞网络性能的指标是阻塞概率。
　　本文选取 CLOS网络为研究背景，仔细研究了历年来国际上提出的各种可重排不阻塞算法，并在此基础上提出了两种重排算法：即阻塞即重排算法和可降低连接阻塞概率的重排算法。即阻塞即重排算法改进了以往的存在多条阻塞连接再重新路由的方法，提出一旦连接请求发生阻塞立即重排的思路，缩减了为调用重排算法而人为加入连接的过程，大大提高了算法的效率。并且算法被理论证明了具有收敛性。可降低连接阻塞概率的重排算法是将重排的概念引入有阻塞网络中，在为某请求建立路由的同时，预测出此连接是否会对后面的连接请求产生影响，即阻塞概率是否为0。如果答案是肯定的，那么调用重排算法，改动已经建立的连接方式，使阻塞概率降低。
　　文章首先简单的介绍了研究的相关背景：配线架，开关网络和CLOS网络。接着讨论了CLOS网络的阻塞和不阻塞特性，一些相关的算法，还提出了阻塞概率的计算方法，为第五章的可降低连接阻塞概率的重排算法做了一定的铺垫。然后详细的介绍了国际上比较先进的四种可重排算法。
　　本文提出的即阻塞即重排算法改进了传统的可重排算法中对连接说明矩阵进行操作的做法，提出了集合矩阵的概念，对集合矩阵的操作更能直观的表现网络的连接方式。集合矩阵中元素的交换，也采用智能的方法，极大程度的避免回溯和同行元素重复交换的情况，算法同时还被证明了具备收敛性。
　　可降低连接阻塞概率的重排算法采用的思想是使中间级交换单元的选取尽可能的集中在已经被占用的少数几个中，使空闲的中间级交换单元的利用性提高，从而降低网络的阻塞特性。本文通过程序仿真验证了此算法能使连接阻塞概率降低20％至30%，从而说明此算法对于降低阻塞概率有很大的帮助。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 配线架

1.2 开关网络

1.3 三级CLOS网络

1.4 论文的研究思路及结构

1.5 本章小结

第二章 CLOS网络的无阻塞及有阻塞特性

2.1 三级CLOS严格无阻塞网络

2.2 三级CLOS可重排无阻塞网络

2.3 三级CLOS有阻塞网络

2.4 本章小结

第三章 三级CLOS网络的可重排算法

3.1 三级CLOS重排网络的路由算法分类

3.2 连接说明矩阵

3.3 现有的可重排无阻塞算法

3.4 本章小结

第四章 即阻塞即重排算法

4.1 集合矩阵

4.2 即阻塞即重排算法

4.3 算法收敛性说明

4.4 算法适用性

4.5 性能分析与比较

4.6 本章小结

第五章 可降低连接阻塞概率的重排算法

5.1 算法的预见性

5.2 重排算法

5.3 仿真结果分析及比较

5.4 本章小结

第六章 仿真程序设计说明

6.1 Lee-Hwang-Caponelli算法的仿真验证

6.2 可降低阻塞概率的可重排算法的仿真设计说明

第七章 结束语

致谢

参考文献

个人简介，研究成果与获奖情况