k元n方体网络故障下子网络可靠性研究

本文主要探讨了k元n方体网络的可靠性问题，这是一种在设计大规模并行与分布式处理系统中广泛应用的互连网络结构。k元n方体以其对称性、正则性和优良的通信性能而受到青睐，它包括多种知名网络如超立方、环形网络和CrayT3D等的子类。在实际应用中，如iWarp、J-machine等系统已采用k元n方体作为基础网络拓扑。 论文的核心关注点在于确定破坏k元n方体中的所有子立方Qkn-m所需的最少故障集F的基数，记为f*(n,m)。对于特定的情况，当m=1时，即破坏最小的子立方时，证明了f*(n,1)等于k+1；当m=n-1时，即破坏最大的子立方，f*(n,n-1)等于kn-1-1和kn-1-2之间的界限。同时，作者给出了f*(n,m)的上下界，上界为Cm-1n-1km到Cm-1n-2km-1，下界为km，这里C表示某个具体的系数。通过示例，证明了这个上界是最优的，表明破坏所有子立方所需的最小故障数是有限且可计算的。 可靠性是网络设计中的关键因素，特别是对于大规模多处理机系统，因为任何故障都可能导致系统性能下降或完全瘫痪。研究k元n方体网络的可靠性有助于理解其在实际应用中的鲁棒性，从而指导系统的容错设计和优化。通过了解最小故障集的规模，可以评估在面对故障时网络能够保持多少功能性子结构，这对于网络设计者来说是极其重要的决策依据。 这篇论文不仅提供了理论分析，还展示了如何通过实证研究来估计k元n方体网络在遭遇故障时的结构保留能力，这在现代并行计算领域具有很高的实用价值。