Browse Prior Art Database

Path Selection Algorithm for Multimedia Traffic

IP.com Disclosure Number: IPCOM000122897D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 98K

Publishing Venue

IBM

Related People

Onvural, RO: AUTHOR [+3]

Abstract

Disclosed is an algorithm that finds a multimedia traffic connection that guarantees that two delay requirements will be met. The delay parameters in question are usually the end-to-end Cell Transfer Delay (CTD) and the jitter. The complexity of this algorithm (which has to be NP-complete in a general case) is a polynomial function of several parameters of the network. One of these parameters is a function of the current network conditions and potentially can be large, but in almost all practical cases it will be small. Consequently, in the overwhelming majority of cases this will be an algorithm of polynomial complexity.

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

Path Selection Algorithm for Multimedia Traffic

      Disclosed is an algorithm that finds a multimedia traffic
connection that guarantees that two delay requirements will be met.
The delay parameters in question are usually the end-to-end Cell
Transfer Delay (CTD) and the jitter.  The complexity of this
algorithm (which has to be NP-complete in a general case) is a
polynomial function of several parameters of the network.  One of
these parameters is a function  of the current network conditions and
potentially can be large, but in  almost all practical cases it will
be small.  Consequently, in the overwhelming majority of cases this
will be an algorithm of polynomial  complexity.

      More formally, the problem is finding a path such that the
following two conditions are satisfied simultaneously:
     <
     P % + % Q % le c sub 1 '   and'
     > lvabove <
     Q % le c sub 2  '   ,'
     >
  where c(1) and c(2) can be any positive values with c sub 1 ge c
sub 2 and P and Q represent the total propagation and queuing delays
along the path, correspondingly.

      The proposed method extends a procedure used in the Networking
Broadband Services (NBBS) architecture (*) In particular, it relies
on the Modified Bellman-Ford (MBF) algorithm.  The MBF method
determines for each number of hops h=1,2, ellipsis ,% and for each
node x in the network, the minimum value D(x,h) of a delay (say, a
CTD) among all paths from source s to this node x consisting of
exactly h hops.  The algorithm stops when an h sub 0 is found such
that D(d,h sub 0 ) lt D sub 0, where d is the destination node and D
sub 0 is the delay constraint.  The D(x,h) matrix is later used to
find an optimal path.

      This path will be "optimal"  in a sense that it will have the
smallest possible delay among the paths that satisfy all other
requirements of this connection.  This can be done for only one kind
of a delay, since the computed D(x,h) matrix contains no information
about the other delays.  The scheme described in this disclosure uses
a somewhat similar technique to collect and store all delay pairs
(CTD, jitter) that correspond to an extremal path (defined below).
Since it is not known which, if any, of the extremal pairs will
belong to an  admissible path, all of them will have to be stored.

      Here is a description of the proposed scheme.  First, a Two
Constraint Modified Bellman-Ford (TCMBF) algorithm is executed.
Unlike the MBF algorithm, described above, the TCMBF algorithm
computes and stores a two-delay matrix (d sub 1, d sub 2, h,x) at
each node x for every value of h.  The d sub 1, d sub 2 values will
represent, correspondingly, the CTD and the jitter on a path from s
to x and will  be extremal in the following sense.  An entry is
stored for a given pair  of (h,x) if and o...