Adaptive, fault-tolerant, deadlock-free and livelock-free interval routing in mesh networks

Author

Loh, Peter ; Wenge, Jing

Author_Institution

Sch. of Appl. Sci., Nanyang Technol. Inst., Singapore

fYear

1996

fDate

11-13 Jun 1996

Firstpage

348

Lastpage

355

Abstract

An adaptive, deadlock-free and livelock-free routing algorithm for faulty two-dimensional mesh connected multiprocessor interconnection networks based on store-and-forward communication is presented in this paper. Only three virtual networks, VN₀, VN₁ and VN₂, are needed. The algorithm is composed of two parts. Part one implemented in VN₀ is deadlock-free and allows a packet to use the path with minimum traffic congestion. Part two is fully-adaptive minimal routing. It requires two virtual networks-VN₁ and VN₂

Keywords

fault tolerant computing; multiprocessor interconnection networks; telecommunication network routing; 2D mesh connected multiprocessor interconnection networks; adaptive routing; deadlock-free routing; fault-tolerant interval routing; livelock-free interval routing; livelock-free routing algorithm; mesh networks; minimum traffic congestion; store-and-forward communication; virtual networks; Delay; Fault tolerance; Intelligent networks; Mesh networks; Multiprocessor interconnection networks; Packet switching; Routing; System recovery; Telecommunication traffic; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

Algorithms & Architectures for Parallel Processing, 1996. ICAPP 96. 1996 IEEE Second International Conference on

Print_ISBN

0-7803-3529-5

Type

conf

DOI

10.1109/ICAPP.1996.562895

Filename

562895