The reliability of interconnection networks has been a significant attention for parallel distributed computing. In the design of interconnection networks, one of the most fundamental concerns is the topological reliability, which can be usually characterized by the functional subsystem of the underlying network topology. Typically, the largest connected component in a faulty network is referred as the functional subsystem without severe performance degradation, which greatly reflects the communication ability and efficiency of interprocessors in the surviving network. The paper first characterizes all possibilities of small components when deleting at most <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7128_Article_IEq1.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="86" /> </InlineMediaObject> <EquationSource Format="TEX">$n+4k-10$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>+</mo> <mn>4</mn> <mi>k</mi> <mo>-</mo> <mn>10</mn> </mrow> </math></EquationSource> </InlineEquation> vertices from the (n, k)-star network for <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7128_Article_IEq2.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">$n \ge 8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7128_Article_IEq3.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">$k \ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7128_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">$n-k \ge 4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mi>k</mi> <mo>≥</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>. Then, we present a minimum neighborhood search algorithm to find the minimum number of neighbors of small components in terms of interconnection rules of (n, k)-star networks. Finally, we implement simulation experiments and analyze its performance under different iterations. These findings contribute to the construction of highly reliable interconnection network systems.

An analysis on component reliability of (n, k)-star networks

期刊论文
发表日期：

2025年3月15日

查看全文

Zhihang Wang,
Jiafei Liu,
Chia-Wei Lee,
Jingli Wu,
Gaoshi Li

摘要

The reliability of interconnection networks has been a significant attention for parallel distributed computing. In the design of interconnection networks, one of the most fundamental concerns is the topological reliability, which can be usually characterized by the functional subsystem of the underlying network topology. Typically, the largest connected component in a faulty network is referred as the functional subsystem without severe performance degradation, which greatly reflects the communication ability and efficiency of interprocessors in the surviving network. The paper first characterizes all possibilities of small components when deleting at most $n+4k-10$ $n + 4 k - 10$ vertices from the (n, k)-star network for $n \ge 8$ $n \geq 8$ , $k \ge 4$ $k \geq 4$ , $n-k \ge 4$ $n - k \geq 4$ . Then, we present a minimum neighborhood search algorithm to find the minimum number of neighbors of small components in terms of interconnection rules of (n, k)-star networks. Finally, we implement simulation experiments and analyze its performance under different iterations. These findings contribute to the construction of highly reliable interconnection network systems.