Browse Prior Art Database

Dynamically Detecting all Occurences of Duplicate Node Names

IP.com Disclosure Number: IPCOM000115691D
Original Publication Date: 1995-Jun-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 120K

Publishing Venue

IBM

Related People

Bertin, O: AUTHOR [+4]

Abstract

A Spanning Tree (ST) structure is built over a network. This ST contains the minimum number of links such that the network is still connected. By construction, this ST defines a node's partition. Every time a node or a node's partition asks to be connected to an existing network, a join process is started between the two partitions in order to merge the two spanning trees. This process is driven by the roots of each partition and therefore the duplicate node name detection mechanism takes place at the join process time.

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

Dynamically Detecting all Occurences of Duplicate Node Names

      A Spanning Tree (ST) structure is built over a network.  This
ST contains the minimum number of links such that the network is
still connected.  By construction, this ST defines a node's
partition.  Every time a node or a node's partition asks to be
connected to an existing network, a join process is started between
the two partitions in order to merge the two spanning trees.  This
process is driven by the roots of each partition and therefore the
duplicate node name detection mechanism takes place at the join
process time.

      A mechanism to dynamically detect duplicate node names is
described in (*).

      However, all cases are not covered by this mechanism:
overcompensation, undercompensation and node replacement.  This paper
completes the referenced document to give a global solution.

THE JOIN PROCESS CANNOT BE STARTED.

Detection of a real duplicate node name: - NodeA, NodeB and NodeC
comprise one CP spanning tree.

      NodeC receives a Combine Request or a Connection Establishment
message coming from an other NodeA, say NodeA' for clarity in this
discussion.  This message should start a join process, but NodeC
detects that NodeA' is on the same partition than itself and then it
does not answer to NodeA'.

      NodeC puts NodeA' in a "potential" duplicate node name list.

      After a delay sufficient enough to receive any reliable
information about the path between NodeC and NodeA on the CP spanning
tree, if NodeA' is still marked as "potential" duplicate, NodeA' is
considered as a true duplicate node name, and then a Combine Abort
message is issued and an alarm is also sent to the network operator.

Overcompensation:- NodeA, NodeB and NodeC comprise one CP spanning
tree.

The link between NodeB and NodeA goes down.  NodeA becomes the root
of its partition.  NodeC receives from NodeA either a Combine Request
or a Connection Establishment in order to start a join, but NodeC has
not yet received information about link failure between NodeB and
Node A, and then NodeC detects that NodeA is on the same partition
than itself and then it does not answer to NodeA.  NodeC puts NodeA
in a "potential" duplicate node name list.

      In this scenario, NodeA could be marked incorrectly as a
duplicate.  This is why is introduced a delay sufficient enough to
receive any reliable information about the path between NodeC and
NodeA on the CP spanning tree.  Indeed, after the reception of the
information saying that the link between NodeB and NodeA is down,
NodeC detects that NodeA is nomore on the same partition as itself
and then removes NodeA from the "potential" duplicate node name list.
The join process can then proceed.

THE JOIN PROCESS IS STARTED

Undercompensation:- The algorithm may fail to detect a duplicate node
name when information about new nodes in the network does not reach
the root prior to a join with an other CP spanning tree...