计算机科学 ›› 2024, Vol. 51 ›› Issue (9): 346-356.doi: 10.11896/jsjkx.230700041

• 计算机网络 • 上一篇    下一篇

增广立方体上边独立生成树的并行构造

李夏晶1,2, 程宝雷1,2, 樊建席1, 王岩1,2, 李晓瑞1,2   

  1. 1 苏州大学计算机科学与技术学院 江苏 苏州 215006
    2 苏州大学江苏省计算机信息处理技术重点实验室 江苏 苏州 215006
  • 收稿日期:2023-07-06 修回日期:2023-11-02 出版日期:2024-09-15 发布日期:2024-09-10
  • 通讯作者: 程宝雷(chengbaolei@suda.edu.cn)
  • 作者简介:(20215227119@stu.suda.edu.cn)
  • 基金资助:
    国家自然科学基金(62272333,62172291);江苏省教育厅未来网络科研基金资助(FNSRFP-2021-YB-39);江苏高校优势学科建设工程资助项目

Parallel Construction of Edge-independent Spanning Trees in Augmented Cubes

LI Xiajing1,2, CHENG Baolei1,2, FAN Jianxi1, WANG Yan1,2, LI Xiaorui1,2   

  1. 1 School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
    2 Provincial Key Laboratory for Computer Information Processing Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2023-07-06 Revised:2023-11-02 Online:2024-09-15 Published:2024-09-10
  • About author:LI Xiajing,born in 1999,postgraduate,is a member of CCF( No.J1607G).Her main research interests include parallel and distributed systems and graph algorithms.
    CHENG Baolei,born in 1979,professor,is a member of CCF( No.16200S).His main research interests include parallel and distributed systems,algorithms,interconnection architectures and software testing.
  • Supported by:
    National Natural Science Foundation of China(62272333,62172291),Jiangsu Province Department of Education Future Network Research Fund Project(FNSRFP-2021-YB-39) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

摘要: 近年来,围绕互连网络的研究工作越来越多。其中独立生成树(Independent Spanning Trees,ISTs)可以应用于信息的可靠传输、并行传输、安全分发以及故障服务器的并行诊断中,因此受到了许多研究者的关注。在一对多广播、可靠通信、多节点广播、容错广播、安全消息分发、IP快速重路由等网络通信中,边独立生成树(Edge-Independent Spanning Trees,EISTs)发挥着重要作用。n维增广立方体AQn是n维超立方体Qn的节点对称变型,它具有超立方体及其变型所没有的一些可嵌入性质。然而,目前增广立方体上边独立生成树的构造方法都是串行构造的。文中首先提出了一种并行算法,用于构造以AQn中的任意节点为根的2n-1棵树。然后证明算法得到的2n-1棵树是高度为n的边独立生成树,算法的时间复杂度为O(N),其中N表示增广立方体中的节点数。最后通过模拟实验来验证了所提方法的准确性。

关键词: 互连网络, 增广立方体, 边独立生成树, 并行算法, 高度

Abstract: In recent years,more and more research work is being conducted around interconnected networks.Independent spanning trees(ISTs) can be used in reliable transmission,parallel transmission,safe distribution of information,and parallel diagnosis of fault servers,and have attracted many researchers' attention.In network communication,such as one-to-all broadcasting,reliable communication,multi-node broadcasting,fault-tolerant broadcasting,secure message distribution,and IP fast rerouting,edge-independent spanning trees(EISTs) play a significant role.The augmented cube of n dimension AQn is a node-symmetric variation of the n-dimensional hypercube Qn,it has some embeddable properties that the hypercube and its variants do not have.However,the current EISTs construction methods in augmented cubes are serial construction.This paper first proposes parallel algorithms for constructing 2n-1 trees rooted at any node in AQn.Then,it proves that the 2n-1 trees obtained by algorithms are EISTs with the height n,and the algorithms' time complexity is O(N),where N equals the number of nodes in AQn.Finally,its accuracy is verified by simulation experiment.

Key words: Interconnection network, Augmented cube, Edge-independent spanning trees, Parallel algorithm, Height

中图分类号: 

  • TP311.12
[1]SAAD Y,SCHULTZ M H.Topological properties of hypercubes [J].IEEE Transactions on Computers,1988,37(7):867-872.
[2]CHOUDUM S A,SUNITHA V.Augmented cubes [J].Networks,2002,40(2):71-84.
[3]TSENG Y C,WANG S Y,HO C W.Efficient broadcasting inwormhole-routed multicomputers:A network-partitioning approach [J].IEEE Transactions on Parallel and Distributed Systems,1999,10(1):44-61.
[4]BAO F,FUNYU Y,HAMADA Y,et al.Reliable broadcasting and secure distributing in channel networks [J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,1998,E81-A(5):796-806.
[5]BAO F,IGARASHI Y,ÖHRING S R.Reliable broadcasting in product networks [J].Discrete Applied Mathematics,1998,83(1/2/3):3-20.
[6]CHEN Y S,CHIANG C Y,CHEN C Y.Multi-node broadcas-ting in all-ported 3-D wormhole-routed torus using an aggregation-then-distribution strategy [J].Journal of Systems Architecture,2004,50(9):575-589.
[7]ELHOURANI T,GOPALAN A,RAMASUBRAMANIAN S.IP fast rerouting for multi-link failures [J].IEEE/ACM Tran-sactions on Networking,2016,24(5):3014-3025.
[8]GOPALAN A,RAMASUBRAMANIAN S.IP fast reroutingand disjoint multipathrouting with three edge-independent spanning trees [J].IEEE/ACM Transactions on Networking,2016,24(3):1336-1349.
[9]PAN Z Y,CHENG B L,FAN J X,et al.A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks [J].Theoretical Computer Science,2023,942:33-46.
[10]ITAI A,RODEH M.The multi-tree approach to reliability in distributed networks [J].Information and Computation,1988,79:43-59.
[11]HSIEH S Y,WU C Y.Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults [J].Journal of Combinatorial Optimization,2010,19(1):16-30.
[12]ZEHAVI A,ITAI A.Three tree-paths [J].Journal of GraphTheory,1989,13(2):175-188.
[13]GOPALANA.On constructing three edge independent spanning trees[EB/OL].https://www.semanticscholar.org/paper/ON-CONSTRUCTING-THREE-EDGE-INDEPENDENT-SPAN-NING-Gopalan/b458a3f665cd41f1ec42fb3cebb5176c369a87ec?p2df.
[14]HOYER A,THOMAS R.Four edge-independent spanning trees [J].SIAM Journal on Mathematics,2018,32(1):233-248.
[15]ALI A,LEE O.Five edge-independent spanning trees [J].Procedia Computer Science,2023,223:223-230.
[16]WANG Y,SHEN H,FAN J X.Edge-independent spanningtrees in augmented cubes [J].Theoretical Computer Science,2017,670:23-32.
[17]KIM J S,LEE H O,CHENG E,et al.Independent spanningtrees on even networks [J].Information Sciences,2011,181(13):2892-2905.
[18]KIM J S,LEE H O,CHENG E,et al.Optimal independentspanning trees on odd graphs [J].The Journal of Supercompu-ting,2011,56(2):212-225.
[19]BAO F,OBOKATA K,IGARASHI Y,et al.Independent spanning trees of product graphs and their construction [J].IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences,1996,E79-A(11):1894-1903.
[20]TANG S M,YANG J S,WANG Y L,et al.Independent spanning trees on multidimensional torus networks [J].IEEE Transactions on Computers,2010,59(1):93-102.
[21]DONG Q,WANG X.How many triangles and quadrilaterals are there in an n-dimensional augmented cube [J].Theoretical Computer Science,2019,771:93-98.
[22]MANE S A,KANDEKAR S A,WAPHARE B N.Constructing spanning trees in augmented cubes [J].Journal of Parallel and Distributed Computing,2018,122:188-194.
[23]CHENG B L,FAN J X,LIN C K,et al.An improved algorithm to construct edge-independent spanning trees in augmented cubes [J].Discrete Applied Mathematics,2020,277:55-70.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!