[go: up one dir, main page]

Lan, 1994 - Google Patents

A fault-tolerant routing algorithm in hypercubes

Lan, 1994

Document ID
14063420785953707051
Author
Lan Y
Publication year
Publication venue
1994 International Conference on Parallel Processing Vol. 3

External Links

Snippet

Fault-tolerant communication mechanism for multicomputer systems is an important feature to reliability-critical applications. In this paper, we will present a fault-tolerant routing algorithm that has a better performance than a previous work in the sense that it requires …
Continue reading at ieeexplore.ieee.org (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17356—Indirect interconnection networks
    • G06F15/17368—Indirect interconnection networks non hierarchical topologies
    • G06F15/17381—Two dimensional, e.g. mesh, torus
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • G06F15/17337—Direct connection machines, e.g. completely connected computers, point to point communication networks
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Error detection; Error correction; Monitoring responding to the occurence of a fault, e.g. fault tolerance
    • G06F11/16—Error detection or correction of the data by redundancy in hardware
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Error detection; Error correction; Monitoring responding to the occurence of a fault, e.g. fault tolerance
    • G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • H04L12/42—Loop networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/06—Deflection routing, e.g. hot-potato routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/22—Alternate routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/06—Arrangements for maintenance or administration or management of packet switching networks involving management of faults or events or alarms
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions

Similar Documents

Publication Publication Date Title
Chiu The odd-even turn model for adaptive routing
Chow et al. Hyperswitch network for the hypercube computer
US6918063B2 (en) System and method for fault tolerance in multi-node system
Lan A fault-tolerant routing algorithm in hypercubes
Lan An adaptive fault-tolerant routing algorithm for hypercube multicomputers
Tien et al. Algorithms and bounds for shortest paths and diameter in faulty hypercubes
Habibian et al. Fault-tolerant routing methodology for hypercube and cube-connected cycles interconnection networks
Ghafoor A class of fault-tolerant multiprocessor networks
Puente et al. Immucube: Scalable fault-tolerant routing for k-ary n-cube networks
Lan Adaptive fault-tolerant multicast in hypercube multicomputers
Rajkumar et al. Multistage interconnection networks reliability analysis
Alam et al. Routing in modular fault-tolerant multiprocessor systems
Olenev et al. Algorithms and methods for design and simulation of onboard SpaceWire networks
Fraigniaud Fault-tolerant gossiping on hypercube multicomputers
Das et al. Stirling networks: a versatile combinatorial topology for multiprocessor systems
Liu et al. Node-disjoint paths in balanced hypercubes with application to fault-tolerant routing
Omari Adaptive Algorithms for Wormhole-Routed Single-Port Mesh-Hypercube Network
Blough et al. Near-optimal message routing and broadcasting in faulty hypercubes
Fukushi et al. A Fault-tolerant Routing Method for Network-on-Chips Based on Communication Function Fault Model
Döring et al. A flexible approach for a fault-tolerant router
Ravikumar et al. Adaptive routing in k-ary n-cubes using incomplete diagnostic information
Avresky et al. Reconfiguration of faulty hypercubes
Ashraf et al. Introduction to routing in multicomputer networks
Chen et al. Fault-tolerant routing for pyramid networks using the least level minimal routing method
Sun et al. Fault tolerant all-to-all broadcast in general interconnection networks