互联网络容错性质分析

论文摘要

网络的拓扑结构是设计和制造集群计算机或超大规模并行计算机系统的第一步，也是实现各种协议的基础，它对网络的性能、系统可靠性和费用都有重大影响。人们通常把互连网络中的处理器抽象成一个点，把处理器之间的信道抽象成两点之间的连线，那么该网络的拓扑结构就被抽象成一个图，研究网络拓扑结构问题就归结为研究图的结构问题，网络的容错性研究可以转化成对图的参数研究。互连网络主要有以下的评价指标：（1）硬件复杂度：可以用拓扑图的顶点度来衡量。（2）通信开销：可以用网络拓扑图的直径来、平均距离来衡量。（3）可扩展性：就是一个小网络要扩充为一个大网络，并保留小网络的结构性质的可能性，它可以归结为图的可嵌入性问题。（4）容错能力：可以用图的连通度以及边连通度、网络的容错直径，宽直径，限制连通度和限制边连通度来衡量。目前讨论比较多的网络主要有网状网、树状网、超方体状网和星状网类型网络。本文主要考虑这些网络的容错性质，我们的工作如下：首先，我们对这些主要的网络拓扑结构的容错性指标，例如通信延迟、容错直径与宽直径、连通性质进行了系统的总结，在此基础上，提出了互连网络拓扑容错性方面一些值得进一步研究的问题。然后，本文对超立方体的子图——广义Fibonacci立方体进行进一步研究。对广义Fibonacci立方体的研究已有很多，包括连通度、递归性，可嵌入环和格、直径。本文研究广义Fibonacci立方体的容错直径，宽直径，限制边连通度和超边连通度，证明了容错直径，宽直径等于它的直径加1，确定了其1-限制边连通度和1-超边连通度。

论文目录

• 中文摘要
• 英文摘要
• 第一章 互联网络容错性研究现状
• §1.1 引言
• §1.2 网络拓扑容错性衡量标准
• §1.3 各种网络拓扑性能比较
• 1.3.1 超方体状网络拓扑结构
• 1.3.2 网状网络拓扑结构
• 1.3.3 星形网络拓扑结构
• 1.3.4 其他网络拓扑结构
• §1.4 结论
• 第二章 广义Fibonacci立方体的容错直径和宽直径
• §2.1 引言
• §2.2 广义Fibonacci立方体
• §2.3 广义Fibonacci立方体的拓扑性质
• 2.3.1 度和连通度
• 2.3.2 点数和边数
• 2.3.3 哈密尔顿性质
• 2.3.4 直径
• 2.3.5 FC（n）与EFC（n）
• 2.3.6 容错直径和宽直径
• §2.4 结论
• 第三章 广义Fibonacci立方体的限制边连通度和超边连通度
• §3.1 限制边连通度和超边连通度
• §3.2 广义Fibonacci立方体的1-限制边连通度和1-超边连通度
• 结语
• 参考文献
• 攻读硕士学位期间完成的论文
• 后记