Ring configurator for system interconnection using fully covered rings

Abstract

A ring configurator for interconnection of data processing and communication systems uses fully covered rings. The ring configuration mechanism can be used to construct a set of covering rings preserving full connectivity for system interconnect. The mechanism can also be used for establishing the routing table for each interconnected system during the system initialization time. To generate a set of edge-disjoint rings, a rotational mechanism is used. The rings are considered stretching along a horizontal direction with nodes aligned in columns across all the rings. With a proper relabeling of the nodes, nodes appearing in the same column position of each ring can be obtained by a simple rotation of the nodes from the previous column of the rings. Once the rotational position is determined for each column, a set of N-1 edge-disjoint rings can be constructed. To find an extra ring so that when combined with the N-1 rings thus found the ring constraints are satisfied, a node reduction technique is invoked. The procedure can be repeated until a set of N edge-disjoint rings satisfying the constraints are found.