增广泡型网络的边连通性和限制边连通性

开篇：润墨网以专业的文秘视角，为您筛选了一篇增广泡型网络的边连通性和限制边连通性范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：并行计算机系统通常以某一高性能网络作为底层拓扑结构。泡型网络是并行计算机系统的候选拓扑结构之一。针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端，采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法，证实了n维增广泡型网络中去除任意不多于n-1条边时，该增广泡型网络的任意两个节点之间依旧连通；通过构造最小限制边割的方法，证实了在不产生孤立节点的条件下，n维增广泡型网络中去除任意不多于2n-3条边时，该增广泡型网络的任意两个节点之间依旧连通。依据上述结果，通过实例证明增广泡型网络的容错能力优于泡型网络。

关键词：并行计算机；高性能网络；泡型网络；增广泡型网络；边连通度；限制边连通度

中图分类号：TP302.01； TP393.02

文献标志码：A

文章编号：1001-9081（2016）11-3006-04

0 引言

目前，大数据的处理和复杂问题的解决对并行计算机的计算能力已近乎苛刻。为了大幅提高计算能力，并行计算机系统的处理器数目急剧增加，从而导致处理器之间的通信开销越来越大。在超级并行计算机系统中，处理器之间的连接模式（即底层网络）对整个系统的硬件消耗、通信性能等方面起着重要的、甚至是决定性的作用。

在实际的系统中，元器件和直连线路难免发生故障。在故障发生时，人们自然希望该系统的任意两个节点之间依旧可以通信； 反映在其底层网络中，人们希望网络依旧连通。连通度和边连通度是度量网络连通性和容错能力的主要参数。然而，这两个参数存在一个明显的缺陷，它认为“和同一个节点相关联的所有边”或“和一条边相关联的所有节点”很有可能同时发生故障。然而，在实际的系统中，同时故障几乎是不可能的。为弥补这一不足，Esfahanian等[1]对发生故障的系统的各个分支加以限制，提出了条件连通度和条件边连通度的概念。自此，许多经典网络的条件连通度[2-4]和条件边连通度被相继研究[5-6]，其中，泡型网络（bubble-sort network）是并行计算机系统的主要候选网络之一，它具有正则性、点对称性、二部性、层次性等优秀的拓扑性质[7-10]。

n维泡型网络的边连通度仅为n-1，限制边连通度仅为2n-4，从而导致其容错能力不强。为此，在泡型网络的基础上设计了一种保留了泡型网络的大多数优秀拓扑性质的增广泡型网络， 并证明了n≥3时，n维增广泡型网络的边连通度为n，限制边连通度为2n-2。对比结果表明，增广泡型网络比泡型网络具有更高的连通性和更强的容错能力。

4 结语

并行计算机系统底层网络的选择和设计对系统的性能具有决定作用。本文在泡型网络的基础上设计了一款新的网络结构，即增广泡型网络。由于增广泡型网络中包含同维的泡型网络，所以它继承了泡型网络的绝大多数优秀性能，并且可以移植泡型网络的路由算法，模拟泡型网络的行为。同时，由于每个节点按照既定的规律增加1度，使得增广泡型网络具有比泡型网络更好的连通性能和更强的容错能力。当故障发生时，增广泡型网络的容错路由算法，节点之间的信息并发机制，子网保持能力等是值得进一步关注的主要问题。

参考文献：

[1] ESFAHANIAN A H， HAKIMI S L. On computing a conditional edge-connectivity of a graph[J]. Information Processing Letters， 1988， 27（4）： 195-199.

[2] WANG X， FAN J， ZHOU J， et al. The restricted h-connectivity of the data center network DCell[J]. Discrete Applied Mathematics， 2016，203：144-157.

[3] HSIEH S Y， HUANG H W， LEE C W. {2，3}-restricted connectivity of locally twisted cubes[J]. Theoretical Computer Science， 2016，615：78-90.

[4] LIN L， XU L， ZHOU S， et al. The extra， restricted connectivity and conditional diagnosability of split-star networks[J]. IEEE Transactions on Parallel and Disributed Systems， 2016，27（2）：533-545.

[5] LIN R， ZHANG H. The restricted edge-connectivity and restricted connectivity of augmented k-ary n-cubes[J]. International Journal of Computer Mathematics， 2016，93（8）：1281-1298.

[6] LI S， TU J， YU C. The generalized 3-connectivity of star graphs and bubble-sort graphs[J]. Applied Mathematics and Computation， 2016， 274（4）： 41-46.

[7] XU X， XU M， JING J. Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs[J]. Acta Mathematica Sinica （English Series）， 2012， 28（4）： 675-686.

[8] WANG J， XU X， GAO L. Decycling bubble sort graphs[J]. Discrete Applied Mathematics， 2015， 194（C）： 178-182.

[9] WANG S， YANG Y. Fault tolerance in bubble-sort graph networks[J]. Theoretical Computer Science， 2012， 421（3）：62-69.

[10] YANG Y， WANG S， LI J. Subnetwork preclusion for bubble-sort networks[J]. Information Processing Letters， 2015， 115（11）： 817-821.

[11] CHENG E， LIPTK L， SHAWASH N， Orienting Cayley graphs generated by transposition trees[J]. Computers and Mathematics with Applications， 2008， 55（11）： 2662-2672.

[12] BONDY J A， MURTY U S R. Graph Theory[M]. New York： Springer， 2008： 623-628.