Mobius立方体互连网络容错路由选择算法研究

摘要

本文以提高网络的容错度为目的，在M(o)bius立方体这种互连网络拓扑结构下，考虑故障处理器发生的概率和故障处理器的分布状况，即在条件连通度下分析互连网络的容错性能和容错路由选择问题。 首先，本文以0-M(o)bius立方体为例证明了M(o)bius立方体在其任一顶点的邻接顶点并不同时发生故障时，Mobius立方体的条件顶点连通度也为2n-2。 然后，本文给出一个M(o)bius立方体互连网络上基于顶点连通度的容错路由选择算法，分析该算法的时间复杂度为O(n)，并且证明在Mn中，在给定一组至多有n-1个故障顶点的故障集F的条件下，对于两个无故障顶点s和t，能够在O(n)时间内找到从s→t的一条无故障路径。 接下来，本文给出M(o)bius立方体互连网络上基于条件顶点连通度的一个容错路由选择算法，分析该算法的时间复杂度为O(n)，并且证明在1-safe的Mn中，在给定故障集F( )V(Mn)，且|F|≤2n-3的条件下，对于两个无故障顶点s，t∈V(Mn-F)，能够在O(n)的时间内找到一条从s →t的无故障路径。 最后，本文还证明了1-safe条件下M(o)bius立方体的条件边连通度也为2n-2，其基于边连通度和基于条件边连通度的容错路由选择算法同基于顶点连通度和基于条件顶点连通度的容错路由选择算法类似。

目录

文摘

英文文摘

第一章引言

第二章预备知识

第三章1-safe条件下Mobius立方体的条件顶点连通度

第四章Mobius立方体互连网络上基于顶点连通度的容错路由选择算法

4.1基于顶点连通度的Mobius立方体的容错路由选择算法

4.2基于算法Routing_1下的最长路径长度分析

第五章Mobius立方体互连网络上基于条件顶点连通度的容错路由选择算法

5.1基于条件顶点连通度的Mobius立方体的容错路由选择算法

5.2基于算法Routing_2下的最长路径长度分析

第六章Mobius立方体的条件边连通度

6.1 Mobius立方体的边连通度

6.2 Mobius立方体的条件边连通度

总结与展望

参考文献

攻读学位期间的研究成果

附录

1基于顶点连通度的MOBIUS立方体的容错路由选择程序

2基于条件顶点连通度的MOBIUS立方体容错路由选择程序

致谢

学位论文独创性声明、学位论文知识产权权属声明