Reliability evaluation of hierarchical hypercube network

Ximeng LIU; Yufang ZHANG; Shuming ZHOU; Xiaoyan LI

doi:10.11959/j.issn.1000-436x.2021064

您当前的位置：

首页 >

文章列表页 >

Reliability evaluation of hierarchical hypercube network

Papers | 更新时间：2024-06-05

- Reliability evaluation of hierarchical hypercube network
- Journal on Communications Vol. 42, Issue 3, Pages: 111-121(2021)
- 作者机构：
  
  1. 福州大学数学与计算机科学学院，福建福州 350108
  2. 福州大学网络安全福建省高校重点实验室，福建福州 350108
  3. 福建师范大学数学与信息学院，福建福州 350007
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(62002062);The National Natural Science Foundation of China(62072109);Education and Scientic Research Project of Young and Middle-aged Teachers of Fujian Provincial Education Department(JAT190031)
- DOI：10.11959/j.issn.1000-436x.2021064
  CLC： TP301
- Online First：2021-03，
  
  Published：25 March 2021
- 稿件说明：
移动端阅览
Ximeng LIU, Yufang ZHANG, Shuming ZHOU, et al. Reliability evaluation of hierarchical hypercube network[J]. Journal on Communications, 2021, 42(3): 111-121.
DOI：

Ximeng LIU, Yufang ZHANG, Shuming ZHOU, et al. Reliability evaluation of hierarchical hypercube network[J]. Journal on Communications, 2021, 42(3): 111-121. DOI： 10.11959/j.issn.1000-436x.2021064.

摘要

针对目前关于分层超立方网络的可靠性研究不够系统，严重制约了其应用和推广的问题，以分层超立方网络为研究对象，在得到分层超立方网络相关拓扑性质的基础上，通过理论推导得到了n维分层超立方（HHC

）在PMC模型和MM*模型下的h-额外条件诊断度和t/s-诊断度。此外，设计了HHC

在PMC模型和MM*模型下的t/s-诊断算法，并分析了其时间复杂度。研究结果表明，HHC

的h-额外条件诊断度是其传统诊断度的约h+1倍， t/s-诊断度是其传统诊断度约 s+1 倍。该结果进一步完善了分层超立方网络的可靠性指标，为其应用和推广提供了重要的理论依据。

Abstract

Aiming at the problem that the reliability research on hierarchical hypercube networks was not yet systematic

which severely restricted its application and popularization

the hierarchical hypercube network was taken as studying object

on the basis of obtaining the relevant topological properties of the hierarchical hypercube network

the h-extra conditional diagnosability and t/s-diagnosability of the n-dimension hierarchical hypercube (HHC

) network under the PMC model and MM* model were obtained by theoretical deduction.In addition

the t/s-diagnosis algorithm of HHC

under the PMC model and MM* model was designed and its time complexity was analyzed.The research results show that

the h-extra conditional diagnosability of HHC

is about h+1 times of its traditional diagnosability

and the t/s-diagnosability of HHC

is about s+1 times of its traditional diagnosability.Those results improve the reliability index of the hierarchical hypercube network and provide an important theoretical basis for its application and popularization.

关键词

Keywords

references

PREPARATA F P , METZE G , CHIEN R T . On the connection assignment problem of diagnosable systems [J ] . IEEE Transactions on Electron Devices , 1967 , 16 ( 6 ): 848 - 854 .

MAENG M , MALEK M . A comparison connection assignment for diagnosis of multiprocessor systems [C ] // Proceedings of the 11th International Fault-Tolerant Computing . New York:ACM Press , 1981 : 173 - 175 .

SENGUPTA A , DAHBURA A T . On self-diagnosable multiprocessor systems:diagnosis by the comparison approach [J ] . IEEE Transactions on Computers , 1992 , 41 ( 11 ): 1386 - 1396 .

ZHANG S R , YANG W H . The g-extra conditional diagnosability and t/k-diagosability of hypercubes [J ] . International Journal of Computer Mathematics , 2016 , 93 ( 3 ): 482 - 497 .

LIN L M , XU L , CHEN R Q , et al . Relating extra connectivity and extra conditional diagnosability regular networks [J ] . IEEE Transactions on Dependable and Secure Computing , 2019 , 16 ( 6 ): 1086 - 1097 .

HUANG Y Z , LIN L M , XU L , et al . Extra diagnosability and good-neighbor diagnosability of n-dimensional alternating group graph AG n under the PMC model [J ] . Theoretical Computer Science , 2019 , 795 : 36 - 49 .

LIU H Q , ZHANY S Z , LI D . On g-extra conditional diagnosability of hierarchical cubic networks [J ] . Theoretical Computer Science , 2019 , 790 : 66 - 79 .

LYU M J , FAN J X , ZHOU J Y , et al . The extra connectivity and extra diagnosability of regular interconnection networks [J ] . Theoretical Computer Science , 2020 , 809 : 88 - 102 .

SUN X L , ZHOU S M , GU Z D , et al . Reliability evaluation of complete cubic networks [J ] . International Journal of Parallel,Emergent and Distributed Systems , 2020 , 35 ( 1 ): 42 - 56 .

SOMANI A K , PELEG O . On diagnosability of large fault sets in regular topology-based computer systems [J ] . IEEE Transactions on Computers , 1996 , 45 ( 8 ): 892 - 903 .

FAN J X , LIN X L . The t/k-diagnosability of the BC graphs [J ] . IEEE Transactions on Computers , 2005 , 54 ( 2 ): 176 - 184 .

YANG X F , TANG Y Y . A (4n-9)/3-diagnosis algorithm on n-dimensional cube network [J ] . Information Sciences , 2007 , 177 ( 8 ): 1771 - 1781 .

ZHOU S M , LIN L M , XU L , et al . The t/k-diagnosability of star graph networks [J ] . IEEE Transactions on Computers , 2015 , 64 ( 2 ): 547 - 555 .

LIN L M , XU L , ZHOU S M , et al . The t/k-diagnosability for regular networks [J ] . IEEE Transactions on Computers , 2016 , 65 ( 10 ): 3157 - 3170 .

LIANG J R , ZHANG Q . The t/s-diagnosability of hypercube networks under the PMC and comparison models [J ] . IEEE Access , 2017 , 5 : 5340 - 5346 .

XIE M , YE L C , LIANG J R . A t/k-diagnosis algorithm on hypercube-like networks [J ] . Concurrency and Computation:Practice and Experience , 2018 , 30 ( 6 ): 1 - 8 .

LI X Y , JIA X H , FAN J X , et al . Reliability analysis of data center networks based on precise and imprecise diagnosis strategies [J ] . Theoretical Computer Science , 2020 , 809 : 189 - 203 .

MALLUHI Q M , BAYOUMI M A . The hierarchical hypercube:a new interconnection topology for massively parallel systems [J ] . IEEE Transactions on Parallel and Distributed Systems , 1994 , 5 ( 1 ): 17 - 30 .

XU J M . Topological structure and analysis of interconnection networks [M ] . Berlin : Springer , 2013 .

DAHBURA A T , MASSON G M . An O(n 2.5 ) faulty identification algorithm for diagnosable systems [J ] . IEEE Transactions on Computers , 1984 , 33 ( 6 ): 486 - 492 .

PREPARATA F P , VUILLEMIN J . The cube-connected-cycles:a versatile network for parallel computation [J ] . Communications of the ACM , 1981 , 24 ( 5 ): 300 - 309 .

LI X Y , LIN C K , FAN J X , et al . Relationship between extra connectivity and component connectivity in networks [J ] . The Computer Journal , 2021 , 64 ( 1 ): 38 - 53 .

ZHOU S M , LIN L M , XU J M . Conditional fault diagnosis of hierarchical hypercubes [J ] . International Journal of Computer Mathematics , 2012 , 89 ( 16 ): 2152 - 2164 .

YANG W H , MENG J X . Extraconnectivity of hypercubes [J ] . Applied Mathematics Letters , 2009 , 22 ( 6 ): 887 - 891 .

CHENG E , QIU K , SHEN Z Z . The h-extra diagnosability of the generalized exchanged hypercube [J ] . International Journal of Computer Mathematics:Computer Systems Theory , 2020 , 5 ( 2 ): 112 - 123 .

郭晨 , 肖志芳 , 冷明 , 等 . 交换交叉立方网络在PMC模型下的(t,k)诊断度研究 [J ] . 通信学报 , 2019 , 40 ( 6 ): 190 - 202 .

GUO C , XIAO Z F , LENG M , et al . (t,k)-diagnosability of exchanged crossed cube under the PMC model [J ] . Journal on Communications , 2019 , 40 ( 6 ): 190 - 202 .

熊茜 , 梁家荣 , 马强 . 交换超立方网络的 (t,k)-诊断度研究 [J ] . 通信学报 , 2016 , 37 ( 3 ): 190 - 198 .

XIONG X , LIANG J R , MA Q . Research on (t,k)-diagnosability for exchanged hypercube network [J ] . Journal on Communications , 2016 , 37 ( 3 ): 190 - 198 .

Views

1385

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

LQG control-aware resource scheduling method for IEEE 802.11ax networks

Joint time and beam domain non-orthogonal multiple access

Highly reliable access algorithm for PD-NOMA based IoT with delay guarantee

Reliable transmission mechanism with differentiated protection in virtualized fiber-wireless access network

Service function chain construct algorithm based on reliability

Related Author

Lei ZHANG

Wei LIANG

Meng ZHENG

Chu ZHOU

Jue WANG

Jiajia WU

Zhaoyang ZHANG

Yongjun XU

Related Institution

Key Laboratory of Networked Control Systems, Chinese Academy of Sciences

Institutes for Robotics and Intelligent Manufacturing, Chinese Academy of Sciences

School of Computer Science and Technology, University of Chinese Academy of Sciences

State Key Laboratory of Robotics, Shenyang Institute of Automation, Chinese Academy of Sciences

College of Information Science and Electronic Engineering, Zhejiang University

AI问答

⁰