基于交换超立方网的路由算法的研究

摘要

互联网已成为现代社会最重要的信息基础设施和人们工作、生活的重要组成部分。目前互联网采用的是一种“尽力而为”的传统模式，但是这种模式无法满足多媒体应用和各种用户对网络传输质量的要求。因此，以提高网络资源利用效率、为用户提供高质量服务作为目标的服务质量研究是当前Internet领域的热点之一。网络的路由算法的目的是建立由源结点向目的结点路由时的路径，在设计一个路由算法时，应当考虑到算法的连通性，算法的自适应性，死锁和活锁的发生率和算法的容错能力四方面的性能。
　　 在现今的网络拓扑结构中，作为流行的互连网络拓扑结构之一，超立方体(hypercube)有许多优良的优点，但是随着边数过多会引起成本效益下降。交换超立方网是一种新型的网络，它是超立方体的一个变体，它既保有了超立方体的优点，同时也克服了它的缺点。
　　 本文主要是针对交换超立方网的路由算法进行研究和分析，分别在最短路径和死锁的避免两种情况下进行了分析。下面是本文的主要研究工作：
　　 1针对交换超立方网络的最短路径的情况，利用图论的方法，研究分析交换超立方网的拓扑结构，提出相似子网的概念，并在此基础上，提出了一个交换超立方网的最短路径路由算法，理论分析表明它可输出任意一条最短路径，并通过仿真实验进一步验证了算法的有效性。
　　 2针对路由算法的无死锁性进行了分析，利用维序路由和将交换超立方网中的部分物理通道分为二个虚拟通道的技术，提出了一种无死锁的最短路径路由算法，并给予了证明。
　　 3针对算法的自适应性进行分析和研究，利用转弯模型和将一个物理通道分成二个虚通道进而形成2个不相交的虚拟网络的技术，提出了一种自适应性的无死锁路由算法。理论证明了算法的无死锁性。