Browse Prior Art Database

Hybrid Topology Database Algorithm

IP.com Disclosure Number: IPCOM000110284D
Original Publication Date: 1992-Nov-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 122K

Publishing Venue

IBM

Related People

Ahmadi, H: AUTHOR [+3]

Abstract

The Topology Database in a network contains information such as utilization levels or bandwidth allocation on links of each node in the network. This information (called link metrics in this article, and used to compute the bandwidth allocated on a link) is of use to network control functions such as path computation, call screening, etc. Therefore, a network node not only monitors its link metrics, but it also broadcasts them to other network nodes so that they maintain up to date information about all network links. Up to date information is key when, for example, dynamically computing paths for new connections. This article describes when and how a broadcast of a node's link metric vectors should take place.

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

Hybrid Topology Database Algorithm

       The Topology Database in a network contains information
such as utilization levels or bandwidth allocation on links of each
node in the network.  This information (called link metrics in this
article, and used to compute the bandwidth allocated on a link) is of
use to network control functions such as path computation, call
screening, etc.  Therefore, a network node not only monitors its link
metrics, but it also broadcasts them to other network nodes so that
they maintain up to date information about all network links.  Up to
date information is key when, for example, dynamically computing
paths for new connections.  This article describes when and how a
broadcast of a node's link metric vectors should take place.

      Perfect knowledge of load information on all network links
would require both the triggering of broadcasts after adding or
removing a single network connection on any link and the
instantaneous receipt of this information by all nodes (the latter
being prohibited by the laws of physics).  Such an approach would
clearly induce an unrealistic processing load on nodes as they would
have to process a huge number of updates.  The goal of the link
metric update policy is, therefore, to provide accurate information
on link loads while keeping the number of updates under control.

      The accuracy needed in link metric updates needs to be high,
especially at high loads, where inaccuracies will be magnified in
link length computations.  However, a high accuracy implies a high
frequency of updates, which at high loads may result in a very large
number of updates (i.e., transition rates are high).  This points to
a potential problem in having event-driven, asynchronous updates.  A
periodic (synchronous) update policy is, therefore, preferable, as it
bounds the frequency of updates.  However, in cases of large changes
in the link metrics, the disadvantage of periodic updates is that the
distribution of this important information will typically be delayed.

      In order to avoid the possibility of too many updates, while
ensuring rapid distribution of critical load information, we propose
a hybrid policy combining event-driven and periodic update
strategies.  Each network node maintains current link metric vectors
for all its intranode links and outbound transmission links.  This
information is kept separate from the topology database; the local
copy of the topology database reflects the most recent update sent.
The algorithm used to decide when and if to send updates is based on
a monitoring interval of duration Tu and two constants, wkl and Wkl,
which are defined as fractions of the link capacity, where Wkl wkl.
The under lying idea behind the algorithm is to...