递归型数据中心网络上g-额外连通度及容错单播算法研究  

g -EXTRA CONNECTIVITY AND FAULT-TOLERANT UNICAST ALGORITHMOF RECURSIVE DATA CENTER NETWORKS

作　　者：伊雯雯[1] 王喜[1,2] 张书奎[2] Yi Wenwen;Wang Xi;Zhang Shukui(School of Software and Service Outsourcing,Suzhou Institute of Industrial Technology,Suzhou 215004,Jiangsu,China;School of Computer Science and Technology,Soochow University,Suzhou 215006,Jiangsu,China)

机构地区：[1]苏州工业职业技术学院软件与服务外包学院,江苏苏州215004 [2]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机应用与软件》2024年第1期261-268,290,共9页Computer Applications and Software

基　　金：国家自然科学基金项目(61702351);江苏省高校自然科学基金项目(17KJB520036);江苏高校“青蓝工程”资助项目。

摘　　要：数据中心网络的研究是近几年兴起的热点。与传统的树型数据中心网络相比,递归型数据中心网络具有更好的容错性和可扩展性。部署于n-口交换机上的k-维递归型完全图网络可以表示为Xk,n,σ表示图中任意顶点与同维度其他子图相连接的边数。在实际情况中,网络的额外连通度相较于传统的连通度能够更准确地衡量一个网络的容错性。证明当k≥3,n≥3,σ∈{1,n-1}且0≤g≤2时,Xk,n的g-额外连通度为(g+1)(kσ-1)+n,这一结果接近于其连通度的g+1倍。进一步,提出基于该情形下的容错单播算法,并证明了该算法的时间复杂度和在最坏情况下Xk,n中任意两点间构造出路径长度的上界。通过模拟仿真实验,验证了该算法在执行效率上优于广度优先和深度优先搜索算法,且算法具有较好的容错性。The research of data center network is a hot spot that has emerged in recent years.Compared with the traditional tree data center network,the recursive data center network has better fault tolerance and scalability.The k-dimensional recursive complete graph network deployed on the n-port switch can be expressed as X k,n.σrepresents the number of edges connecting any vertex in the graph with other sub graphs of the same dimension.In practical situations,the extra connectivity of the network can measure the network s fault tolerance more accurately than traditional connectivity.This paper proves that when k≥3,n≥3,σ∈{1,n-1}and 0≤g≤2,the extra connectivity of X k,n is(g+1)(kσ-1)+n,which is close to g+1 times of its connectivity.Furthermore,we propose a fault-tolerant unicast algorithm based on this case.In this paper,it is proved that the time complexity of the algorithm and the maximal length of the path constructed by the algorithm between any two nodes in the worst case.Through simulation experiments,it is proved that the algorithm is superior to the breadth-first search and depth-first search algorithms in execution efficiency,and the algorithm has good fault tolerance performance.

关 键 词：递归型数据中心网络 容错性 额外连通度 容错单播算法 算法分析 

分 类 号：TP391.3[自动化与计算机技术—计算机应用技术]