Browse Prior Art Database

Traffic Redirection Technique in Multi-Speed Network Design

IP.com Disclosure Number: IPCOM000122259D
Original Publication Date: 1991-Nov-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 4 page(s) / 195K

Publishing Venue

IBM

Related People

Chang, PC: AUTHOR [+3]

Abstract

This article presents a traffic redirection technique for network topology design with multiple choices of linktypes. It substantially reduces the algorithm complexity by allowing the use of any single- speed design algorithm as a building block. The results show significant improvements in both cost and reliability.

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

Traffic Redirection Technique in Multi-Speed Network Design

      This article presents a traffic redirection technique for
network topology design with multiple choices of linktypes. It
substantially reduces the algorithm complexity by allowing the use of
any single- speed design algorithm as a building block. The results
show significant improvements in both cost and reliability.

      We consider the network design problem of finding minimum cost
mesh network topologies given point-to-point requirements and a
matrix specifying the cost of links between each pair of nodes.  Most
comparably fast existing algorithms for the solution of this problem
use a single-speed link throughout the network, e.g., MENTOR [*]. In
general, however, it may be advantageous to use different speed links
within the topology.

      One possibility for solving the multi-speed network design
problem is to simply augment the basic single-speed algorithm with a
trimming routine as a post process which assigns an appropriate
capacity to each link.  However, while this is an improvement over
the original algorithm, significantly more can be gained by
explicitly considering different link speeds in the original design
process.
Traffic Redirection Technique

      We introduce a traffic redirection technique which allows a
multiple level design in which each level can use the original
single-speed design algorithm while useful intermediate results are
passed to next levels by the form of reorganized traffic
requirements.  The multi- speed design algorithm we use here is a
general procedure which works with any single-speed design algorithm.
It consists of multiple levels. Within each level a single-speed
design procedure is used to obtain a network topology based on a
specific link speed corresponding to this level.  This algorithm
starts from the highest link speed and proceeds to lower speed link
types. The algorithm iterates two procedures, the in-level procedure
and the inter-level procedure, considering each type of link.  The
in-level procedure can be any single- speed design algorithm, e.g.,
MENTOR.  The function of the inter-level procedure is to reorganize
the input data for the next level based on the results of the current
level so that the same design procedure can be used for all types of
links.

      The inter-level procedure starts with a topology which is
designed based on the highest speed link available.  The topology is
first checked and only the cost effective parts of this topology are
retained and passed to the next level. The qualified parts include
those nodes selected as backbone nodes in this level and those links
with traffic flows justifying high-speed links.  The retained
backbone nodes are made mandatory backbone nodes in the next level,
i.e., these nodes must be chosen as backbone nodes unconditionally at
the next level.  The retained high-speed links, however, are not
passed to the next level directly.  In...