两类互连网络的边容错直径

《两类互连网络的边容错直径》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽大学硕士学位论文两类互连网络的边容错直径进入八十年代，大规模集成电路和微电子技术开始飞速发展，大型超级计算机应运而生，人们对网络系统的拓扑结构的要求不断提高，于是，图论思想和方法在网络设计和分析中的应用被大量的计算机理论工作者所接受，进而网络拓扑结构与图论的联系更加紧密，新的网络，新的概念和问题开始不断涌现。例如，为了改进连通度度量网络可靠性和容错性的准确程度，Bauer和Boesch等人[7，8，9]，Harary[10]，Esfahanian和Hakimi[11】分别提出了图的超连通性，条件连通度和限制连通度的概念。Akers等

2、人[12]对高对称网络进行分析，推动了对可迁图，尤其是对Cayley[羽的研究[13】。Chung等[14】也提出了度量路由优劣的转发指数，来更准确地度量网络路由选择给网络节点带来的负载。接着，1981年，Boesch和Harary等人[151研究了网络的点或者边发生故障对直径的影响，从而提出了网络的脆弱性的概念，法国国家科研中一I二,(CNRS)的信息研究实验室(L酣)中以Bermond为首的著名图论人士也介入此项研究，推动了对直径的研究[16】。另外，通过对容错网络的考虑，Chung和Garey[17]提出了出边添加问题和边减少问题

3、。著名数学家Alon[18]也介入此研究领域。1987年，Krishnamoorthy和Krishna-mirthy[19]正式提出容错直径概念，这个概念一经提出就受到了不小的关注。那一时期，对网络拓扑结构性质的研究成为最热门的研究。美国、日本和西欧一些国家已经充分到了组合网络理论的重要性，成立了由数学家和计算机科学家组成的国家级研究中心或研究组，如美国的“离散数学与理论计算机科学(DIMACS)’’中心，法国国家科研中一C4CNRS)的信息研究实验室(LRI)等。而且，在一些著名图论和理论计算机科学家的倡导和影响下，国内学者也开展了组

4、合网络理论的研究，现在已经成为国际上不容忽视的一支研究力量。中国科学技术大学(徐俊明)、上海交通大学(李乔)、厦门大学(张福基)、福州大学(范更华)、新疆大学(孟吉翔)、北京大学(方新贵)、等院校和单位都有很强的队伍开展研究，得到了许多令国际同行颇为关注的成果，并培养了一大批年轻科研学者和研究生。我国台湾省也有不少大学和研究所在从事组合网络的研究，在宽直径、容错直径和圈嵌入等研究方面，他们已经取得了不少的成果。1．2组合网络理论研究的内容和特点互连网络的拓扑结构是组合网络研究的主要对象，即，超大规模计算机系统2第一章引言中的元件连接模式

5、。因此，网络本身的拓扑是具体的，它的结构特性是给确定的。由于网络与图的对应关系，我们研究的图显然也是具体和确定的。这样，就可以将其转化为数学问题来进行解析，图论这一工具当然是我们的主要方法。组合网络理论的研究特点是研究网络拓扑结构的理论问题，有一定的实际相关性，它与计算机网络的发展有密不可分。因为研究哪种网络，分析哪些理论问题，这都要根据要求和实际应用来确定。在综述文献【20]中，Feng介绍了早期网络拓扑结构，它们的结构相对简单，如：线阵列(路)，单环网(圈)，树，星图，双环网，完全图，低维超立方体和立方连通圈。总的来说，它们的理论并

6、不是很深刻。连通度和直径是图论中两个网络背景很强的概念，它们被认为是网络可靠性和有效性的最重要的度量参数。在组合网络理论研究的初期，这两个参数的研究基本不涉及具体的网络结构，但随着计算机网络设计的发展，它们的受关注度在不断增加。1964年，伊利诺斯州立大学研制出第一个并行处理计算机ILLIACIV型计算机【21】，它的网络拓扑就是由n2(，z=8)处理器组成的循环无向图G(，z2；±{1，n))。在那个时候，许多专家和设计者都认为，无向图G(，z2；±{1，刀))的直径是所有，z2阶循环无向图G(n2；±{1，s))中最短的。这个猜想的

7、提出，引起了七八十年代对两种循环图G(玎；±{1，s))幂ilG(n；{1，s))直径的研究，紧接着对一般循环图的直径和连通度的研究也随之展开。1977年，世界上第一台以超立方体为互连网络拓扑结构的并行处理机BHPP在Columbia大学问世，即BolumbiaHomogeneousParallelProcessor[22，23]。随后的八十年代，有许多基于超立方体网络的超级计算机投入商业运行，比如：Caltech的Cosmic[24]，Inter的iPSC／2125】和ConnectionMachines[26]。随后，超立方体作为互

8、连网络拓扑结构得到了广泛的应用，超立方体网络的研究狂潮也就此展开。有关超立方体网络早期研究的一些结果和基于超立方体网络设计的超级计算机的发展可以参考文献[27，28，291。1987年，还专门召开了有关超立