基于内部不相交Steiner树的BCCC数据中心网络广义3-连通性精准解析及其可靠性意义

《Discrete Applied Mathematics》：The generalized 3-connectivity of BCCC data center networks

本文聚焦数据中心网络（DCNs）多节点协同通信中的可靠性度量难题。针对新兴的以服务器为中心的网络架构BCube连接交叉开关（BCCC），作者深入研究了其逻辑图中连接任意三个节点的内部不相交Steiner树的最大打包数量问题。通过精确的理论推导与构造，该工作最终确定了BCCC逻辑图的广义3-连通性（κ3）的精确值。这一成果突破了传统两点连通性理论的局限，为评估大规模数据中心在多节点故障场景下的网络可靠性与容错能力提供了关键的理论指标，具有重要的理论意义与应用价值。

　　

章节精要

术语与符号

考虑一个无向简单图G = (V(G), E(G))，对于任意节点v ∈ V(G)，v的开邻域定义为N_G(v) = {w ∈ V(G) | (v, w) ∈ E(G)}，v的度定义为d_G(v) = |N_G(v)|。我们用δ(G)表示G的最小度，定义为δ(G) = min{d_G(v) | v ∈ V(G)}。如果对于任意u ∈ V(G)都有d_G(u) = n，则称G是n-正则的。对于u, v ∈ V(G)，我们用d_G(u, v)表示它们之间的距离，即u和v之间最短路径的长度。图G的直径，记为d(G)，定义为max{d_G(u, v) | u, v ∈ V(G)}。

L-BCCC(n, k)的广义3-连通性

本节致力于研究L-BCCC(n, k)的广义3-连通性。根据定义2，L-BCCC(n, k)由(k+1)n^k个K_n的副本（我们称之为L-BCCC(n, k)的团）构成，记为C₁, C₂, …, C_(k+1)n^k。设S是L-BCCC(n, k)中任意三个不同节点的集合，通过考虑S中三个节点分布在不同的团中的所有可能情况，来确定κ₃(L-BCCC(n, k))。

引理 2

设x, y和z是L-BCCC(n, k)中的三个不同节点，后续……

结论

作为传统连通性的延伸，广义k-连通性能够衡量网络中连接任意k个节点的能力。它突破了两点间连通性的局限，对于评估网络的可靠性与容错性具有至关重要的意义。在本工作中，通过构建最大数量的内部不相交Steiner树，我们得出了BCCC逻辑图的广义3-连通性的精确结果。

利益冲突声明

作者声明，他们没有已知的可能影响本工作报告的竞争性经济利益或个人关系。

致谢

本工作部分得到了国家自然科学基金（编号：62172291、62272333和62572124）的支持。