由于均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性,超立方体(Hypercube)和彼特森图(Petersen Graph)互联网络受到了研究者们的广泛关注,是迄今为止最为重要和最具吸引力的并行计算机互联网络拓扑结构之一。随着现在的并行计算机互联网络规模越来越大,网络中出现处理机故障或处理机间的链路故障的可能性也越来越大;这就使得并行计算机互联网络的容错性及其研究也变得越来越重要,因此,设计具有较好容错性的路由算法对并行计算机互联网络有着重要意义。 到目前为止,人们已经对超立方体或彼特森图互联网络的拓扑特性及其容错模型与容错路由算法方面分别进行了深入的研究,并基于超立方体或彼特森图互联网络的拓扑特性分别建立了一些容错模型及其容错路由算法,但上述研究均是针对超立方体或彼特森图互联网络单独进行的,缺乏对这两种互联网络系统的综合研究。超立方体和彼特森图互联网络虽然在本质上各不相同,但由于它们均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性,在拓扑特性上具有很大程度的相似性,而且还可以通过相互结合形成具有某些特殊性质的新型互联网络拓扑结构,因此,将超立方体和彼特森图互联网络综合起来进行系统深入的研究,将比对其中的单个网络进行孤立研究具有更好的效果,能更进一步地促进对这两种互联网络乃至整个高性能并行计算机互联网络的研究发展,特别地,取两个网络拓扑特性之长来弥补各自之短,研究如何利用超立方体互联网络的可扩展性和彼特森图互联网络的短直径特性来构造出具有更优特性的新型并行计算机互联网络,将具有重要的研究价值。综上所述,本文综合系统地研究超立方体和彼特森图这两种具有相似拓扑特性的高性能并行计算机互联网络的拓扑特性及其容错模型与容错路由算法。 在对超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面,本文首先综述了目前国内、国际上在超立方体互联网络研究方面所做的主要研究工作,并基于已有的一些研究成果,提出了三种新的超立方体互联网络的容错模型及其容错路由算法:即基于极大安全通路向量的容错模型MSPV(Maximal Safety Path Vector)及其容错路由算法、基于极大安全通路矩阵的容错模型MSPM(Maximal Safety Path Matrix)及其容错路由算法,以及基于两类子连通性的超立方体互联网络容错模型及其容错路由算法;证明了上述超立方体互联网络的容错模型及其容错路由算法分别是基于安全向量的容错模型SV(Safety Vector)、基于扩展安全向量的容错模型ESV(Extended Safety Vector)、基于最优通路矩阵的容错模型OPM(Optimal Path Matrix)、基于扩展最优通路矩阵的容错模型EOPM(Extended