Browse Prior Art Database

Fully Covered System Interconnect via Edge-Disjoint Rings

IP.com Disclosure Number: IPCOM000116841D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 105K

Publishing Venue

IBM

Related People

Booth, RC: AUTHOR [+6]

Abstract

One way to shorten the propagation delay in large rings is to use multiple smaller rings and rely on switches to perform the routing function from one ring to another. The use of switches provides significant advantages, as it increases both the overall network connectivity and available bandwidth. An additional consideration in ring-based networks is that a switch must behave like a regular node on a ring, to allow frames to pass to a downstream node. It also must permit frames to be routed through to a different ring, as well. The operation to divert the traffic to another ring is referred to in this report as a shortcut. The operation to keep a packet on the ring and pass it to the downstream node is referred to as a bypass. The overhead for a shortcut operation is typically higher than that of a bypass.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Fully Covered System Interconnect via Edge-Disjoint Rings

      One way to shorten the propagation delay in large rings is to
use multiple smaller rings and rely on switches to perform the
routing function from one ring to another.  The use of switches
provides significant advantages, as it increases both the overall
network connectivity and available bandwidth.  An additional
consideration in ring-based networks is that a switch must behave
like a regular node on a ring, to allow frames to pass to a
downstream node.  It also must permit frames to be routed through to
a different ring, as well.  The operation to divert the traffic to
another ring is referred to in this report as a shortcut.  The
operation to keep a packet on the ring and pass it to the downstream
node is referred to as a bypass.  The overhead for a shortcut
operation is typically higher than that of a bypass.  The number of
bypass and shortcut operations that a packet must undertake before
reaching its destination determines the propagation delay in the
network (excluding queueing delay).

      Various topologies for interconnecting switches, such as 2D and
3D torus, single-stage shuffle, butterfly, livefly, and crossbar have
been addressed in the literature.  Most of these topologies are
highly regular, as they can only accommodate a fixed number of nodes
associated with a fixed number of links.  Scalability is not
emphasized in these studies.  Furthermore, these topologies do not
emphasize link utilization, which means that they do not attempt to
optimize bandwidth distribution.

      In this disclosure, we have identified a topology for
ring-based networks which utilizes all available links, while
maintaining a high-degree of scalability.  The topology is based on a
generalized hybrid scheme, which includes N switches with m + n
ports.  The m ports are used to interconnect m buffer-insertion
rings, while the n ports are used for constructing a back-end network
that provides inter-switch connectivity.

      In order to provide a minimum distance between any two switches
(i.e., be able to have a direct connection from one switch to
another), a fully connected back-end network must be provided.  This
would require that n = N - 1.  We provide a methodology for
identifying N  non-overlapping rings (which we call Permuted Rings)
each one interconnecting N - 1 nodes.  If, however, a fully connected
back-end network is not possible (n < N-1) because of technology or
cost considerations (that may limit the size of realizable switching
chips), then a sparsely connected network must be defined.  For this
case, we also provide a methodology which optimizes the distance and
path-availability parameters of the network.

      Methods of Decomposing a Network into Permuted Rings - The
proposed scheme provides a systematic method for the complete
decomposition of a fully connected directed network with either N or
N-1 nodes.  The advantage of this...