论文部分内容阅读
将互联网络的各个处理器视为节点,各处理器之间的链接作为边,则得到该网络的一个拓扑结构,图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 ( mn mn-1 Λm1)和Qn(m)的宽直径和容错直径,并对GHC 结构优化作了讨论。作为通常讨论的容错问题的推广和补充,[10]提出了限制故障集条件?v ∈V(G ),A (v)?F下的连通度与容错直径的问题。本文对Q ( mn mn-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 图和图的笛卡尔积综合利用,将有利于设计出满足要求的优化的网络。