几类网络的结构及相关参数研究

论文摘要

将互联网络的各个处理器视为节点,各处理器之间的链接作为边,则得到该网络的一个拓扑结构,图G。图G 的性质直接反映网络的性能。考虑到在网络信息传输中对小的通信延迟和大的容错性能的需求,以及在构造网络中经济因素及物理机制等方面的要求,本文在研究一般图的宽直径,容错直径的基础之上,对n-cube,m-ary n-cube,GHC,n-star 等网络的性能和结构作了研究和比较。研究图的宽直径,容错直径等参数是本文的主要手段。设C n为一个n 点的圈,在C n中添加t 条边得到的图的集合记为C （ n,t）,[12]中定义了函数h （ n,t）= min{d2 （G）G∈C（n,t）}并将h （ n,t）的计算作为公开问题提出。本文对函数h （ n,t）进行了讨论。n-cube 作为一个具有广泛应用的流行网络拓扑,具有很好的性质,而以它为基础的GHC 结构既具有类似的拓扑结构,又突破了点数必须为2 的幂的限制。本文在文献[9] 中提出的路由算法的基础之上计算了Q ( mnmn-1Λm1)和Qn（m）的宽直径和容错直径,并对GHC 结构优化作了讨论。作为通常讨论的容错问题的推广和补充,[10]提出了限制故障集条件?v ∈V（G ）,A （v）?F下的连通度与容错直径的问题。本文对Q ( mnmn-1 L m1)和Qn（m）在限制故障集合条件下的连通度与容错直径进行了讨论和计算。作为对n-cube 的性能进一步提高的拓扑结构,本文将n-star 网络与n-cube网络在基本参数,基本结构,基本路由等方面进行了比较。n-star 具有很多优于n-cube 的性质。然而其缺点也是明显的,即不同阶的n-star 的顶点数跃迁太大。作为对这一缺陷的弥补,文中介绍了arrangement graph 网络和（n,k）-star 网络,并列出了它们的基本性质。Cayley 图由于其正则性,传递性以及规整性近年来受到广泛的关注。在设计具有强层次性结构的网络时,Cayley 图往往是首选。而两个图的笛卡尔积由于兼具两个图的很多性质,在设计有特殊要求的网络时,往往是不错的选择。本文对积图的性质作了补充,证明了积图具有传递性,并将一些典型的网络的笛卡尔积的基本参数作了对比。计算参数是手段,但研究网络结构,为设计更为优化的网络结构作必要的知识准备才是本文的目的。作者认为将Cayley 图和图的笛卡尔积综合利用,将有利于设计出满足要求的优化的网络。

论文目录

• 第一章 综述
• 1.1 引言
• 1.2 流行的网络拓扑
• 1.3 宽直径与容错直径的概念
• 1.4 图的宽直径一般结论
• 1.5 宽直径与容错直径的关系
• 1.6 限制故障集容错问题
• 第二章 立方体网络
• 2.1 n 维超立方体及其基本性质
• 2.2 n-cube 网络中的容错问题
• 2.3 广义超立方体的结构以及基本性质
• 2.4 GHC 结构优化
• 第三章 星网络
• 3.1 n-star 网络
• 3.2 由n-star 派生出的其他网络介绍
• 第四章 Cayley 图与积图
• 4.1 Cayley 图
• 4.2 图的笛卡尔积
• 第五章 结论
• 参考文献
• 致谢
• 个人简介