分层超立方网络的可靠性评估

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

Abstract

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_n) network under the PMC model and MM* model were obtained by theoretical deduction.In addition, the t/s-diagnosis algorithm of HHC_n 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_n is about h+1 times of its traditional diagnosability, and the t/s-diagnosability of HHC_n 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.

Key words: h-extra conditional diagnosability, t/s-diagnosability, t/s-diagnosis algorithm, hierarchical hypercube network, reliability

CLC Number:

TP301

Ximeng LIU, Yufang ZHANG, Shuming ZHOU, Xiaoyan LI. Reliability evaluation of hierarchical hypercube network[J]. Journal on Communications, 2021, 42(3): 111-121.

Figures/Tables 6

References 27

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	HUANG Y Z , LIN L M , XU L ,et al. Extra diagnosability and good-neighbor diagnosability of n-dimensional alternating group graph AG_nunder the PMC model[J]. Theoretical Computer Science, 2019,795: 36-49.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	FAN J X , LIN X L . The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers, 2005,54(2): 176-184.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	XU J M . Topological structure and analysis of interconnection networks[M]. Berlin: Springer, 2013.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	YANG W H , MENG J X . Extraconnectivity of hypercubes[J]. Applied Mathematics Letters, 2009,22(6): 887-891.
[25]	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.
[26]	郭晨, 肖志芳, 冷明 ,等. 交换交叉立方网络在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.
[27]	熊茜, 梁家荣, 马强 . 交换超立方网络的 (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.

Metrics

Recommended 0

No Suggested Reading articles found!

Reliability evaluation of hierarchical hypercube network

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 27

Related Articles 15

Metrics

Recommended 0

[1]	Zhaoyang ZHANG, Jiajia WU, Jue WANG, Chu ZHOU. Joint time and beam domain non-orthogonal multiple access [J]. Journal on Communications, 2021, 42(4): 76-88.
[2]	Chaonong XU,Jianxiong WU,Yongjun XU. Highly reliable access algorithm for PD-NOMA based IoT with delay guarantee [J]. Journal on Communications, 2020, 41(9): 210-221.
[3]	Ruyan WANG,Yishuang GAO,Xiao CHEN. Reliable transmission mechanism with differentiated protection in virtualized fiber-wireless access network [J]. Journal on Communications, 2019, 40(3): 36-47.
[4]	Julong LAN,Zijin JIN,Penghao SUN,Yiming JIANG,Yue WANG. Service function chain construct algorithm based on reliability [J]. Journal on Communications, 2019, 40(1): 64-70.
[5]	Zhe WANG,Taoshen LI,Jin YE,Zhihui GE,Min WU. Reliability modeling and planning of energy harvesting based on uncertainty theory [J]. Journal on Communications, 2018, 39(5): 166-176.
[6]	Zi-jing CHENG,Jun-nan ZHAO,Yu-wen CUI,Le-yi SHI. Reliability and cost efficiency analysis for deep space habitat network based on Nash bargaining solution [J]. Journal on Communications, 2017, 38(2): 10-15.
[7]	Tao HU,Jian-hui ZHANG,Teng MA,Wei ZHAO. Multi-controller balancing deployment strategy based on reliability evaluation in SDN [J]. Journal on Communications, 2017, 38(11): 188-198.
[8]	Yue SHI,song QIUXue,yong GUOShao,Feng QI. Optimal planning of optical transmission network using improved genetic algorithm [J]. Journal on Communications, 2016, 37(1): 116-122.
[9]	UGuo-bing H,ULi-zhong X,AOAn-ping B,UShan-shan W,AOYan G. Reliability test for frequency estimation of sinusoid based on LMP detection [J]. Journal on Communications, 2015, 36(5): 89-97.
[10]	. Secure and high throughput routing protocol with QoS constraints in cognitive wireless Mesh networks [J]. Journal on Communications, 2014, 35(11): 8-66.
[11]	Zhu-fang KUANG,Zhi-gang CHEN,Guo-jun WANG,Hui LIU. Secure and high throughput routing protocol with QoS constraints in cognitive wireless Mesh networks [J]. Journal on Communications, 2014, 35(11): 69-80.
[12]	. Modeling and maintaining the reliability of data replica service in cloud storage systems [J]. Journal on Communications, 2014, 35(10): 11-97.
[13]	Chang-qin HUANG,Yuan LI,Hong-yan WU,Yong TANG,Xuan LUO. Modeling and maintaining the reliability of data replica service in cloud storage systems [J]. Journal on Communications, 2014, 35(10): 89-97.
[14]	. RSPEED：the reliability and real-time routing based on uncertain delay in wireless sensor network [J]. Journal on Communications, 2013, 34(8): 15-119.
[15]	Quan CHEN,Hong GAO. RSPEED：the reliability and real-time routing based on uncertain delay in wireless sensor network [J]. Journal on Communications, 2013, 34(8): 110-119.