Embedding rings in recursive networks

The WK-Recursive network (WKRN) is a hierarchical interconnection network that is recursively defined and has excellent properties for scalable message-passing computer systems. In this paper we describe the ability of a WKRN to implement algorithms that use the communication pattern of rings. We first describe how rings of arbitrary size can be embedded in WKRNs. We then describe how Hamiltonian cycles can he embedded in a WKRN in the presence of up to W-3 faulty links. The existing scheme for fault-tolerant embedding of Hamiltonian cycles tolerates up to [(W-3)/2] faulty edges. Thus, the new scheme for embedding Hamiltonian cycles tolerates twice as many faulty links as the existing scheme