Fault tolerant routing in star graph networks in the forbidden fault model

被引：0
作者：
Latifi, S [1 ]
Rouskov, Y [1 ]
Srimani, P [1 ]
机构：
[1] Univ Nevada, Dept Elect Engn, Las Vegas, NV 89154 USA
来源：
INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-III, PROCEEDINGS | 1997年
关键词：
star graph; fault tolerant routing; forbidden fault model; algorithm;
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
It is well known that star graphs are strongly resilient like the n cubes in the sense that they are optima[ly fault tolerant and the fault diameter is increased only by one in the presence of maximum number of allowable faults [1, 2]. Star graphs have also been investigated under the conditions of forbidden faulty sets [3] where all the neighbors of any node cannot be faulty simultaneously; we have shown [4] that under these conditions star graphs can tolerate up to (2n - 5) faulty nodes and the fault diameter is increased only by 2 in the worst case in presence of maximum number of faults. Thus, star graphs enjoy the similar property of strong resilience under forbidden faulty sets like the n-cubes. Our purpose in the present paper is to develop shortest routing algorithms between arbitrary pair of nodes under this restricted fault model.
引用
收藏
页码：1605 / 1613
页数：9
相关论文
共 50 条
  • [31] A study of fault tolerance in star graph
    Latifi, Shahram
    INFORMATION PROCESSING LETTERS, 2007, 102 (05) : 196 - 200
  • [32] Fault-tolerant routing in two-dimensional mesh networks with less-restricted fault patterns
    Wang, SD
    Sui, PH
    2001 PACIFIC RIM INTERNATIONAL SYMPOSIUM ON DEPENDABLE COMPUTING, PROCEEDINGS, 2001, : 111 - 118
  • [33] A Fault-tolerant Routing Method for Network-on-Chips Based on Communication Function Fault Model
    Fukushi, Masaru
    Kouda, Kazuya
    Kurokawa, Yota
    2021 9TH INTERNATIONAL CONFERENCE ON INFORMATION AND EDUCATION TECHNOLOGY (ICIET 2021), 2021, : 405 - 409
  • [34] Fault-tolerant ring embedding in a star graph with both link and node failures
    Tseng, YC
    Chang, SH
    Sheu, JP
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (12) : 1185 - 1195
  • [35] Dynamic Reliability Analysis Model for Fault-tolerant Network Routing
    Wang Bin
    Wu Chunming
    Yang Qiang
    Qian Yaguan
    Wang Xiaonan
    CHINESE JOURNAL OF ELECTRONICS, 2012, 21 (03): : 500 - 504
  • [36] A Fault-Tolerant Routing Algorithm Design for On-Chip Optical Networks
    Xiang, Dong
    Zhang, Yan
    Shan, Shuchang
    Xu, Yi
    2013 IEEE 32ND INTERNATIONAL SYMPOSIUM ON RELIABLE DISTRIBUTED SYSTEMS (SRDS 2013), 2013, : 1 - 9
  • [37] Fault-tolerant routing in unique-path multistage interconnection networks
    Sadawarti, H
    Bansal, PK
    Proceedings of the IEEE INDICON 2004, 2004, : 427 - 430
  • [38] Fault-tolerant routing for reliable packet transmission in on-chip networks
    Ouyang, Yiming
    Zhang, Tianbao
    Li, Jianhua
    Liang, Huaguo
    MICROELECTRONICS JOURNAL, 2024, 153
  • [39] Directed flooding: A fault-tolerant routing protocol for wireless sensor networks
    Farivar, R
    Fazeli, M
    Miremadi, SG
    2005 SYSTEMS COMMUNICATIONS, PROCEEDINGS: ICW 2005, WIRELESS TECHNOLOGIES; ICHSN 2005, HIGH SPEED NETWORKS; ICMCS 2005, MULTIMEDIA COMMUNICATIONS SYSTEMS; SENET 2005, SENSOR NETWORKS, 2005, : 395 - 399
  • [40] An Adaptive Learning Approach for Fault-Tolerant Routing in Ad Hoc Networks
    Misra, Sudip
    Krishna, P. Venkata
    Bhiwal, Akhil
    Chawla, Amardeep Singh
    Wolfinger, Bernd E.
    E-TECHNOLOGIES AND NETWORKS FOR DEVELOPMENT, 2011, 171 : 15 - 25
12345