BCube在2-限制连通度下的容错路由算法  

Fault-tolerant Routing Algorithm in BCube Under 2-restricted Connectivity

作　　者：易怡 樊建席[1] 王岩[1] 刘钊[1] 董辉 YI Yi;FAN Jian-xi;WANG Yan;LIU Zhao;DONG Hui(School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China)

机构地区：[1]苏州大学计算机科学与技术学院,江苏苏州215006

出　　处：《计算机科学》2021年第6期253-260,共8页Computer Science

基　　金：国家自然科学基金联合基金(U1905211);国家自然科学基金(61972272);江苏高校优势学科建设工程资助。

摘　　要：BCube是具有良好性能的数据中心网络。相比传统的树形数据中心网络,BCube在扩展和容错性能方面都表现出很大的优势。目前,对于BCube的研究可以归结为对其逻辑图BC_(n,k)(广义超立方体的一种特例)的研究,其中交换机被视为透明设备。在实际应用中,随着网络规模的不断增加,顶点发生故障已经成为一种常态。因此,研究网络的容错路由很有意义。目前,有不少关于BC_(n,k)容错路由的研究,但其2-限制连通度下的容错路由目前还没有被研究。在提出容错路由算法之前,首先证明了BC_(n,k)的2-限制连通度为3(k+1)(n-1)-2n,其中k≥3且n≥3。然后在此基础上提出了一个时间复杂度为O(κ(BC_(n,k))~3)的容错路由算法,其中κ(BC_(n,k))=(k+1)(n-1)是BC_(n,k)的连通度。该算法可以在故障顶点个数小于3(k+1)(n-1)-2n且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径。BCube is a data center network with good performance.Compared to traditional tree-shaped data center network,BCube has not only higher fault-tolerance performance but also superior scalability.Currently,the research on BCube can be reduced to logical structure(a special generalized hypercube),in which the switches are regarded as transparent devices.In actual application,with the continuous increase of network scale,vertex failure has become inevitable.Therefore,it is meaningful to study the fault-tolerant routing of the network.At present,there is some research on fault-tolerant routing of BC n,k.However,the fault-tolerant routing of BC n,k under the 2-restricted connectivity has not been studied yet.Before proposing the algorithm,the 2-restricted connectivity of BC n,k is firstly proved which is 3(k+1)(n-1)-2n for k≥3 and n≥3.Then a fault-tolerant routing algorithm with a time complexity of O(κ(BC n,k)3)is proposed whereκ(BC n,k)=(k+1)(n-1)denotes the connectivity of BC n,k.The proposed algorithm can find a fault-free path between any two distinct fault-free vertices when the number of faulty vertices is less than 3(k+1)(n-1)-2n and every fault-free vertex has at least two fault-free neighbors.

关 键 词：数据中心网络 BCube 2-限制连通度 容错路由 时间复杂度 

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