Browse Prior Art Database

Mesh Network Topological Optimization And Routing

IP.com Disclosure Number: IPCOM000120519D
Original Publication Date: 1991-May-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 3 page(s) / 99K

Publishing Venue

IBM

Related People

Grover, GA: AUTHOR [+3]

Abstract

This article describes an algorithm for determining an initial topology for a mesh network given the cost of internode connections and the internode traffic volumes.

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

Mesh Network Topological Optimization And Routing

      This article describes an algorithm for determining an
initial topology for a mesh network given the cost of internode
connections and the internode traffic volumes.

      The overall plan is to send traffic over a direct route between
the source and destination whenever the magnitude of the requirement
is sufficiently large and to send it via a path within a tree in all
other cases.

      The tree is determined by the following heuristic which is a
modification of Prim's MST Algorithm and, like Prim's Algorithm, has
a complexity of order N squared.

      Given a node, C, which is the center (defined below) of the
network, we start with C in the tree and all other nodes outside the
tree.  For all links (i,j) with i in the tree and j outside the tree,
we define L'(i,j), a modified length for (i,j), as the original
length of link (i,j) plus P (defined below) times the distance from j
to C (through the part of tree already defined).

      P is a parameter whose value is between 0 and 1.  For P equal
0, we ignore path length and simply find a MST; this is Prim's
Algorithm exactly.  As P increases, we give more consideration to
using links which help create a path directly towards C and thereby
reduce the total path length in the tree.  When P is 1, and the
distances obey the triangle inequality as we are assuming, a star
around C will result.  Our experiments to date indicate that moderate
values of P, between .3 and .5, yield trees with the desired
characteristics.

      The center node, C, is found by computing a figure of merit for
each node, i, as the sum over all nodes j of the distance from i
to j times the total traffic to and from j. We refer to the total
traffic to and from a node as its weight.  The node with the smallest
figure of merit is then chosen as center.  Note that this node has
the virtue of being the node which would serve as the center of a
star network minimizing the total path length over all star networks;
this is often a reasonable approximation to the optimal
path-minimizing tree.

      The next step is to identify direct links which can be
justified by the magnitude of the requirements between their end
points.  Thus, if a link has capacity A and we have accumulated a
requirement greater than or equal to UA (where U...