Browse Prior Art Database

Efficient Protocols for Initial Topology Exchange

IP.com Disclosure Number: IPCOM000103931D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 91K

Publishing Venue

IBM

Related People

Bodner, RA: AUTHOR [+9]

Abstract

In many communication networks, each node is responsible for distributin information about the state of the node and its local links to the other nodes in the network. This information, called a topology update, is used to dynamically update a representation of the network's topology (i.e., nodes and links) that is replicated at every node. This representation is termed the topology database.

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

Efficient Protocols for Initial Topology Exchange

      In many communication networks, each node is responsible for
distributin information about the state of the node and its local
links to the other nodes in the network.  This information, called a
topology update, is used to dynamically update a representation of
the network's topology (i.e., nodes and links) that is replicated at
every node.  This representation is termed the topology database.

      Described is an efficient algorithm to be used when two network
partitions need to exchange topology information about their
respective partitions, while combining the partitions into a single
network with a merged topology database.  The amount of topology
information exchanged can be very large, and some of the information
may be redundant if the two partitions were previously connected.
The algorithm described here provides a means to determine the
minimum topology information that needs to be propagated in each
partition, and a means to check the integrity of the topology
information being exchanged.

      This algorithm assumes that each node has a single sequence
number space it uses to assign sequence numbers for all topology
updates that it creates.  The sequence number is used by the
algorithm to determine the integrity of the topology information.

      It is also assumed that when the two network partitions decide
to combine, they agree on the link that will connect the two
partitions.  This link must connect two nodes, one in each partition.
Each of these nodes sends to the other node its copy of the topology
database that describes its partition.  Upon receipt of the other
node's topology database, each node examines each record and
determines whether the record contains new, old, or inconsistent
information.  Records containing old information are ignored.  Those
records that carry new information are propagated to the node's own
partition using topology updates.  Those carrying inconsistent
information trigger topology updates to one or both partitions in
order to request more accurate information from the nodes owning the
resources associated with the records.

The following routine determines which records trigger topology
updates to both partitions:

o   If the node has a corresponding record already stored in its
    topology database (parts of the partitions were previously
    connected):

o   If the received record does not describe a resource owned by the
    node:

o   If th...