摘要
近年来,围绕互连网络的研究工作越来越多。其中独立生成树(Independent Spanning Trees,ISTs)可以应用于信息的可靠传输、并行传输、安全分发以及故障服务器的并行诊断中,因此受到了许多研究者的关注。在一对多广播、可靠通信、多节点广播、容错广播、安全消息分发、IP快速重路由等网络通信中,边独立生成树(Edge-Independent Spanning Trees,EISTs)发挥着重要作用。n维增广立方体AQ_(n)是n维超立方体Q_(n)的节点对称变型,它具有超立方体及其变型所没有的一些可嵌入性质。然而,目前增广立方体上边独立生成树的构造方法都是串行构造的。文中首先提出了一种并行算法,用于构造以AQ_(n)中的任意节点为根的2n-1棵树。然后证明算法得到的2n-1棵树是高度为n的边独立生成树,算法的时间复杂度为O(N),其中N表示增广立方体中的节点数。最后通过模拟实验来验证了所提方法的准确性。
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 AQ_(n) is a node-symmetric variation of the n-dimensional hypercube Q_(n),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 AQ_(n).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 AQ_(n).Finally,its accuracy is verified by simulation experiment.
作者
李夏晶
程宝雷
樊建席
王岩
李晓瑞
LI Xiajing;CHENG Baolei;FAN Jianxi;WANG Yan;LI Xiaorui(School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China;Provincial Key Laboratory for Computer Information Processing Technology,Soochow University,Suzhou,Jiangsu 215006,China)
出处
《计算机科学》
CSCD
北大核心
2024年第9期346-356,共11页
Computer Science
基金
国家自然科学基金(62272333,62172291)
江苏省教育厅未来网络科研基金资助(FNSRFP-2021-YB-39)
江苏高校优势学科建设工程资助项目。
关键词
互连网络
增广立方体
边独立生成树
并行算法
高度
Interconnection network
Augmented cube
Edge-independent spanning trees
Parallel algorithm
Height
