The MPLS-OPS Archive[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index][Thread Index][Author Index][Subject Index] RE: CR algorithm
Hi, my 2 euro cents contribution : like mentionned Hani, there is several ways to solve scalability issues raised by such contraints complexity. Hybrid algorithms are really powerfull as he mentionned. Another interesting approach is introduction of Heuristics simplifications. If you know what will be the application field of your algorithm, there as several "shortcuts" you can implement. Result will be reducing the size of the search tree, and so improved scalability. in the algorithm we're working on, by introducing fair heuristics we could reduce optimization time from several days to 3 minutes, by loosing only 4% on solution optimality. we also built on top of initial Dijkstra algorithm 4 extra constraints with less than 5% perf decrease thanks to hybrid approach and several heuristics shortcuts. kr, seb. -----Original Message----- From: Hani El Sakkout [mailto:hani.el-sakkout@parc-technologies.com] Sent: vendredi 28 novembre 2003 21:40 To: 'mpls-ops@mplsrc.com ' Subject: RE: [MPLS-OPS]: CR algorithm 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 ------- The MPLS-OPS Mailing List Subscribe/Unsubscribe: http://www.mplsrc.com/mplsops.shtml Archive: http://www.mplsrc.com/mpls-ops_archive.shtml
|
|