Performance evaluation of the backtrack-to-the-origin-and retry routing for hypercycle-based interconnection networks

• Main Authors: Dimopoulos, N.J., Radvan, D., Li, K.F.
• Format: Conference Proceeding
• Language: English
• Subjects: Computational modeling; Computer networks; Embedded computing; Hypercubes; Joining processes; Message passing; Multidimensional systems; Multiprocessor interconnection networks; Network topology; Routing
• DOI: 10.1109/ICDCS.1990.89258

Hypercycles, a class of multidimensional graphs that are generalizations of the n-cube are presented. 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 choose among a number of different 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. A back track-to-the-origin-and-retry routing, whereby paths that block at intermediate nodes are abandoned and a new attempt is made, is presented. Intermediate nodes are chosen at random at each point from among those that form the shortest paths from a source to a destination. Simulation results that establish the performance of a variety of configurations are presented. An initial attempt at constructing a hypercycle-based router is discussed.< >