Research on(t,k)-diagnosability for exchanged hypercube network

Xi XIONG; Jia-rong LIANG; Qiang MA

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

您当前的位置：

首页 >

文章列表页 >

Research on(t,k)-diagnosability for exchanged hypercube network

Academic paper | 更新时间：2024-06-05

- Research on(t,k)-diagnosability for exchanged hypercube network
- Journal on Communications Vol. 37, Issue 3, Pages: 190-198(2016)
- 作者机构：
  
  广西大学计算机与电子信息学院，广西南宁530004
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.1000-436x.2016067
  CLC： TP393
- Online First：2016-03，
  
  Published：25 March 2016
- 稿件说明：
移动端阅览
Xi XIONG, Jia-rong LIANG, Qiang MA. Research on(t,k)-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016, 37(3): 190-198.
DOI：

Xi XIONG, Jia-rong LIANG, Qiang MA. Research on(t,k)-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016, 37(3): 190-198. DOI： 10.11959/j.issn.1000-436x.2016067.

摘要

故障诊断是网络系统修复的一个重要环节，PMC诊断模型是一种简单、易于理解的故障诊断模型。通过对以交换超立方网EH(s

p)(1≤s≤p)为拓扑模型的多处理器系统进行结构分析，给出了该网络系统的一般化的故障诊断方法——(t

k)诊断方法，证明了在PMC模型下交换超立方网络EH(s

p)(1≤s≤p)是

</mo><mi>s</mi><mo>+</mo><mn>1</mn></mrow> <mo>)</mo></mrow></mrow></math>

可诊断的，且是条件

</mo><mn>2</mn><mi>s</mi></mrow> <mo>)</mo></mrow></math>

可诊断的。结果表明，交换超立方网的(t

k)诊断度大于其传统诊断度s+1，条件(t

k)诊断度

大于其传统条件诊断度4s-3。这些结果为交换超立方网络的故障诊断提供了重要的理论依据。

Abstract

Fault diagnosis was an important part in the processing of network system repair.PMC was a diagnosis model which was simple and easy to be understood.Through analysis of the structure of exchanged hypercube

a generalization measure of fault diagnosis for the network system was provided

called (t

k)-fault diagnosis method.By computing

it is shown that EH(s

p) is

</mo> <mi>s </mi> <mo>+ </mo> <mn>1 </mn> </mrow> <mo>) </mo> </mrow> </math>

-diagnosable and conditional

</mo> <mn>2 </mn> <mi>s </mi> </mrow> <mo>) </mo> </mrow> </math>

-diagnosable

where 1≤s≤p.The result shows that the(t

k)-diagnosability of EH(s

p) is

which is bigger than its ordinary diagnosability s+1

and the conditional (t

k)-diagnosability is

which is bigger than its ordinary conditional diagnosability 4s-3.Above results present the important theory basis for fault diagnosis of exchanged hypercube network.

关键词

Keywords

references

MALEK M . A comparison connection assignment for diagnosable of multiprocessor systems [C ] // The 7th Annual Symposium on Computer Architecture . New York,United States , c 1980 : 31 - 36 .

MAENG J , MALEKM . A comparison connection assignmentfor self-diagnosis of multiprocessor systems [C ] // The 11th International Symposium on Fault Tolerant Computing . Edinburgh,Scotland , c 1981 : 173 - 175 .

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

HONG W S , HSIEH S Y . Strong diagnosability and conditional diag-nosability of augmented cubes under the comparison diagnosis model [J ] . IEEE Transactions on Reliability , 2012 , 61 ( 1 ): 140 - 148 .

KHANNNA S , PUCHS W K . A Graph partitioning approach to sequential diagnosis [J ] . IEEE Transactions on Computer 1997 , 46 ( 1 ): 39 - 47 .

LEE C W , HSIEH S Y . Diagnosability of two-matching composition network under the MM* model [J ] . IEEE Transactions on Dependable and Secure Computing . 2011 , 8 ( 2 ): 246 - 255 .

HSIEH S Y , CHEN Y S . Strongly diagnosable product networks under the comparison diagnosis model [J ] . IEEE Transactions on Computers , 2008 , 57 ( 6 ): 721 - 732 .

PREPARATA F P , METZE G , CHIEN R T . On the connectionassign-ment problem of diagnosable systems [J ] . IEEE Transactions on Elec-tronic Computers , 1967 , 16 ( 6 ): 848 - 854 .

CHANG N W , HSIEH S Y . Conditional diagnosability of augmented cubes under the PMC model [J ] . IEEE Transactions on Dependable and Secure Computing , 2012 , 9 ( 1 ): 46 - 60 .

ZHU Q . The conditional diagnosability of crossed cubes under the comparison model [J ] . International Journal of Computer Mathematics , 2010 , 87 ( 15 ): 3387 - 3396 .

LIN C K , KUNG T L , TAN J J M . An algorithmic approach to condi-tional-fault local diagnosis of regular multiprocessor interconnected systems under the PMC model [J ] . IEEE Transactions on uters , 2013 , 62 ( 3 ): 439 - 451 .

LIN C K , PENG S L , TAN J J M , et al . The diagnosability of g-good-neighbor conditional- fault hypercube under PMC model [C ] // 2010 International Conference on Parallel and Distributed Processing Tech-niques and Applications (PDPTA'10). Las Vegas,USA , c 2010 : 494 - 499 .

CHANG G Y , CHANG G J , CHEN G H . Diagnosability of regular networks [J ] . IEEE Transactions on Parallel and Distributed Systems , 2005 , 16 ( 4 ): 314 - 323 .

XU M , THULASIRAMAN K , XU X D . Conditional diagnosability of matching composition networks under the PMC model [J ] . IEEE Transactions on Circuits and Systems-II:Express Briefs , 2009 , 56 ( 11 ): 875 - 879 .

LIN C K , KUNG T L , TAN J J M . Conditional-fault diagnosability of multiprocessor systems with an efficient local diagnos algorithm un-der the PMC model [J ] . IEEE Transactions on Computers , 2011 , 22 ( 10 ): 1669 - 1680 .

ARAKI T , SHIBATA Y . (t,k)-Diagnosable system:a generalization of the PMC models [J ] . IEEE Transactions on Computers , 2003 , 52 ( 7 ): 971 - 975 .

CHEN C , HESIH S Y . (t,k)-diagnosis for component-composition graphs under the MM ∗model [J ] . IEEE Transactions on Computers , 2011 , 60 ( 12 ): 1704 - 1717 .

CHANG G Y . (t,k)-diagnosability for regular networks [J ] . IEEE Transactions on Computers , 2010 , 59 ( 9 ): 1153 - 1157 .

CHANG G Y , CHEN G H . (t,k)-Diagnosability of multiprocessorsys-tems with applications to grids and toris [J ] . Siam Journal on Compu-ting , 2007 , 37 ( 4 ): 1280 - 1298 .

LAI P L , TAN J J M , CHANG C P , et al . Conditional diagnosability measures for large multiprocessor systems [J ] . IEEE Transactions on Computers , 2005 , 54 ( 2 ): 165 - 175 .

郭晨，梁家荣，葛志辉，等 . 基于互测PMC模型的条件诊断算法 [J ] . 电子学报 2015 , 43 ( 2 ): 255 - 261 .

GUO C , LIANG J R , GE Z H , et al . A conditional diagnosis algorithm based on ex-test PMC model [J ] . Chinese Journal of Electronics , 2015 , 43 ( 2 ): 255 - 261 .

LOH P K K , HSU W J , PAN Y . The exchange hypercube [J ] . IEEE Transactions on Parallel and Distributed Systems , 2005 , 16 ( 9 ): 866 - 874 .

LIANG J R , HUANG Y , YE L C . Diagnosabilities of exchanged hypercube networks under pessimistic one-step diagnosis strategy [J ] . Journal of System Engineering and Electronics , 2015 , 26 ( 2 ): 415 - 420 .

MA M J , ZHU L Y . The super connectivity of exchanged hyper-cubes [J ] . Information Processing Letters , 2011 , 111 ( 8 ): 360 - 364 .

LI X J , XU J M . Generalized measures of fault tolerance in exchanged hypercubes [J ] . Information Processing Letters , 2013 , 113 ( 14 ): 533 - 537 .

Views

1240

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

(t,k)-diagnosability of exchanged crossed cube under the PMC model

Related Author

Chen GUO

Zhifang XIAO

Ming LEMG

Shuo PENG

Bo WANG

Related Institution

School of Electronic and Information Engineering,Jinggangshan University,Ji’an

Jiangxi Engineering Laboratory of IoT Technologies for Crop Growth,Ji’an

AI问答

⁰