一类递归型数据中心网络上容错单播算法的研究  

A Fault-Tolerant Unicast Routing Algorithm fora Class of Recursive Data Center Networks

作　　者：伊雯雯[1] 张书奎[2] 王喜[1,2] 李文俊[1] YI Wenwen;ZHANG Shukui;WANG Xi;LI Wenjun(College of Software and Service Outsourcing,Suzhou Vocational Institute of Industrial Technology,Suzhou Jiangsu 215004,China;College of Computer Science and Technology,Soochow University,Suzhou Jiangsu 215006,China)

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

出　　处：《西南大学学报（自然科学版）》2021年第9期181-192,共12页Journal of Southwest University(Natural Science Edition)

基　　金：国家自然科学基金项目(61702351);江苏省自然科学基金青年项目(BK20180209);苏州工业职业技术学院科研课题(2020kyjj04).

摘　　要：提出了一类基于完全图的递归型数据中心网络(RDCN),与传统树形数据中心网络相比,RDCN具有更好的网络带宽和容错性能.证明了当k≥1,n≥3且σ∈{1,n-1}时,RDCN基于限制故障顶点集的限制连通度为2kσ+n-2,这一结果近于其连通度的2倍;提出了基于该情形的一种改进的容错单播算法XFRouting,证明了该算法的时间复杂度为O(┌log|F|┐k 3),并证明了在最坏情况下构造出其最长路径长度的上界.最后通过模拟仿真实验,验证了该算法在执行效率上优于广度优先搜索算法和深度优先搜索算法.The data center network is the main infrastructure supporting applications such as cloud services,supercomputing and social networks.The traditional tree-based data center network has some shortcomings,such as insufficient scalability and low fault tolerance.Based on completed graphs,this paper presents a kind of recursive data center network(RDCN).Compared with the traditional tree data center network,RDCN has better network bandwidth and fault-tolerant performance.It is proved that when k≥1,n≥3 andσ∈{1,n-1},the restricted connectivity of RDCN is 2kσ+n-2,which is almost twice the RDCN's traditional connectivity.We present an improved fault-tolerant unicastrouting algorithm(XFRouting)and prove thatthe time complexity of XFRouting is O(┌log|F|┐k 3),and furthermoreprove the maximal length of the path constructedby the algorithm in the worst case.Finally,a simulation experiment based on our algorithm is carried out,and the results show that the algorithm is better than the breadth first search algorithm and the depth first search algorithm.

关 键 词：递归型数据中心网络 连通度 限制连通度 容错单播路由算法 

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