Browse Prior Art Database

Algorithm for Assigning Weights to Links of APPN Networks

IP.com Disclosure Number: IPCOM000106437D
Original Publication Date: 1993-Nov-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 2 page(s) / 105K

Publishing Venue

IBM

Related People

Birman, A: AUTHOR [+2]

Abstract

Disclosed is an algorithms which, given a communicationnetwork consisting of a topology, a set of traffic requirements and a link capacity table, it 1) defines a set of classes of service, 2) associates a class of service with each requirement, and 3) specifies link weights for each class of service. These classes of service and the corresponding link weights are such that when used in an APPN implementation to route the network traffic will produce near optimal traffic flows.

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

Algorithm for Assigning Weights to Links of APPN Networks

      Disclosed is an algorithms which, given a communicationnetwork
consisting of a topology, a set of traffic requirements and a link
capacity table, it 1) defines a set of classes of service, 2)
associates a class of service with each requirement, and 3) specifies
link weights for each class of service.  These classes of service and
the corresponding link weights are such that when used in an APPN
implementation to route the network traffic will produce near optimal
traffic flows.

      APPN [1]  is a virtual circuit based network in which the path
used by a virtual circuit is fixed and lasts for the life of the
corresponding session.  Every traffic requirement is associated with
a class of service.  For a given class of service the route selection
for requirements is performed according to a shortest path algorithm
applied to the set of link weights.  Thus, there is a set of link
weights for every class of service.  The number of classes of service
is limited; usually there are up to eight classes of service.  A
routing is considered optimal if it minimizes the global network
delay.  The optimization problem for a virtual circuit based network
(the VC-optimization problem) is solvable [3,4]  and solutions have
been implemented on some network design tools [2].

      The algorithm below has three main steps.  An initialization
step is followed by an iterative step which attempts to satisfy as
many remaining requirements as possible by creating an additional
class of service.  A set of link weights is created which attempts to
route the requirements in a way similar to the VC-optimal routing.
The step terminates if either all requirements have been satisfied or
if the number of available classes of service has been exhausted.
The third and last step issues a Fail message if there are any
unsatisfied requirements left.  The algorithm follows.

1.  Initialize: mark all requirements as unsatisfied, for all links
    Leftover Capacity equals total link capacity, let the
    Class-of-service be the first.

2.  While not all the requirements are satisfied and the classes of
    service have not been exhausted iterate:

    a.  Derive the VC optimal link flows by invoking VC-optimization
        with Leftover Capacity on links and the unsatisfied
        requirements as active requirements.

    b.  Calculate candidate link weights for the current
        Class-of-service (see below).

    c.  Map the candidate link weights into integers from 0 to 255
        (see below).

    d.  Determine the actual link weights by mapping the integer
        values obtained above to a set of at most eight distinct
        values (see below).

    e.  Determine routes based on shortest paths using the link
        weights above.

    f.  For all requirements not yet satisfied, in order of
       ...