This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on abaptive 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 virual nodes hl-vn(Sd) and hl-vn(Ds) that respectively contain Sbut not D and D but not S.Such virtual nodes characterize other Nd-2(where Nd is the node degree for a fixed topology) virtual nodes hl-vn(IsD) of the same level that contain neither S nor D.Consequently, it is possible to locate Nd-2 triangles whose vertices are these virtual nodes with property to share the same path, calledthe self-routing path, directly connecting hl-vn(SD_ to hl-vn(D_S_. When the self-routing path is unavailable to transmit a message from S to D because of deadiock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proosed communication scheme has the abvantage that1) it is the same for all tjreecpmdotopms;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 fauity links.
展开▼