Reliability Evaluation of BC Networks

Abstract

Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity determination and faulty networks' structure analysis are two important aspects for the reliability evaluation of interconnection networks. An n-dimensional bijective connection network (in brief, BC network), denoted by X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> , is an n-regular graph with 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> vertices and n2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n-1</sup> edges. The hypercubes, Mobius cubes, crossed cubes, and twisted cubes are some examples of the BC networks. By exploring the boundary problem of the BC networks, we prove that when n ≥ 4 and 0 ≤ h ≤ n - 4 the h-extra connectivity of an n-dimensional BC network X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> is k <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">h</sub> (X <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> = n(h + 1)- 1/2h (h + 3). Furthermore, there exists a large connected component and the remaining small components have at most h vertices in total if the total number of faulty vertices is strictly less its h-extra connectivity. As an application, the results on the h-extra connectivity and structure of faulty networks on hypercubes, Mobius cubes, crossed cubes, and twisted cubes are obtained.