An incremental network topology for contention-free and deadlock-free routing
Journal
Ninth International Conference on Parallel and Distributed Systems
Journal Volume
2002-January
Pages
209-215
Date Issued
2002-12
Date
2002-12
Author(s)
Abstract
Wormhole switching has become the most widely used switching technique for multicomputers. However, the main drawback of wormhole switching is that blocked messages remain in the network, prohibiting other messages from using the occupied links and buffers. To address the deadlock problem without compromising communication latency and the incremental expansion capability that irregular networks can offer, we propose a simple topology called extended incremental triangular mesh (EITM) for switch-based networks. EITM is an extension of a previous ITM (incremental triangular mesh) topology with a more flexible structure. We also show that EITM is highly scalable, allows incremental expansion of systems, has guaranteed deadlock freedom, and can support contention-free multicast. First, we show that for an EITM, any shortest path routing method will not deadlock, therefore EITM networks are ideal for the escape paths in adaptive routing networks. Second, we show that it is possible to arrange the nodes of an EITM in a circular order so that two messages from independent parts of the circular order will not interfere with each other - this is extremely useful for implementing contention-free multicast and other collective communication operations. We also present the results on the relation between ITM/EITM, outer planar graphs and chordal graphs. We show that chordal graphs are strongly related to the freedom of deadlock for shortest path routing, and ITM in our previous paper is indeed maximum outer planar graph. © 2002 IEEE.
Subjects
Network topology; Routing; System recovery
SDGs
Other Subjects
Flexible structures; Graph theory; Graphic methods; Mesh generation; MESH networking; Multicasting; Switching circuits; Topology; Collective communication operations; Communication latency; Deadlock-free routing; Network topology; Routing; Shortest path routing; Switch-based networks; System recovery; Network routing
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
01183401.pdf
Size
671.86 KB
Format
Adobe PDF
Checksum
(MD5):9cef1a59dc6ae126cc036d1b50e54adb