The MPLS-OPS Archive

[Hani El Sakkout <hani.el-sakkout@parc-technologies.com>]

Norman, 

It's true that integer programming has modeling and scalability limitations
- it's only widely used though because it's easily understood and easily
applied.  

However specialized hybrid search algorithms (involving tight integrations
of more than one solver class) enable practical NP-hard routing problems to
be dealt with effectively, provided the processing timeframe is large
enough.   

It all depends on the timeframe: if you are solving a very simple routing
problem (e.g. bandwidth only) quickly (sub-1s), an SPF/CSPF variant is fine.


The situation is different when the algorithm execution timeframe is greater
and the routing problem is harder (e.g. bandwidth and delay).  A time-frame
of 1s-1000s is acceptable for most backbone operations use-cases (initialize
routing, admit new service, groom routing, repair routing), and also failure
recovery if paths are pre-computed (e.g. pre-configured MPLS TE secondary
paths or FRR paths).

In this situation, a specialized hybrid search algorithm for operations
use-cases yields substantial improvements in (1) the proportion of problems
that can be solved; (2) quality of solutions found; and (3) performance
consistency across similar networks and loads.   

Practical search algorithms can also be built for planning use-cases
(network design) provided the model sensibly restricts the design choices.



Hani El-Sakkout, Ph.D. 
Parc Technologies 


-----Original Message-----
From: nbwaite@attglobal.net
To: mpls-ops@mplsrc.com
Sent: 28/11/03 16:59
Subject: [MPLS-OPS]: CR algorithm

Bhavesh Modi:

Saw your post with:

>    I have 2 questions:
>
>    1. Which are the constraints that are specified ( other
>    than bandwidth ) generally to determine a constrait based
>    route?
>
>    2. Which are the algoriths generally used for determinig
>    a constraint based route?

If the constraints are severe enough, then the problem can get
complicated.  In particular, the problem can be in the class
parts of the research community call 'NP-complete' where 'NP'
abbreviates 'non-deterministic polynomial'.  NP-complete
theory is an extensive topic with some unsolved problems:  In
practice, large NP-complete problems tend to be challenging to
solve, but generally attacks can be successful.  For such
attacks, it is possible to use manual or simple methods, but
it is fair to say that the most powerful attacks are via
'integer optimization'.

As bad as this can be for operations, for design it is worse
because (1) there is much more to design than to operations
(getting solutions for operations is a special case of
design), (2) in operations mostly we just want a solution
using existing deployments while in design we are saying how
to spend money, and (3) operations is concerned mostly with
just the short term while in design we want to consider the
longer term and its uncertainties.

Norman B. Waite, Ph.D.
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

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