TY - JOUR
T1 - Augmented ring networks
AU - Aiello, William
AU - Bhatt, Sandeep N.
AU - Chung, Fan R.K.
AU - Rosenberg, Arnold L.
AU - Sitaraman, Ramesh K.
PY - 2001/6
Y1 - 2001/6
N2 - We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRNs) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d - 1) multiring. 3) Every depth-d multiring M can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of M resides at a corner of the mesh. 4) Every depth-d HRN H can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of H resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRNs that are asymptotically tight for large N and d.
AB - We study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only modestly. Chordal rings add "shortcut" edges, which can be viewed as chords, to the ring. Express rings are chordal rings whose chords are routed outside the ring. Multirings append subsidiary rings to edges of a ring and, recursively, to edges of appended subrings. Hierarchical ring networks (HRNs) append subsidiary rings to nodes of a ring and, recursively, to nodes of appended subrings. We show that these four modes of augmentation are very closely related: 1) Planar chordal rings, planar express rings, and multirings are topologically equivalent families of networks with the "cutwidth" of an express ring translating into the "tree depth" of its isomorphic multiring and vice versa. 2) Every depth-d HRN is a spanning subgraph of a depth-(2d - 1) multiring. 3) Every depth-d multiring M can be embedded into a d-dimensional mesh with dilation 3 in such a way that some node of M resides at a corner of the mesh. 4) Every depth-d HRN H can be embedded into a d-dimensional mesh with dilation 2 in such a way that some node of H resides at a corner of the mesh. In addition to demonstrating that these four augmented ring networks are grid graphs, our embedding results afford us close bounds on how much decrease in diameter is achievable for a given increase in structural complexity for the networks. Specifically, we derive upper and lower bounds on the optimal diameters of N-node depth-d multirings and HRNs that are asymptotically tight for large N and d.
KW - Chordal rings
KW - Diameter trade-offs
KW - Express rings
KW - Graph embedding
KW - Grid graphs
KW - Hierarchical ring networks
KW - Multirings
KW - Ring networks
UR - http://www.scopus.com/inward/record.url?scp=0035364160&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035364160&partnerID=8YFLogxK
U2 - 10.1109/71.932713
DO - 10.1109/71.932713
M3 - Article
AN - SCOPUS:0035364160
SN - 1045-9219
VL - 12
SP - 598
EP - 609
JO - IEEE Transactions on Parallel and Distributed Systems
JF - IEEE Transactions on Parallel and Distributed Systems
IS - 6
ER -