Self-Stabilizing Wormhole Routing on Ring Networks

Ajoy K. Datta ； Maria Gradinariu ； Anthony B. Kenitzki ； Sébastien Tixeuil

《Journal of Information Science and Engineering》 19卷3期 (2003/05) Pp. 401-414

https://doi.org/10.6688/JISE.2003.19.3.1

並列摘要

Wormhole routing is most commonly used in parallel architectures in which messages are sent in small fragments, called flits. It is a lightweight and efficient method of routing messages between parallel processors. Self-stabilization is a technique that guarantees tolerance to transient faults (e.g., memory corruption or communication hazards) for a given protocol. Self-stabilization guarantees that the network recovers to a correct behavior in a finite amount of time, without the need for human intervention. Self-stabilization also guarantees the safety property, meaning that once the network is in a legitimate state, it will remain there until another fault occurs.
This paper presents the first self-stabilizing network algorithm in the wormhole routing model, using the unidirectional ring topology. Our solution benefits from wormhole routing by providing high throughput and low latency, and from self-stabilization by ensuring automatic resilience to all possible transient failures.

並列關鍵字

distributed algorithms ； fault-tolerance ； self-stabilization ； wormhole routing ； interconnexion networks ； virtual channels