Browse Prior Art Database

Algorithm to Monitor Connectivity in a Network with Topological Instabilities

IP.com Disclosure Number: IPCOM000118894D
Original Publication Date: 1997-Aug-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 5 page(s) / 178K

Publishing Venue

IBM

Related People

Scotton, P: AUTHOR [+3]

Abstract

An elementary problem in graph theory is to determine whether or not a path exists between a pair of vertices in the graph. The question arises in a wide range of graph analysis problems, where the task is not to determine the shortest path or the optimal path based on some predefined cost function but simply to determine if connectivity exists between two vertices in the graph. Our principle interest is not the solution of this particular problem for a given graph of fixed topology since a number of well-known "classical" techniques may be used to solve this problem. This disclosure presents an efficient solution that addresses the situation where the graph topology is continually changing due to the addition or removal of vertices and/or edges. The addressed problem may be stated as follows.

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

Algorithm to Monitor Connectivity in a Network with Topological Instabilities

      An elementary problem in graph theory is to determine whether
or not a path exists between a pair of vertices in the graph.  The
question arises in a wide range of graph analysis problems, where the
task is not to determine the shortest path or the optimal path based
on some predefined cost function but simply to determine if
connectivity exists between two vertices in the graph.  Our principle
interest is not  the solution of this particular problem for a given
graph of fixed topology since a number of well-known "classical"
techniques may be used  to solve this problem.  This disclosure
presents an efficient solution  that addresses the situation where
the graph topology is continually changing due to the addition or
removal of vertices and/or edges. The  addressed problem may be
stated as follows.  Given that a path is known  to exist, or not
exist, between a particular vertex and any other vertex  in a graph,
how can changes in the connectivity be efficiently determined  when a
single edge is added or removed.

Current Connectivity Monitoring Techniques

      The principle problem of using classical techniques (1, 2) for
monitoring connectivity is that they are intended for finding an
optimal path between two vertices, subject to specified cost
constraints. This  intent dictates the form of the algorithms used.
Thus, even if one tries to simplify them to merely monitor
connectivity, they still exhibit  a complexity of order O(n sup 2),
where 'n' is the number of vertices in  the graph.

      An additional limitation is that classical algorithms should be
used on "topologically stable" graphs.  At every topological change,
when the connectivity has to be determined, the algorithm must be run
on the entire graph.  It is worth mentioning that advanced techniques
(e.g., incremental spanning trees or graph sparsification (3)) may be
used to perform an incremental evaluation.  However, these techniques
are very sophisticated and far beyond the scope of simple
connectivity monitoring.

Proposed Algorithm

The proposed algorithm attempts to establish connectivity between a
particular vertex, or Root vertex, and all of the other vertices in
the graph through the use of a colored connectivity tree.  Each
branch originating from the Root vertex is assigned a unique color.
All of the  vertices whose connectivity is obtained from that branch
are assigned to  that color.  Any vertices to which connectivity
cannot be obtained are  colored None.

      In addition to its color, each vertex to which connectivity has
been established is assigned a distance value.  This value is the
number of hops to this vertex from the Root vertex along the branch
from which  connectivity is obtained.  Both the color and distance
attributes are demonstrated in Fig. 1.  Note that not all of the
edges are on the connectivity tree.

      When a n...