An O(log(2)(N)) Algorithm for Reliability Evaluation of h-Extra Edge-Connectivity of Folded Hypercubes

作者：Zhang, Mingzu; Zhang, Lianzhu^*; Feng, Xing; Lai, Hong-Jian

来源：IEEE Transactions on Reliability, 2018, 67(1): 297-307.

DOI：10.1109/TR.2017.2779130

• Algorithm
• edge fault tolerance
• folded hyper-cube
• h-extra edge-connectivity
• interconnection networks
• multiprocessor
• reliability evaluation

Reliability analysis of an interconnection network is of great significance to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of a given interconnected network G with N processors, denoted by lambda(h)(G), is the minimum cardinality of set of faulty links, such that whose removal will disconnect the network with all its resulting components having at least h processors for h <= N/2. It gives a more refined quantitative analysis of indicators of the robustness of a multiprocessor system in the presence of failing links. The n-dimensional folded hypercube FQ(n), as one of potential inter-connected networks, is a well-known variation of the hypercube structure with N = 2(n) processors. In this paper, the h-extra edge-connectivity of the network FQ(n), lambda(h)(FQ(n)), is first investigated for each well-defined positive integer h <= N/2. We divide the interval 1 <= h <= N/2 into some subintervals and obtain some properties of lambda(h)(FQ(n)) in these subintervals. Then, we deduce a recursive relation of lambda(h)(FQ(n)). Based on this recursion, an efficient O(log(2) (N)) algorithm is designed to totally determine the exact values and lambda(h)-optimality of lambda(h)(FQ(n)) for each h <= N/2.

• 出版日期2018-3
• 单位厦门大学