计算机科学

计算机科学 ›› 2022, Vol. 49 ›› Issue (7): 287-296.doi: 10.11896/jsjkx.210500170

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

数据中心网络BCDC上的顶点独立生成树构造算法

潘志勇, 程宝雷, 樊建席, 卞庆荣   

  1. 苏州大学计算机科学与技术学院 江苏 苏州215006
  • 收稿日期:2021-05-25 修回日期:2021-09-15 出版日期:2022-07-15 发布日期:2022-07-12
  • 通讯作者: 程宝雷(chengbaolei@suda.edu.cn)
  • 作者简介:(20205227070@stu.suda.edu.cn)
  • 基金资助:
    国家自然科学基金(U1905211,62172291,61572337);江苏省高等学校自然科学重大项目(18KJA520009);江苏高校优势学科建设工程资助项目

Algorithm to Construct Node-independent Spanning Trees in Data Center Network BCDC

PAN Zhi-yong, CHENG Bao-lei, FAN Jian-xi, BIAN Qing-rong   

  1. School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China
  • Received:2021-05-25 Revised:2021-09-15 Online:2022-07-15 Published:2022-07-12
  • About author:PAN Zhi-yong,born in 1998,postgra-duate.His main research interests include parallel and distributed systems and graph algorithms.
    CHENG Bao-lei,born in 1979,associate professor.His main research interests include parallel and distributed systems,algorithms,interconnection architectures and software testing.
  • Supported by:
    National Natural Science Foundation of China(U1905211,62172291,61572337),Natural Science Foundation of Jiangsu Higher Education Institutions of China(18KJA520009) and Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions.

PDF (PC)

389

摘要： 作为云计算技术的基础,数据中心网络的通信性能成为了近年来的研究热点。独立生成树(Independent Spanning Trees,ISTs)作为数据中心网络中常见的基础结构,因其在可靠通信、容错广播以及安全分发方面的应用受到了研究者的广泛关注,在诸多特殊的网络上都取得了显著的成果。但是,学者们对在线图中独立生成树的研究却很少。BCDC是由Wang等于2018年提出的一个新的以服务器为中心的数据中心网络,其逻辑图是交叉立方体的线图且为2n－2正则图。文中给出了BCDC上独立生成树的构造算法,首先利用一种并行算法在交叉立方体中构造出2n－2棵树,然后将这些树按照一定规则连接并通过特定的转换方法将其转变为BCDC中2n－2棵相互独立的树,最后将BCDC中的剩余顶点通过一个时间复杂度为O(N)(其中N表示BCDC的顶点数)的高效算法挂接到树上,从而构造出BCDC上的以顶点[r,N(r,2)]为根的2n－2棵独立生成树,其中顶点r为交叉立方体CQn上的任意一个顶点。

关键词: BCDC, 独立生成树, 交叉立方体, 数据中心网络, 线图

Abstract: As the foundation of cloud computing technology,the communication performance of data center networks has become a research hotspot in recent years.And as an important infrastructure of data center networks,independent spanning trees(ISTs) attract much attention of researchers because of their application in reliable communication,fault-tolerant broadcasting and secure message distribution,and remarkable results have been obtained on some special networks.But only a few results are reported on the line graphs.A new server-centric network called BCDC was proposed in 2018.Its logic graph is the line graph of crossed cube and is (2n－2)-regular.In this paper,an algorithm is proposed to construct the independent spanning trees on BCDC.Firstly,2n－2 trees are constructed by a parallel algorithm on crossed cube.Then,connect these trees by a special rule,and transfer these trees into 2n－2 independent trees on BCDC through a way of transformation.Finally,the rest nodes of BCDC are connected to these trees by an algorithm which is proposed with time complexity O(N),where N is the number of nodes on BCDC.As a result,we will obtain 2n－2 ISTs rooted at node [ r,N(r,2)] on BCDC,where r is an arbitrary node in n dimensional crossed cube CQn.

Key words: BCDC, Crossed cube, Data center networks, Independent spanning trees, Line graph

中图分类号: 

  • TP311.12
[1]ZUO P,SHU Y A.Dynamic Multi-Path Load Balancing Method Based on Feedforward Neural Network in DCN[J].Computer Engineering,2021,47(9):113-119.
[2]ZHOU X,LU D X,HUO J H,et al.Performance analysis ofdata center optical interconnection based on single-side band modulation technologies [J].Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition),2020,32(5):707-718.
[3]LI D,WU J.On data center network architectures for interconnecting dual-port servers [J].IEEE Trans on Computers,2015,64(11):3210-3222.
[4]WANG X,FAN J X,LIN C K,et al.A high-performance,server-centric data center network [J].Journal of Computer Science and Technology,2018,33(2):38-44.
[5]ZHANG Z,DENG Y H,MIN G Y,et al.HSDC:A highly scalable data center network architecture for greater incremental scalability[J].IEEE Transactions on Parallel and Distributed Systems,2019,30(5):1105-1119.
[6]ITAI A,RODEH M.The multi-tree approach to reliability in distributed networks [J].Information and Computation,1988,79:43-59.
[7]ZEHAVI A,ITAI A.Three tree-paths [J].Journal of GraphTheory,1989,13(2):175-188.
[8]HUCK A.Independent trees in planar graphs [J].Graphs and Combinatorics,1999,15(1):29-77.
[9]OBOKATA K,IWASAKI Y,BAO F,et al.Independent span-ning trees of product graphs and their construction [J].IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences,1996,E79-A(11):1894-1903.
[10]KIM J S,LEE H O,CHENG E,et al.Independent spanningtrees on even networks [J].Information Sciences,2011,181(13):2892-2905.
[11]KIM J S,LEE H O,CHENG E,et al.Optimal independentspanning trees on odd graphs [J].Journal of Supercomputing,2011,56(2):212-225.
[12]CHENG B L,FAN J X,JIA X H,et al.Independent spanning trees in crossed cubes [J].Information Sciences,2013,233(1):276-289.
[13]WANG Y,FAN J X,ZHOU G,et al.Independent spanningtrees on twisted cubes [J].Journal of Parallel and Distributed Computing,2012,72(1):58-69.
[14]CHENG B L,FAN J X,JIA X H.Dimensional-permutation-based independent span- ning trees in bijective connection networks [J].IEEE Transactions on Parallel and Distributed Systems,2015,26(1):45-53.
[15]LI H,HE W H,YANG W H,et al.A note on edge-disjointHamilton cycles in line graphs [J].Graphs and Combinatorics,2016,32:741-744.
[16]HASUNUMA T.Structural properties of subdivided-line graphs [J].Journal of Discrete Algorithms,2015,31:69-86.
[17]HARVEY D J,WOOD D R.Treewidth of the line graph of a complete graph [J].Journal of Graph Theory,2015,79(1):48-54.
[18]TIAN T,XIONG L M.Traceability on 2-connected line graphs [J].Applied Mathematics and Computation,2018,321:1339-1351.
[19]BONOMO F, DURÁN G, SAFE M D,et al.Clique-perfectness of complements of line graphs [J].Electronic Notes in Discrete Mathematics,2011,37:327-332.
[20]CHENG B L,FAN J X,JIA X H,et al.Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes [J].Journal of Parallel and Distributed Computing,2013,73(5):641-652.
[21]YU X,WU,WANG G J.A Parallel Routing Algorithm forCrossed Cube Networks[J].Computer Engineering,2007,33(3):12-14.
[22]EFE K.The crossed cube architecture for parallel computation [J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-524.
[23]EFE K.A variation on the hypercube with lower diameter [J].IEEE Transactions on Computers,1991,40(11):1312-1316.
[24]CHARTRAND G,STEWART M J.The connectivity of line-graphs [J].Mathematische Annalen,1969,182(3):170-174.
[25]CHENG B L,FAN J X,LI X Y,et al.Towards the Independent Spanning Trees in the Line Graphs of Interconnection Networks[C]//International Conference on Algorithms & Architectures for Parallel Processing.Cham,:Springer,2018:342-354.
[1] 易怡, 樊建席, 王岩, 刘钊, 董辉.
BCube在2-限制连通度下的容错路由算法
Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity
计算机科学, 2021, 48(6): 253-260. https://doi.org/10.11896/jsjkx.200900203
[2] 张登科, 王兴伟, 何强, 曾荣飞, 易波.
可重构数据中心网络研究综述
State-of-the-art Survey on Reconfigurable Data Center Networks
计算机科学, 2021, 48(3): 246-258. https://doi.org/10.11896/jsjkx.201100038
[3] 金勇, 刘亦星, 王欣欣.
基于SDN的数据中心网络多路径流量调度算法
SDN-based Multipath Traffic Scheduling Algorithm for Data Center Network
计算机科学, 2019, 46(6): 90-94. https://doi.org/10.11896/j.issn.1002-137X.2019.06.012
[4] 樊自甫,李书,张丹.
基于流量调度的SDN数据中心网络拥塞控制算法
Traffic Scheduling Based Congestion Control Algorithm for Data Center Network on Software Defined Network
计算机科学, 2017, 44(Z6): 266-269. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.061
[5] 师海忠,师越.
互连网络的m层二进制图模型
M-layers Binary Graph Model for Interconnection Networks
计算机科学, 2017, 44(Z11): 308-311. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.065
[6] 刘军,周明全,耿国华,沈映泉.
基于视觉曲率估算的文物线图绘制方法
Drawing Method of Cultural Relics Line Drawing Based on Visual Curvature Estimation
计算机科学, 2017, 44(Z11): 244-250. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.051
[7] 林政宽,赵源,樊建席,程宝雷.
基于顶点度数的完全独立生成树研究
Research on Completely Independent Spanning Trees Based on Degree of Vertices
计算机科学, 2017, 44(6): 94-96. https://doi.org/10.11896/j.issn.1002-137X.2017.06.016
[8] 乔焰,焦俊,饶元.
基于数据中心流量特征的端到端流量估计算法
Traffic Estimation for Data Center Network Based on Traffic Characteristics
计算机科学, 2017, 44(2): 171-175. https://doi.org/10.11896/j.issn.1002-137X.2017.02.026
[9] 肖春宝,冯大政.
基于K近邻一致性的特征匹配内点选择算法
Inlier Selection Algorithm for Feature Matching Based on K Nearest Neighbor Consistency
计算机科学, 2016, 43(1): 290-293. https://doi.org/10.11896/j.issn.1002-137X.2016.01.062
[10] 沈鹍霄,兰义华,卢玉领,尚耐丽,马晓普.
乳腺辅助诊断系统中可疑肿块分割方法研究
Research on Segmentation Methods in Breast Computer-aided Detection
计算机科学, 2015, 42(Z11): 195-198.
[11] 张赣,梁伟,毕经平,邵定宏.
基于支点的数据中心网络地址快速自动配置方法研究
PFAC:Pivot-based Fast Automatic Configuration for Data Center Networks
计算机科学, 2013, 40(5): 62-66.
[12] 冷飞,徐进华,栾仕喜.
DCNS:一种高可用性的数据中心网络
DCNS:A High Available Data Center Network Topology
计算机科学, 2013, 40(12): 177-181.
[13] 尹栋,慕德俊,戴冠中.
一种以服务器为通信节点的数据中心网络设计
Research on Server Centric Data Center Network Design
计算机科学, 2012, 39(3): 110-112.
[14] 杨振亚,陈裕泉,潘敏.
基于Curvelet变换的X射线图像增强
X-ray Image Enhancement Based on Curvelet Transform
计算机科学, 2010, 37(3): 275-277.
[15] 孙建勇 金翔宇 等.
一种快速在线图形识别与规整化方法

计算机科学, 2003, 30(2): 172-176.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发