Previous [1] [2] [3] [4] [5] [6] [7] [8] [9]


Journal of Information Science and Engineering, Vol.19 No.3, pp.401-414 (May 2003)

Self-Stailizing Wormhole Routing on Ring Networks*

Ajoy K. Datta, Maria Gradinariu, Anthony B. Kenitzki
and Sebastien Tixeuil
School of Computer Science
University of Nevada Las Vegas
Las Vegas, NV89154, U.S.A.
*IRISA, Campus de Beaulieu, France
+Universite Paris Sud
LRI-CNRS UMR 8623, France

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.

Keywords: distributed algorithms, fault-tolerance, self-stabilization, wormhole routing, interconnexion networks, virtual channels

Full Text () Retrieve PDF document (200305_01.pdf)

Received May 15, 2002; accepted July 25, 2002.
Communicated by Biing-Feng Wang, Stephan Olariu and Gen-Huey Chen.
*A preliminary version of the paper was presented at the 2002 International Conference on Parallel and Distributed Systems, Chungli, Taiwan.