• Article
  • | |
  • Metrics
  • |
  • Reference [26]
  • |
  • Related
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    Optimal fault-tolerant routing is imperative for large hypercube systems in the existence of large number of faulty links or nodes. This paper first defines hypercube network with a large number of faulty nodes and/or links to be generalized hypercube and illustrates that many non-hypercube systems can be transformed to Generalized Hypercube systems. It then proposes node path vector (NPV) to capture the complete optimal and sub-optimal routing information for a generalized hypercube system. To reduce the computation iterations in solving NPV, it also introduces the concept of relay node technique. Based on NPV and relay node technique, this paper further proposes optimal fault-tolerant routing scheme (OFTRS) to derive shortest path for any communication pair in a generalized hypercube system. With an example of large number of faulty nodes or faulty links, it is illustrated that the previous algorithm could omit up to 60% routing paths, while this approach achieves all optimal and sub-optimal routing paths. Compared to previous work, OFTRS has a significant improvement in obtaining routing information for optimal and sub-optimal, i.e. no matter how many faulty nodes or links exist, it is guaranteed to route through the optimal or sub-optimal path as long as a path between the source-destination pair exists. In addition, the proposed scheme is distributed and relying only on non-faulty neighboring nodes since it only requires the information of non-faulty neighbor nodes in computing NPV, thus it has high applicability, especially when some non-hypercube systems can be transformed into Generalized Hypercube systems.

    Reference
    [1]Lee TC,Hayes JP.A fault-tolerant communication scheme for hypercube computers.IEEE Trans.on Computers,1992,41(10):1242-1256.
    [2]Chiu GM,Wu SP.A fault-tolerant routing strategy in hypercube multicomputers.IEEE Trans.on Computers,1996,45(2):143-155.
    [3]Chen MS,Shin KG.Depth-First approach for fault-tolerant routing in hypercube multicomputers.IEEE Trans.on Parallel and Distributed Systems,1990,1(2):152-159.
    [4]Jong K,Shin KG.Deadlock-Free fault-tolerant routing in injured hypercubes.IEEE Trans.on Computers,1993,42(9):1078-1088.
    [5]Chen MS,Shin KG.Adaptive fault-tolerant routing in hypercubes multicomputers.IEEE Trans.on Computers,1990,39(12):1406-1416.
    [6]Wu J.Reliable unicasting in faulty hypercubes using safety levels.IEEE on Computers,1997,46(2):241-247.
    [7]Wu J.Adaptive fault-tolerant routing in cube-based multicomputers using safety vectors.IEEE Trans.on Parallel and Distributed Systems,1998,9(4):321-334.
    [8]Gao F,Li ZC,Min YH,Wu J.A fault-tolerant routing strategy based on extended safety vectors in hypercube multicomputers.Chinese Journal of Computers,2000,23(3):248-254 (in Chinese with English abstract).
    [9]Gao F,Li ZC.Fault-Tolerant routing in hypercube multicomputers using optimal path matrices.Chinese Journal of Computers,2000,23(3):242-247 (in Chinese with English abstract).
    [10]Al-Sadi J,Day K,Ould-Khaoua M.A new fault-tolerant routing for k-ary n-cubes.Microprocessors and Microsystems,2001,25(5):239-246.
    [11]Al-Sadi J,Day K,Ould-Khaoua M.Probability vectors:A new fault-tolerant routing algorithm for k-ary n-cubes.In:Proc.of the 17th ACM Symp.on Applied Computing (SAC 2002).Madrid:IEEE Society,2002.830-834.
    [12]Tian SH.A fault-tolerant routing strategy based on extended optimal path matrices in hypercube multi-computers.Chinese Journal of Computers,2002,25(1):87-92 (in Chinese with English abstract).
    [13]Tian SH,Cai ZX,Tian Z,Tian M.Utilizing OPSBOPMs to realize a fault-tolerant routing strategy in hypercube system.Journal of Central South University of Technology (Natural Science Edition),2002,33(6):637-642 (in Chinese with English abstract).
    [14]Wang GJ,Chen JE,Chen SQ.Designing efficient routing algorithms on hypercube networks with a large number of faulty nodes.Chinese Journal of Computers,2001,24(9):909-916 (in Chinese with English abstract).
    [15]Wang L,Lin YP,Chen ZP,Wen X.Fault-Tolerant routing for hypercube multi-computers based on maximum safety-path matrices.Journal of Software,2004,15(7):994-1003 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/15/994.htm
    [16]Wang L,Lin YP,Chen ZP,Wen X.Fault-Tolerant routing based on safety path vectors in hypercube system.Journal of Software,2004,15(5):783-790 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/15/783.htm
    [17]Wu J,Gao F,Li ZC,Min YH.Optimal,and reliable communication in hypercubes using extended safety vectors.IEEE Trans.on Reliability,2005,54(3):402-411.
    [18]Schlosser M,Sintek M,Decker S,Nejdl W.HyperCuP-Hypercubes,ontologies and efficient search on P2P networks.In:Koubarakis M,ed.Proc.of the Int'l Workshop on Agents and Peer-to-Peer Computing (AP2PC).Bologna:Springer-Verlag,2002.112-124.
    [19]Castro M,et al.An evaluation of scalable application-level multicast built using peer-to-peer overlay networks.In:Proc.of the IEEE INFOCOM.San Francisco:IEEE Society,2003.1510-1520.
    [8]高峰,李忠诚,闵应骅,吴杰.超立方体多处理机系统中基于扩展安全向量的容错路由.计算机学报,2000,23(3):248-254.
    [9]高峰,李忠诚.用最优通路矩阵实现超立方体多处理机系统的容错路由.计算机学报,2000,23(3):242-247.
    [12]田绍槐.超立方体多处理机系统中基于扩展最优通路矩阵的容错路由.计算机学报,2002,25(1):87-92.
    [13]田绍槐,蔡朝曦,田争,田敏.用OPSBOPMs实现超立方体系统的容错路由.中南工业大学学报(自然科学版),2002,33(6):637-642.
    [14]王国军,陈建二,陈松乔.具有大量错误节点的超立方体网络中的高效路由算法的设计与讨论.计算机学报,2001,24(9):909-916.
    [15]王雷,林亚平,陈治平,文学.超立方体中基于极大安全通路矩阵的容错路由.软件学报,2004,15(7):994-1003.http://www.jos.org.cn/1000-9825/15/994.htm
    [16]王雷,林亚平,陈治平,文学.超立方体系统中基于安全通路向量的容错路由.软件学报,2004,15(5):783-790.http://www.jos.org.cn/ 1000-9825/15/783.htm [1]Since ESVs and EOPMS improve on SVs and OPMs respectively,we only show the path information based on ESVs and EOPMs in table 3.Those values with an underline are for EOPMs only.Others are for both ESVs and EOPMs.
    Related
    Comments
    Comments
    分享到微博
    Submit
Get Citation

田绍槐,陆应平,张大方.基于NPV广义超立方体最佳容错路由算法.软件学报,2007,18(7):1818-1830

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 14,2006
  • Revised:May 18,2006
You are the first2033413Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063