互联网络PCP(n)的容错性研究

摘要

并行计算机系统中的容错技术是当今计算机科学研究的热点之一。网络容错是指，在互联网络中某些节点或链路发生故障的情形下，仍能保证网络中无故障的节点之间进行可靠的信息传送。一个网络的容错度，是网络中能保证任意两个无故障节点间进行可靠信息传送所允许故障节点的最大个数。互联网络作为并行计算机系统的主干，其容错性能的高低用容错度来衡量，容错度越高，容错性能越好。因此，高容错度是互联网络设计的重要目标之一。
　　交叉立方体互联网络，是超立方体互联网络的一种变形，它在某些方面有着比超立方体更好的拓扑性质，因此是非常具有吸引力的互联网络拓扑结构之一。RCP(n)互联网络（即基于交叉立方体环连接的彼特森图互联网络）是一种新型的并行计算机互联网络拓扑结构，环的简单扩展性、彼特森图的短直径与交叉立方体网络中节点的高可连接性，使得RCP(n)网络具有良好的通信性能。
　　本文的主要研究成果是论文的第三章和第四章。
　　第三章提出了局部k维子交叉立方体连通性和局部子交叉立方体连通性的概念，并给出交叉立方体互联网络中两种基于子交叉立方体结构的局部连通性容错模型;基于这两种局部连通性容错模型，设计了两个高效的单播容错路由算法，并分析了路由算法的时间复杂度。在这两种局部连通性容错模型中，即使交叉立方体网络中的错误节点数接近50％，正确节点仍能保持连通。两个容错路由算法的时间复杂度分别为O(n)和O(n2)，都是多项式时间算法，并且都是基于局部信息，因而具有很好的通信性能。
　　第四章构建了RCP(n)网络上的三种容错模型:以环为基本容错元素的容错模型，以彼特森图为基本容错元素的容错模型和以交叉立方体为基本容错元素的容错模型;基于局部（k维）子交叉立方体连通的RCP(n)网络容错模型，给出了RCP(n)网络上的两个容错路由算法，其时间复杂度都是O(2n-3)。虽然时间复杂度是指数的，但因为n的取值不会太大，所以它们仍然是通信高效的。这三种容错模型中，以环为基本容错元素的容错模型适合网络中的错误节点分布比较均匀的情况，可允许20％到40％的错误节点;以彼特森图为基本容错元素的容错模型可允许40％的错误节点;以交叉立方体为基本容错元素的容错模型不仅适合网络中的错误节点分布均匀的情况，也适合错误节点分布不均匀的情况，并且其容错度最高，可达将近50％。因此，这三种容错模型都是合理的、高容错性的。

目录

摘要

第一章 引言

1．1 研究目的及意义

1．2 国内外研究现状

1．3 主要研究内容

第二章 预备知识

2．1 互联网络拓扑结构的相关概念

2．2 几种重要的互联网络

第三章 交叉立方体网络容错模型及容错路由算法

3．1 概述

3．2 交叉立方体网络的局部连通性容错模型

3．3 交叉立方体容错路由算法

3．3．1 基于局部k维子交叉立方体连通容错模型的容错路由算法

3．3．2 基于局部子交叉立方体连通容错模型的容错路由算法

3．4 本章小结

第四章 RCP(n)网络容错模型及容错路由算法

4．1 RCP(n)网络容错模型

4．1．1 以环为基本元素的RCP(n)网络容错模型

4．1．2 以彼特森图为基本元素的RCP(n)网络容错模型

4．1．3 以交叉立方体为基本元素的RCP(n)网络容错模型

4．2 RCP(n)网络容错路由算法

4．3 本章小结

结束语

参考文献

攻读硕士期间发表论文情况

个人简况及联系方式

致谢

声明