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

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且每个无故障顶点至少有两个无故障邻居时找到任意两个不同的无故障顶点之间的一条无故障路径。