M（？）bius 立方体互连网络容错路由选择算法研究

论文摘要

Mobius立方体具有很多优越的性质,已经被用作多种并行机中处理器连接的拓扑结构并引起了国际上许多研究者的研究兴趣。本文以提高网络的容错度为目的,在Mobius立方体这种互连网络拓扑结构下,考虑故障处理器发生的概率和故障处理器的分布状况,即在条件连通度下分析互连网络的容错性能和容错路由选择问题。 首先,本文以0-Mobius立方体为例证明了Mobius立方体在其任一顶点的邻接顶点并不同时发生故障时,Mobius立方体的条件顶点连通度也为2n-2,即1-safe条件下Mobius立方体的条件顶点连通度为2n-2,其容错度为2n-3。 然后,本文给出一个Mobius立方体互连网络上基于顶点连通度的容错路由选择算法,分析该算法的时间复杂度为O（n）,并且证明在Mn中,在给定一组至多有n-1个故障顶点的故障集F的条件下,对于两个无故障顶点s和t,能够在O（n）时间内找到从s→t的一条无故障路径,且路径长度至多为:「（n-「log|F|」）/2」+4「log|F|」+2,并且当n充分大时,这条最长路径长度近似于Mn的直径。 接下来,本文给出Mobius立方体互连网络上基于条件顶点连通度的一个容错路由选择算法,分析该算法的时间复杂度为O（n）,并且证明在1-safe的Mn中,在给定故障集F（?）V（Mn）,且|F|≤2n-3的条件下,对于两个无故障顶点s,t∈V（Mn-F）,能够在O（n）的时间内找到一条从s→t的无故障路径,且路径长度最长为:「（n-「log|F|」）/2」+4（「log|F|」+1）,并且当n分大时,这条最长路径长度近似于Mn的直径。 最后,本文还证明了1-safe条件下Mobius立方体的条件边连通度也为2n-2,其基于边连通度和基于条件边连通度的容错路由选择算法同基于顶点连通度和基于条件顶点连通度的容错路由选择算法类似。 另外,本文对上面提出的两种算法设计了基于C语言的模拟程序,证明了他们的正确性。

论文目录

• 第一章 引言
• 第二章 预备知识
• 第三章 1-safe条件下M（o|¨）bius立方体的条件顶点连通度
• 第四章 M（o|¨）bius立方体互连网络上基于顶点连通度的容错路由选择算法
• 4.1 基于顶点连通度的M（o|¨）bius立方体的容错路由选择算法
• 1下的最长路径长度分析'>4.2 基于算法Routing₁下的最长路径长度分析
• 第五章 M（o|¨）bius立方体互连网络上基于条件顶点连通度的容错路由选择算法
• 5.1 基于条件顶点连通度的M（o|¨）bius立方体的容错路由选择算法
• 2下的最长路径长度分析'>5.2 基于算法Routing₂下的最长路径长度分析
• 第六章 M（o|¨）bius立方体的条件边连通度
• 6.1 M（o|¨）bius立方体的边连通度
• 6.2 M（o|¨）bius立方体的条件边连通度
• 总结与展望
• 参考文献
• 攻读学位期间的研究成果
• 附录
• 致谢
• 学位论文独创性声明、学位论文知识产权权属声明