Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Optimization of Spanning Tree Reconfiguration

IP.com Disclosure Number: IPCOM000114195D
Original Publication Date: 1994-Nov-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 133K

Publishing Venue

IBM

Related People

Bodner, RA: AUTHOR [+5]

Abstract

When a link that was an edge on a spanning tree fails, the spanning tree breaks into two disjoint spanning trees, each of which is termed a spanning tree partition. In order to recombine the two spanning tree partitions back into a single spanning tree (when the link recovers or if there is another parallel link between the two nodes which can be an edge), the rootships of the spanning tree partitions must be moved to the nodes at either end of the failed link. Then the spanning tree algorithm in both nodes must execute the procedure necessary for the spanning trees to combine.

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

Optimization of Spanning Tree Reconfiguration

      When a link that was an edge on a spanning tree fails, the
spanning tree breaks into two disjoint spanning trees, each of which
is termed a spanning tree partition.  In order to recombine the two
spanning tree partitions back into a single spanning tree (when the
link recovers or if there is another parallel link between the two
nodes which can be an edge), the rootships of the spanning tree
partitions must be moved to the nodes at either end of the failed
link.  Then the spanning tree algorithm in both nodes must execute
the procedure necessary for the spanning trees to combine.

      In order to recombine the spanning tree partitions as quickly
as possible and with as few messages as possible, an optimization of
the spanning tree algorithm could be used when it is the case that
parallel links between the nodes at either end of the failed link.
In this case, the spanning tree edge could be locally moved to a
parallel link without moving the spanning tree rootships.

      See (1).  This article describes the spanning tree algorithm,
which is used to discuss the proposed optimization.

This optimization resolves the following issues:
  o  Moving the rootship requires processing at each node that is in
      the path from (and including) the node that was the root of the
      combined spanning tree to the node where the link failed.
  o  The delay created during rootship transfer puts a requirement on
      the new roots that are responsible for repairing the breakage:
      to exchange all topology database information.  This is
required
      since topology databases are dynamically updated and ensures
that
      the two partitions have the most current "picture"  of each
      partition's configuration.  See [2], which describes this
      exchange and issuance of topology information.
  o  Each partition's topology database becomes more outdated from
the
      other's topology database as time passes.  When the partitions
      have remained disjoint for an extended period of time before
      combination begins, the likelihood of performing more write
      operations and issuing more topology database information to
the
      rest of the network increases.
  o  Nondisruptive path switching becomes more intricate since the
      nodes, where the nondisruptive path switching is taking place,
      may not be receiving link utilization information due to the
      partitions.

      A group is defined to be all unidirectional links between two
nodes, which have the characteristics necessary to fit the criteria
for being an edge on the spanning tree.  A potential unidirectional
group is defined to have the following characteristics:
  o  It is a group between one node on the spanning tree and one node
      that is not on the spanning tree, both nodes having the same
  ...