Reliability Evaluation of BC Networks in Terms of the Extra Vertex- and Edge-Connectivity
Reliability Evaluation of BC Networks in Terms of the Extra Vertex- and Edge-Connectivity
复制标题
DOI：
10.1109/tc.2013.128
复制
发表时间：
2014-10
影响因子：
3.7
通讯作者：
Weihua Yang;Huiqiu Lin
中科院分区：
文献类型：
--
作者：
Weihua Yang;Huiqiu Lin
互连网络的可靠性评估对多处理机系统的设计和维护具有重要意义。额外连通度和额外边连通度是评价互连网络可靠性的两个重要参数。n维双射连接网络（简称BC网络）包括几种众所周知的网络模型，如超立方体、莫比乌斯立方体、交叉立方体和扭曲立方体。本文研究了BC网络的额外连通度和额外边连通度，并讨论了多故障BC网络的结构。当n ≥ 4且1 ≤ g ≤ 2[[n/2]]时，得到了n维BC网络的g-额外边连通性的一个精确下界.我们还得到了n维BC网络的g-额外连通性的一个尖锐下界，其中n ≥ 4且1 ≤ g ≤ 2 n，这改进了[“Reliability evaluation of BC networks，”IEEE Trans. Computers，DOI：10.1109/tc.2012.106.]对于1 ≤ g ≤ n - 3。此外，我们还对更一般的g给出了BC网络的g-额外边连通性的一个讨论，并刻画了具有多个故障节点或故障链路的BC网络的结构。作为应用，我们得到了超立方体、莫比乌斯立方体、交叉立方体和扭曲立方体上g-额外（边）连通性和故障网络结构的若干结果.
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.