Subnetwork reliability is a key practical indicator for evaluating the fault tolerance of multiprocessor interconnection networks. The (n, k)-star networks <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$S_{n,k}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> is an attractive generalized interconnection network. Existing studies on subnetwork reliability of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$S_{n,k}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> mainly focus on <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$(n-1, k-1)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>-</mo> <mn>1</mn> <mo>,</mo> <mi>k</mi> <mo>-</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-dimensional subnetworks, while the reliability evaluation for general <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$S_{n-m,k-m}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>-</mo> <mi>m</mi> <mo>,</mo> <mi>k</mi> <mo>-</mo> <mi>m</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> subnetworks with arbitrary <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$m\ge 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> still remains insufficient, restricting the practical application of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$S_{n,k}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> in multiprocessor systems. To fill this research gap, this paper investigates the subnetwork reliability <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$R_{n,k}^m(p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>R</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> <mi>m</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, defined as the probability that <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$S_{n,k}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> contains at least one fault-free <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$S_{n-m,k-m}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>-</mo> <mi>m</mi> <mo>,</mo> <mi>k</mi> <mo>-</mo> <mi>m</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> subnetwork under independent vertex failure model. We derive the upper and lower bounds of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$R_{n,k}^m(p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>R</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> <mi>m</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> by analyzing the intersection characteristics of subnetworks, and develop a heuristic algorithm based on Monte Carlo simulation to estimate the reliability. When the gap between the two bounds is sufficiently small, the Monte Carlo simulation result can well approximate the exact subnetworks reliability of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$R_{n,k}^m(p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>R</mi> <mrow> <mi>n</mi> <mo>,</mo> <mi>k</mi> </mrow> <mi>m</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, which provides an efficient approximate evaluation scheme without exhausting complex intersection enumeration.

Subnetwork reliability of the (n, k)-star networks under probabilistic fault model

期刊论文
发表日期：

2026年7月18日

查看全文

Hao Li,
Eminjan Sabir

摘要

Subnetwork reliability is a key practical indicator for evaluating the fault tolerance of multiprocessor interconnection networks. The (n, k)-star networks $S_{n,k}$ $S_{n, k}$ is an attractive generalized interconnection network. Existing studies on subnetwork reliability of $S_{n,k}$ $S_{n, k}$ mainly focus on $(n-1, k-1)$ $(n - 1, k - 1)$ -dimensional subnetworks, while the reliability evaluation for general $S_{n-m,k-m}$ $S_{n - m, k - m}$ subnetworks with arbitrary $m\ge 1$ $m \geq 1$ still remains insufficient, restricting the practical application of $S_{n,k}$ $S_{n, k}$ in multiprocessor systems. To fill this research gap, this paper investigates the subnetwork reliability $R_{n,k}^m(p)$ $R_{n, k}^{m} (p)$ , defined as the probability that $S_{n,k}$ $S_{n, k}$ contains at least one fault-free $S_{n-m,k-m}$ $S_{n - m, k - m}$ subnetwork under independent vertex failure model. We derive the upper and lower bounds of $R_{n,k}^m(p)$ $R_{n, k}^{m} (p)$ by analyzing the intersection characteristics of subnetworks, and develop a heuristic algorithm based on Monte Carlo simulation to estimate the reliability. When the gap between the two bounds is sufficiently small, the Monte Carlo simulation result can well approximate the exact subnetworks reliability of $R_{n,k}^m(p)$ $R_{n, k}^{m} (p)$ , which provides an efficient approximate evaluation scheme without exhausting complex intersection enumeration.