基于l-额外边连通度的折叠Petersen网络容错性分析

《Applied Mathematics and Computation》：Fault tolerability analysis of folded Petersen networks on the basis of l-extra edge-connectivity

　　

对多处理器系统的故障容错性进行分析，不仅对系统设计至关重要，对系统维护也具有重要意义。l-额外（边）连通度作为传统（边）连通度的广义形式，能够实现对多处理器系统故障容错性更为精确的评估。对于众多重要的多处理器体系结构而言，计算l-额外（边）连通度，尤其是较大l值对应的l-额外（边）连通度，仍是尚未解决的研究问题。n维折叠Petersen网络P_n已成为多处理器系统拓扑结构的主要候选方案之一。本文研究了P_n的l-额外边连通度λ_l(P_n)，其中整数l∈[1,5·10^n?1]。更具体地，研究人员证明了对于区间[1,5·10^n?1]中约三分之二的整数l（其中n≥2），λ_l(P_n)呈现出集中现象（concentration phenomenon）；而对于整数l∈[1,2ⁿ⁺¹]∪[5·2ⁿ,6·2ⁿ]，则表现出λ_l-最优性质。此外，折叠Petersen网络的集中性质可推广至折叠Petersen立方体。

## 研究背景与问题提出

随着技术的加速发展，高速多处理器系统和云计算已被广泛应用于大规模数据分析和并行/分布式计算领域。随着多处理器系统规模和复杂度的不断增长，处理器故障和链路故障变得不可避免。因此，评估系统的故障容错性——即系统在多个组件失效情况下维持高效运行的能力——成为其设计中的关键研究方向。为便于分析，多处理器系统通常被表示为一个连通图，其中处理器作为顶点、通信链路作为边。该图G被称为系统的互连网络（interconnection network），其边连通度（edge-connectivity）记为λ(G)，定义为使G断开所需删除的最少边数。边连通度是评估多处理器系统故障容错性和可靠性的关键度量指标，λ(G)值越高直接对应着更高的系统可靠性。

然而，边连通度这一参数存在两个主要缺陷。其一，它无法区分具有相同边连通度但故障容错行为显著不同的图。其二，更为关键的是，边连通度是一种最坏情况度量。正如Xu所解释，由于此类极端故障在实践中较为罕见，依赖该度量会导致对网络真实韧性的显著低估。为克服这些局限性，学者们在条件边连通度（conditional edge-connectivity）框架下提出了若干精细化概念。其中，由Fàbrega和Fiol引入的额外边连通度（extra edge-connectivity）提供了更为细粒度的度量。对于正整数l，图G的一个l-额外边割（l-extra edge-cut）是指一个边集，其移除使G断开，且每个结果连通分支至少包含l个顶点。l-额外边连通度记为λ_l(G)，定义为此类割的最小大小。值得注意的是，λ₁(G)与标准边连通度λ(G)一致。

### λ_l-最优性定义

对于非空真子集Y?V(G)，用[Y,Y]表示Y与其补集Y之间的所有边构成的边割。定义ξ_t(G)=min{|[Y,Y]|, |Y|=t≤?n/2?, G[Y]与G[Y]连通}，其中n=|V(G)|。若图G满足λ_l(G)=ξ_l(G)，则称G为λ_l-最优的；否则，称其非λ_l-最优。

## 现有研究进展与折叠Petersen网络的提出

已有大量研究针对不同互连网络的λ_l进行了探讨，包括超立方体Q_n、折叠超立方体FQ_n、增强立方体AQ_n、3-元n-立方体Q_n³等。例如，Li和Yang确定了1≤l≤2^?n/2?时λ_l(Q_n)的值；Zhang等首先考虑了折叠超立方体FQ_n在1≤l≤2^?n/2?+1范围内的λ_l(FQ_n)，并进一步设计了O(log2N)时间算法以计算所有1≤l≤2^n?1的情况；Xu等为增强立方体AQ_n提供了覆盖1≤l≤2^n?1的O(log2N)算法；对于3-元n-立方体Q_n³，已建立了1≤l≤(3ⁿ?1)/2的结果。

在众多重要网络中，超立方体Q_n因其正则性、递归结构、高性能路由与广播方案、顶点对称性和边对称性等优良性质，成为互连网络中极为流行的拓扑结构，并已被应用于Intel iPSC/2和Connection Machine CM-2等商业多计算机系统。尽管如此，新型网络结构仍在不断被提出和研究，以期在实用性、拓扑结构或性能特性方面有所增强。

1985年，Chartrand和Wilson首次引入了现称为Petersen图的图。该图是十个顶点上图论中最著名且最重要的图之一。虽然3维超立方体Q₃具有8个顶点、度为3、直径为3，但Petersen图在具有10个顶点的同时，实现了更小的直径2且保持相同的顶点度3。此后，?hring和Das提出了折叠Petersen网络（folded Petersen networks），这是一类基于Petersen图作为基本模块的新型互连拓扑族。

对于多处理器体系结构，n维折叠Petersen网络P_n被证明是一种引人注目的候选拓扑，非常适应并行计算的需求。研究表明，在直径、度、连通度、成本和封装密度等标准参数方面，P_n表现出优于同等规模超立方体及其他网络的性能。

## 主要研究内容与技术方法

研究人员开展了关于折叠Petersen网络P_n的l-额外边连通度λ_l(P_n)的系统研究。研究所用的主要关键技术方法包括：

**图论基本工具与递归分析方法**：基于P_n的递归定义，利用其作为Petersen图P的n次笛卡尔积的结构特性，建立分析框架。研究人员定义了辅助函数g_n(l)=3nl?ex_l(P_n)，其中ex_l(P_n)为外部边数，该函数在分析中起核心作用。

**策略性子图分析方法**：通过对P_n中特定规模子集的边边界进行精细分析，结合Petersen图的性质，确定不同参数区间内λ_l(P_n)的精确值。特别是对子集边界的组合优化分析，为证明集中现象提供了关键工具。

**算法设计方法**：针对λ_l的高度振荡特性，研究人员开发了高效的O(n)时间算法，用于计算l∈[1,2ⁿ⁺¹]∪[5·2ⁿ,6·2ⁿ]范围内所有整数对应的λ_l(P_n)值。

**笛卡尔积推广方法**：将P_n的结果推广至折叠Petersen立方体P_mⁿ=P_n×Q_m，利用超立方体Q_m的性质与引理4.1中给出的H_n,m(s)表达式，建立了一般性结论。

## 研究结果

### λ_l(P_n)的集中现象与λ_l-最优性质

研究人员通过策略性分析子集的边边界，证明了对于n≥2，约66%的整数l∈[1,5·10^n?1]，λ_l(P_n)呈现出集中现象。具体而言，在以下区间内表现为常数值：

- 当2.4·10^n?1≤l≤5·10^n?1时，λ_l(P_n)=5·10^n?1；
- 当1.5·10^n?1≤l≤2·10^n?1时，λ_l(P_n)=4·10^n?1；
- 当1.3·10^n?1≤l≤1.4·10^n?1时，λ_l(P_n)=3.8·10^n?1；
- 当0.9·10^n?1≤l≤10^n?1时，λ_l(P_n)=3·10^n?1。

对于正整数l∈[1,2ⁿ⁺¹]∪[5·2ⁿ,6·2ⁿ]，λ_l(P_n)表现出λ_l-最优性质，即λ_l(P_n)=ξ_l(P_n)。这一性质的确立依赖于对P_n递归结构中子图间边割的精确计算。

### 应用实例与模拟验证

研究人员通过基于实际案例研究的模拟，展示了理论发现的应用性。由于n维折叠Petersen网络具有结构正则性、对称性（顶点和边对称）、递归构造、低延迟和易于实现等优良品质，它在学术界引发了研究兴趣，并可作为并行和分布式多处理器系统底层架构的候选拓扑。该理论研究所提供的定量分析为系统设计者评估网络可靠性提供了重要依据。

### 折叠Petersen立方体的推广

研究人员将P_n的集中性质推广至折叠Petersen立方体P_mⁿ。通过引理4.1给出的H_n,m(s)表达式，其中s=2^m·t+k（0≤k<2^m），结合定理3.2的结果，证明了对于2.4·10ⁿ·2^m≤l≤5·10ⁿ·2^m，有λ_l(P_mⁿ)=5·10^n?1·2^m。这一推广显著扩展了理论结果的适用范围。

## 讨论与结论

λ_l是评估多处理器系统可靠性的关键度量指标。本文主要研究了P_n的λ_l。对于n≥2，约66%的整数l∈[1,5·10^n?1]所对应的λ_l(P_n)表现出集中现象；而正整数l∈[1,2ⁿ⁺¹]∪[5·2ⁿ,6·2ⁿ]所对应的λ_l(P_n)则表现出λ_l-最优性质。鉴于λ_l的高度振荡特性，研究人员开发了高效的O(n)时间算法，用于计算l∈[1,2ⁿ⁺¹]∪[5·2ⁿ,6·2ⁿ]范围内所有l对应的λ_l(P_n)值。未来工作将解决其余参数区间内的λ_l(P_n)确定问题。

该研究的重要意义在于：首先，为折叠Petersen网络这一具有优良拓扑性质的候选多处理器架构提供了精确的可靠性量化分析工具；其次，所揭示的集中现象表明，在较大参数范围内，网络的故障容错性可由其规模简洁地表征，这对于大规模系统的可靠性评估具有实际价值；最后，研究成果向折叠Petersen立方体的成功推广，展现了该理论框架的广泛适用性。论文发表在《Applied Mathematics and Computation》。