Browse Prior Art Database

Reconfigurable-Metanet: Fault-Tolerant Routing and Flow-Control Mechanism on Locally-Ordered Ring-in-tree Embedding

IP.com Disclosure Number: IPCOM000116074D
Original Publication Date: 1995-Aug-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 6 page(s) / 226K

Publishing Venue

IBM

Related People

Bhandari, IS: AUTHOR [+3]

Abstract

Disclosed is a scheme to use local numbering for the Tree-Embedded Ring (TER) in the MetaNet. Locally-Ordered Ring-in-tree Embedding (LORE) does the following: 1. Preserves the global sense of direction. Hence, desirable properties such as self-routing, etc. are unaffected by the change. 2. Simplifies the design of fault-tolerant techniques because it is not necessary to reach a global consensus for numbering the TER after the MetaNet is reconfigured. Only a topology-maintenance procedure is required, many of which exist. All numbering will simply be computed locally. Messages that were in transit when a fault occurred do not need to be changed. 3.

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

Reconfigurable-Metanet: Fault-Tolerant Routing and Flow-Control Mechanism
on Locally-Ordered Ring-in-tree Embedding

      Disclosed is a scheme to use local numbering for the
Tree-Embedded Ring (TER) in the MetaNet.  Locally-Ordered
Ring-in-tree Embedding (LORE) does the following:
  1.  Preserves the global sense of direction.  Hence, desirable
       properties such as self-routing, etc. are unaffected by the
       change.
  2.  Simplifies the design of fault-tolerant techniques because it
is
       not necessary to reach a global consensus for numbering the
TER
       after the MetaNet is reconfigured.  Only a
topology-maintenance
       procedure is required, many of which exist.  All numbering
will
       simply be computed locally.  Messages that were in transit
when
       a fault occurred do not need to be changed.
  3.  Simplifies the implementation of the MetaNet, because it
       eliminates the need for a virtual numbering that is known
       globally.

This method considers the Metanet where the topology of the network
is arbitrary and all links are bidirectional.  Each node has one or
more full-duplex ports connected to full-duplex links.

      The self-routing on the MetaNet can be based on a logical
embedding of a unidirectional virtual ring over a spanning tree in
the network (Tree-Embedded Ring or TER mode) which will provide
global sense of direction and ensure that packets reach (converge to)
their destinations, in spite of changing and dynamic traffic pattern.

      The links of the bidirectional network are divided into two
types: (i) ring links and (ii) thread links.  The ring links are part
of the virtual embedded ring, and the thread links are all the rest.

      The global virtual embedding provides global sense of
direction, which is used for self-routing.  A packet is routed such
that its distance to its destination always decreases.  The simplest
method of routing is by following the virtual ring, which guarantees
that the packet reaches its destination.  This simple method is, of
course, not very efficient; therefore, our basic routing principles
at every intermediate node is to try to decrease the distance to the
destination as much as possible.  Two basic methods are used:  (i)
short-cuts to a virtual node on the same physical node that is closer
to the destination, and (ii) jumps on threads to a virtual node on a
neighbor physical node, that is closer to the destination.

      The internal flow control in the network is based on a buffer
insertion ring principle.  Under this principle the traffic already
in
the ring has priority to continue on the ring.  Jumps and short-cuts
are possible only if the buffer insertion principle is not violated.

      A major need in network architecture, in general, is a flexible
fault-tolerance in the routing and flow-control.  Faults involves
changing of network topology (...