A novel view: edge isoperimetric methods and reliability evaluation of several kinds of conditional edge-connectivity of interconnection networks

Abstract

Reliability evaluation and fault tolerance of an interconnection network of some parallel and distributed systems are discussed separately under various link-faulty hypotheses in terms of different $\mathcal{P}$-conditional edge-connectivity. With the help of edge isoperimetric problem's method in combinatorics, this paper mainly offers a novel and unified view to investigate the $\mathcal{P}$-conditional edge-connectivities of hamming graph $K_L^n$ with satisfying the property that each minimum $\mathcal{P}$-conditional edge-cut separates the $K_L^n$ just into two components, such as $L^t$-extra edge-connectivity, $t$-embedded edge-connectivity, cyclic edge-connectivity, $(L-1)t$-super edge-connectivity, $(L-1)t$-average edge-connectivity and $L^t$-th isoperimetric edge-connectivity. They share the same values in form of $(L-1)(n-t)L^t$ (except for cyclic edge-connectivity), which equals to the minimum number of links-faulty resulting in an $L$-ary-$n$-dimensional sub-layer from $K_L^n$. Besides, we also obtain the exact values of $h$-extra edge-connectivity and $h$-th isoperimetric edge-connectivity of hamming graph $K_L^n$ for each $h\le L^{\lfloor \frac{n}{2}\rfloor }$. For the case $L=2$, $K_2^n=Q_n$ is $n$-dimensional hypercube. Our results can be applied to more generalized class of networks, called $n$-dim-ensional bijective connection networks, which contains hypercubes, twisted cubes, crossed cubes, Möbius cubes, locally twisted cubes and so on. Our results improve several previous results on this topic.

12 pages, 8 figures, 2021 IEEE 21st International Conference on Software Quality, Reliability and Security (QRS)