DocumentCode :
105453
Title :
Reliability Evaluation of BC Networks in Terms of the Extra Vertex- and Edge-Connectivity
Author :
Weihua Yang ; Huiqiu Lin
Author_Institution :
Dept. of Math., Taiyuan Univ. of Technol., Taiyuan, China
Volume :
63
Issue :
10
fYear :
2014
fDate :
Oct. 2014
Firstpage :
2540
Lastpage :
2548
Abstract :
Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. The extra connectivity and the extra edge-connectivity are two important parameters for the reliability evaluation of interconnection networks. The n-dimensional bijective connection network (in brief, BC network) includes several well known network models, such as, hypercubes, Möbius cubes, crossed cubes, and twisted cubes. In this paper, we explore the extra connectivity and the extra edge-connectivity of BC networks, and discuss the structure of BC networks with many faults. We obtain a sharp lower bound of g-extra edge-connectivity of an n-dimensional BC network for n ≥ 4 and 1 ≤ g ≤ 2[[n/2]]. We also obtain a sharp lower bound of g-extra connectivity of an n-dimensional BC network for n ≥ 4 and 1 ≤ g ≤ 2 n which improves the result in [“Reliability evaluation of BC networks,” IEEE Trans. Computers, DOI: 10.1109/tc.2012.106.] for 1 ≤ g ≤ n - 3. Furthermore, we give a remark about exploring the g-extra edge-connectivity of BC networks for the more general g, and we also characterize the structure of BC networks with many faulty nodes or links. As an application, we obtain several results on the g-extra (edge-) connectivity and the structure of faulty networks on hypercubes, Möbius cubes, crossed cubes, and twisted cubes.
Keywords :
hypercube networks; multiprocessing systems; BC network extra edge-connectivity; BC network extra vertex-connectivity; BC network reliability evaluation; Möbius cube network models; crossed cube network models; faulty networks; hypercube network models; interconnection network reliability evaluation; multiprocessor systems; n-dimensional BC network; n-dimensional bijective connection network; twisted cube network models; Computer network reliability; Fault tolerance; Hypercubes; Multiprocessing systems; Program processors; BC networks; extra connectivity; extra edge-connectivity; hypercube; interconnection networks; maximally connected component; reliability;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2013.128
Filename :
6532290
Link To Document :
بازگشت