论文部分内容阅读
随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一,各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。当处理器数目逐渐增多时,其发生故障的可能性也随之增加,不同处理器之间信息传递过程中的容错性便成为一个非常关键的问题。因此,如何设计新的网络容错模型以便容纳更多的错误结点,以及如何设计高效的容错路由算法以便保证无故障处理器间正确可靠的信息传递是至关重要的。超立方体网络是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、可扩展性强、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文基于LIP容错模型和局部连通性,对超立方体网络的容错性和路由算法进行研究,主要研究内容如下:1.给出了超立方体网络及其k维子立方体的概念,同时结合LIP的相关概念和性质,给出了对求解LIP长度的程序的改进,并根据程序的运行结果进行了分析。2.结合第二章最长导出路LIP的概念,提出了超立方体中基于LIP的广播容错路由算法。该算法是基于“超立方体中至少存在一条无故障结点的LIP”的前提条件的,在此条件满足的情况下,超立方体是全局连通的,且该算法能容许大量的错误结点(2n-1甚至更多),在容错性上有了很大提高。3.基于LIP容错模型和超立方体中的4维子立方体,提出超立方体网络中的一种单播容错路由算法。该算法在必要的搜索时间内,在具有大量错误结点的超立方体网络中找出连接两个正确结点的路径,并且该算法是基于局部信息的,因而具有很好的实际意义。本文在超立方体网络容错模型及路由算法方面作了一些探索工作,取得了一定的结果,但还有大量工作需要研究。首先,进一步研究超立方体网络中的LIP容错模型,给出LIP长度的近似或精确计算公式,以便更好的进行容错分析;其次,深入研究并行计算机互连网络尤其是超立方体网络中的各种容错路由算法,以便结合LIP容错模型,提出更加优越的容错路由算法;再次,对各种容错路由算法进行网络模拟,比如用NS2进行模拟,通过模拟结果对路由算法进行更加深入的分析。