The MPLS-OPS Archive

[nbwaite@attglobal.net]

Manoj,

For your

>    I am trying to simulate a resource provisioning and
>    control in MPLS domain.
>
>    For this, I want to use Dijkstra's algorithm to find all
>    source-destination shortest path on a given network
>    topology, then map that to a LP problem to be solved
>    using a LP solver which takes input in MPS format. So, I
>    will be using AMPL to convert LP format to MPS format in
>    between. After LP solver gives the result, I will take
>    the output and feed to my algorithm to optimize the
>    network resource utilization.
>
>    Does anyone knows of a tool which takes topology as input
>    and provide a all source-destination shortest paths in a
>    fashion so that it will be easy to convert to LP problem.
>
>    Any tips will be of great help.

at the beginning, you lost me:  If you want all network
shortest paths, fine.  And, sure, can use E, Dijkstra's
algorithm.  Once you have done that, then you have the paths.
So, then, why work through AMPL, LP, MPS, and an LP solver?

If you have some software for Dijkstra's algorithm, then just
use it directly.  Otherwise, it sounds to me like you do want
the shortest paths but should set aside Dijkstra's algorithm
and just work with linear optimization ('linear programming')
specialized for network flows.

Min cost capacitated network flows is a special case of linear
optimization.  Further, if the arc capacities are all integer,
then there is an optimal solution with all the flow amounts
integer, and the simplex algorithm of linear programming will
give this solution just by starting with an integer solution.
That is, starting with an integer basic feasible solution, the
simplex algorithm will find only integer basic feasible
solutions until it has found an optimal basic feasible
solution, and one with all the non-zero reduced costs with the
same sign (dual feasibility).

Further, for such a flow problem, there is a specialized
version of the simplex algorithm, e.g., as in

     W. H. Cunningham, "A Network Simplex Method",
     'Mathematical Programming', Volume 11, pages 105-116,
     1976.

and here there is a clever anti-cycling algorithm.  The key
point of the network simplex algorithm is, just applying the
simplex algorithm to a network flow problem, each simplex
basic feasible solution is a spanning tree of arcs in the
network; then, one iteration of the simplex algorithm consists
of adding some one non-basic arc to the tree, running flow
around the resulting circuit to save money, and removing from
the basis an old arc whose flow first goes to zero.  This fact
was noticed likely in the 1950s; Cunningham's modification is
for an easy way to avoid cycling.

For a 'solver' such as, say, the IBM OSL, the network simplex
algorithm part of what is provided.  There is some
documentation from IBM but also in

     Ming S. Hung, Walter O. Rom, Allan D. Waren,
     'Optimization with IBM OSL', ISBN 0-89426-244-0, Boyd &
     Fraser Publishing, Danvers, MA, 1994.

as well as on an IBM Web site.

Here you will likely have to write a little Fortran or C to
read in the definition of your topology, but you will be
calling the optimization subroutines directly and will not
need to work with MPS (MPS is clumsy -- you also will not need
AMPL).  One advantage of the network simplex algorithm is
speed:  It is much faster than using a general purpose linear
optimization code.

By writing a little Fortran or C code, you get to define your
own topology file -- you get to use a definition that is easy
for you to work with.  For a start, just look at what your
(OSL or whatever) wants for input.

For using network flows to find all shortest paths, looks like
one approach would be, for n edge 'source' nodes, have an arc
entering that node with flow n - 1 and for each of the other n
- 1 edge nodes, each regarded as a 'sink', have arc capacity
1.  For all intermediate arcs, have capacity, say, n which
will never be achieved.  For the arc costs, have distance,
just 1, or whatever you have in mind to minimize (the arc
costs are all >= 0, right?).

Here you have just some one 'commodity' being sent from one
source node to n - 1 sink nodes.  So, this is not an integer
multicommodity network flow problem.

Then solving this one commodity network flow problem should
give you n - 1 of the flows you want.  Some intermediate arcs
in your topology may have flows of 10, 20, or whatever, but it
should be easy enough to determine all the n - 1 individual
flows.  Indeed, the final optimal basic feasible solution will
determine a spanning tree on your network.

Do this n times, and you are done.  For each of the other n -
1 times, you have the same problem but are just changing flows
at two of the edge nodes.  That is, the node that was the
source now becomes a sink, and some other node that was a sink
now becomes the source.  So, just restarting the optimization
with these two changes and from the last optimal solution
should yield a new optimal solution quickly.

If you want guaranteed 'polynomial' performance, then use,
say, the polynomial network flow algorithm in

     Dimitri P. Bertsekas, 'Linear Network Optimization:
     Algorithms and Codes', ISBN 0-262-02334-2, MIT Press,
     Cambridge, MA, 1991.

There is a story that this algorithm was originally developed
for a guaranteed fast way to assign ABM warheads to incoming
ICBMs.

But, the network simplex algorithm as provided in, say, the
OSL should be plenty fast and reliable enough.

Alas, it is not clear that all the network shortest paths is
all you need for MPLS design, but that is another subject.

Norman B. Waite, Ph.D.
Founder
Network Architectonics
9 Fox Run
Wappingers Falls, NY 12590
nbwaite@attglobal.net
845-227-7821

-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml