An Adaptive Routing Algorithm for WK-Recursive Topologies |
| |
Authors: | L Verdoscia R Vaccaro |
| |
Affiliation: | (1) Instituto per la Ricerca sui Sistemi Informatici Paralleli -- CNR, Via P. Castellino, 111, Italy, e-mail: lorenzo@irsip.na.cnr.it , IT |
| |
Abstract: | This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive
routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have
been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions,
the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each
node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore,
this routing algorithm is able to tolerate up to faulty links.
Received: July 19, 1998; revised May 17, 1999 |
| |
Keywords: | AMS Subject Classifications:68M10 90B12 |
本文献已被 SpringerLink 等数据库收录! |
|