The interconnection network is a fundamental technique for realizing high-performance computing and massive data communication. Fault tolerance of high-performance computing systems is a critical issue in ensuring network reliability, and connectivity is one of the most significant indicators for assessing fault tolerance of the system. However, the existing conditional connectivity measures cannot reveal the fault tolerance of a network well enough to balance the size of each component and the number of components of the remaining network in the presence of failing units. In this work, we introduce a novel connectivity measure for star graph, h-extra r-component connectivity, denoted by <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq1.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="93" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ECC}_{r}^{h}(\text{{Star}}_{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mtext>ECC</mtext> <mrow> <mi>r</mi> </mrow> <mi>h</mi> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, for the reliability of n-dimension star network <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{{Star}}_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> by taking into account of the size and number of disconnected components in a faulty network. Then, we determine the 1-extra 3-component connectivity and 1-extra 4-component connectivity of <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="92" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{{Star}}_{n}(n\ge 5)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>≥</mo> <mn>5</mn> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> to be <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq4.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="169" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ECC}_{3}^{1}(\text{{Star}}_{n})=4n-10$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mtext>ECC</mtext> <mrow> <mn>3</mn> </mrow> <mn>1</mn> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>4</mn> <mi>n</mi> <mo>-</mo> <mn>10</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq5.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="169" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{ECC}_{4}^{1}(\text{{Star}}_{n})=6n-18$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mtext>ECC</mtext> <mrow> <mn>4</mn> </mrow> <mn>1</mn> </msubsup> <mrow> <mo stretchy="false">(</mo> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>6</mn> <mi>n</mi> <mo>-</mo> <mn>18</mn> </mrow> </math></EquationSource> </InlineEquation>, respectively. Furthermore, we design an algorithm based on random iterations to obtain edge minimal cuts (RIEMC), aiming at solving the problem of the 1-extra r-component connectivity of G. Simulation results demonstrate that 1-extra r-component connectivity can accurately and effectively reflect fault tolerance and reliability of <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11227_2025_7272_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="40" /> </InlineMediaObject> <EquationSource Format="TEX">$\text{{Star}}_{n}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mtext>Star</mtext> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> than the state-of-the-art connectivity measures.

A novel fault-tolerant technique for star graph-based interconnection networks

期刊论文
发表日期：

2025年5月3日

查看全文

Wenfei Liu,
Jiafei Liu,
Jou-Ming Chang,
Jingli Wu,
Qi Wang

摘要

The interconnection network is a fundamental technique for realizing high-performance computing and massive data communication. Fault tolerance of high-performance computing systems is a critical issue in ensuring network reliability, and connectivity is one of the most significant indicators for assessing fault tolerance of the system. However, the existing conditional connectivity measures cannot reveal the fault tolerance of a network well enough to balance the size of each component and the number of components of the remaining network in the presence of failing units. In this work, we introduce a novel connectivity measure for star graph, h-extra r-component connectivity, denoted by $\text{ECC}_{r}^{h}(\text{{Star}}_{n})$ ${ECC}_{r}^{h} ({Star}_{n})$ , for the reliability of n-dimension star network $\text{{Star}}_{n}$ ${Star}_{n}$ by taking into account of the size and number of disconnected components in a faulty network. Then, we determine the 1-extra 3-component connectivity and 1-extra 4-component connectivity of $\text{{Star}}_{n}(n\ge 5)$ ${Star}_{n} (n \geq 5)$ to be $\text{ECC}_{3}^{1}(\text{{Star}}_{n})=4n-10$ ${ECC}_{3}^{1} ({Star}_{n}) = 4 n - 10$ and $\text{ECC}_{4}^{1}(\text{{Star}}_{n})=6n-18$ ${ECC}_{4}^{1} ({Star}_{n}) = 6 n - 18$ , respectively. Furthermore, we design an algorithm based on random iterations to obtain edge minimal cuts (RIEMC), aiming at solving the problem of the 1-extra r-component connectivity of G. Simulation results demonstrate that 1-extra r-component connectivity can accurately and effectively reflect fault tolerance and reliability of $\text{{Star}}_{n}$ ${Star}_{n}$ than the state-of-the-art connectivity measures.