TITLE:   Implementation of The Routing Engine For Hypercycle
         Based Interconnection Networks

AUTHORS: R. Sivakumar, N. J. Dimopoulos, V. Dimakopoulos,
         M. Chowdhury and Don Radvan

IN:      Proceedings of CCVLSI '91, Canadian Conference on
         Very Large Scale Intergration, Kingston, Ont.,
         Canada, Aug. 1991, pp. 6.4.1 - 6.4.7

ABSTRACT

In this work, we present the design and implementation of a
Routing Engine for Hypercycle-based interconnection Networks.
Hypercycles, is a class of multidimensional graphs, which are
generalizations of the n-cube. These graphs are obtained by
allowing each dimension to incorporate more than two elements
and a cyclic interconnection strategy. Hypercycles, offer
simple routing, and the ability, given a fixed degree, to chose
among a number of alternative size graphs. These graphs can be
used in the design of interconnection networks for distributed
systems tailored specifically to the topology of a particular
application. For routing, we have adopted a circuit switching
back-track-to-the-origin-and-retry strategy, whereupon paths
that block at intermediate nodes are abandoned, and a new
attempt is made. Intermediate nodes are chosen at random at
each point from among the ones that form the shortest paths
from a source to a destination. Simulation results have
established the performance for a variety of configurations.
Hypercycles, because of the richness of their connectivity,
exhibit superior performance as compared to Hypercubes both in
terms of throughput and in terms of matching the size/topology
requirements of an application.