Browse Prior Art Database

Fast Communications Network Topology Design Heuristic

IP.com Disclosure Number: IPCOM000102402D
Original Publication Date: 1990-Nov-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 201K

Publishing Venue

IBM

Related People

Cohn, O: AUTHOR [+3]

Abstract

This article describes an algorithm which solves the problems of constructing a backbone network topology for a set of communicating nodes which simultaneously meets performance and reliability constraints and is of low cost. More specifically, given a set of N nodes, and T link types, and an N x N matrix of traffic requirements, and an N x N x T matrix of costs of direct links between the modes, a set of links is constructed with sufficient capacity to meet the traffic requirements, and such that the network remains connected in the presence of up to k link or node failures, for any prescribed k < N. Subject to these restrictions, the algorithm can minimize the cost of the topology.

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

Fast Communications Network Topology Design Heuristic

       This article describes an algorithm which solves the
problems of constructing a backbone network topology for a set of
communicating nodes which simultaneously meets performance and
reliability constraints and is of low cost. More specifically, given
a set of N nodes, and T link types, and an N x N matrix
of traffic requirements, and an N x N x T matrix of costs of direct
links between the modes, a set of links is constructed with
sufficient capacity to meet the traffic requirements, and such that
the network remains connected in the presence of up to k link or node
failures, for any prescribed k < N.  Subject to these restrictions,
the algorithm can minimize the cost of the topology.  In contrast to
existing network design algorithms, this one is fast, takes a global
view of the problem, and incorporates reliability constraint in the
construction process.  The speed of the algorithm makes it possible
to design backbone networks with 200-500 backbone nodes in a
reasonable time frame.

      The standard paradigm for network backbone design uses an
incremental local approach see, e.g.,  l .  Such algorithms are
extremely time consuming, and are impractical for networks of more
than about 30 nodes.  Algorithms which rely on Lagrangean relaxation
of a non-linear optimization problem, e.g.,  2  are also limited in
the number of backbone nodes and usually do not include reliability
in the formulation of the optimization model.  The Mentor algorithm
of  3  is capable of dealing with large numbers of nodes, but does
not include any reliability constraints.

      The input to the algorithm is a set of N nodes, and a set
of T link types (of various capacities).  Expected traffic between
any pair of nodes is specified as an N x N matrix of traffic
requirements.  The cost of a direct link of a given type between two
nodes is specified as an N x N x T matrix of costs.  If no
link of a given type is available between a specific pair of nodes,
the relevant cost matrix entry is left blank.  A set of links is
constructed with sufficient capacity to meet the traffic
requirements, such that the network remains connected in the presence
of up to k link or node failures, for any prescribed k < N.  Subject
to these restrictions, the algorithm attempts to minimize the cost of
the topology.  If no single link is available to meet the required
capacity between two points, multiple links are used.

      The first phase is to simplify the cost structure either by
using a cross section of the cost matrix - using only one link type,
or by constructing a cost estimate matrix based on a weighted
combination of several link types.  This cost estimation procedure is
justified by the (usually) concave and monotonic nature of the
capacity versus cost graph, i.e., increased capacity costs more
money.  The algorithm for constructing a backbone topology, with
connectivity k is a r...