An adaptive routing algorithm for WK-recursive topologies

This paper presents an easy and straightforward routing algorithm for WK-re cursive topologies. The algorithm, based on adaptive routing, takes advanta ge 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 I, two virtual nodes hl-vn(S-D) and hl-vn(D-S) that respectively contain S but not D and D but not S. Such virtual nodes c haracterize other N-d-2 (where N-d is the node degree for a fixed topology) virtual nodes hl-vn(I-SD) of the same level that contain neither S nor D. Consequently, it is possible to locate N-d-2 triangles whose vertices are t hese virtual nodes with property to share the same path, called the self-ro uting path, directly connecting hl-vn(S-D) to hl-vn(D-S). When the self-rou ting path is unavailable to transmit a message from S to D because of deadl ock, 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 al gorithm is able to tolerate up to [N-d(N-d-3)/2 + 1]N-d(l)-1/N-d-1 faulty l inks.