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

来源：计算机应用与软件杂志2024年第1期北京时间：

作者：伊雯雯，王喜，张书奎, ,

摘要：数据中心网络的研究是近几年兴起的热点。与传统的树型数据中心网络相比，递归型数据中心网络具有更好的容错性和可扩展性。部署于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中任意两点间构造出路径长度的上界。通过模拟仿真实验，验证了该算法在执行效率上优于广度优先和深度优先搜索算法，且算法具有较好的容错性。

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