Browse Prior Art Database

Fast Optimal Assignment Algorithm

IP.com Disclosure Number: IPCOM000121292D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 150K

Publishing Venue

IBM

Related People

Cohn, O: AUTHOR [+4]

Abstract

Disclosed is an algorithm which optimally assigns link capacities in a communication network for which the traffic flows are given. The objective criterion is to minimize the total cost of the links, subject to a constraint on the average message delay, where capacities are taken from a finite discrete set.

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

Fast Optimal Assignment Algorithm

      Disclosed is an algorithm which optimally assigns link
capacities in a communication network for which the traffic flows are
given.  The objective criterion is to minimize the total cost of the
links, subject to a constraint on the average message delay, where
capacities are taken from a finite discrete set.

      The invention relates to the construction of a design tool for
APPN networks.  Existing solutions to the capacity assignment (CA)
problem assume that any capacity is feasible and the capacity cost
function is linear (see, e.g., [1]). In practice, the feasible
capacities are within a discrete and finite set which are
location-dependent.  For every two nodes in the network, feasible
capacities and costs may be different.  The common practice to
circumvent this complexity is to solve the continuous optimization
problem first, and then to take the closest feasible solution, a
heuristic approach that may result in expensive networks. Proposed is
a fast algorithm for the CA problem in the most general set up, which
converges in practice within 30 iterations, and finds the optimal
capacities most of the time.  In cases where it does not converge to
the optimum, it yields a solution which is close to it and provides
the difference to the optimal cost.  The algorithm is suitable for
networks of around two thousand nodes.  Today, link capacities and
their tariff are subject to constant changes and, as high bandwidth
will become more common, link capacities will become available for
the users on a demand basis and for short terms, e.g., for minutes or
hours, they would become feasible by sharing a high bandwidth trunk
among many networks.  A network may save on its operation cost by
dynamically allocating its link capacities, not just once when
designing/redesigning the network.  The capacity assignment algorithm
should then be executed dynamically and be integrated into the
network architecture.

      The inputs to this algorithm consist of the following:
  *  The set of network links {1,2,...,N}.
  *  The corresponding traffic flows in each direction j, j = 1, 2
(in bits/sec), {Xj1, Xj2,..., Xjn}.
  *  The feasible carrier types (Voice grade, D2400, etc.) Ci, 1 & i
& N.
  *  The link cost tables, COSTi(c), c e Ci .  The value COSTi(c)
represents the monthly cost of using capacity c for link i, where the
cost combines the monthly cost and the installation cost divided into
the number of months in the planning horizon.
  *  The total message generation rate in the network y.
  *  The average message delay constraint T.
  *  A user-defined parameter MAX_MULT - maximal link multiplicity.

      The outputs of the algorithm are the optimal capacities of
every link in the network.

      In the preparation part of the algorithm every set Ci is
extended to include every combination of 1 & K & MAX_MULT carrier
types that have sufficient capacity to support the flo...