Re: MPLS Inter-area TE requirement draft

Hi Yakov,

At 11:55 AM 1/2/2004 -0800, Yakov Rekhter wrote:
>Jean Philippe,
>
> > Jim,
> >
> > At 07:05 PM 12/31/2003 -0800, Jim Boyle wrote:
> >
> > >JP, so you state that both optimality and scalability are
> > >requirements, yet you acknowledge that there will be trade-offs.  I
> > >believe it is important to prioritize the requirements, so as to best
> > >guide the discussion on the solution.
> >
> > A few comments:
> > - you seem to make the statement that optimal always means non scalable,
> > something I disagree with. Of course, more optimal very likely means more
> > expensive to compute, hence the trade-off I was referring to.
>
>Whether optimality means scalability depends on the problem complexity.
>E.g., for problems with log or (low) polynomial complexity optimality
>need *not* mean non scalable; on the other hand, for NP-complete problems
>optimality certainly *does* mean non-scalable.

fully agree. Here, the potential solution one has in mind (PCS) relies on 
CSPF, although more sophisticated algorithms could be used of course.
By optimal we mean as optimal as in the case of a single area (shortest 
constrained path).

> > - moreover, the notion of scalability of a particular computation solution
> > must be determined based upon specific criteria: implementation 
> efficiency,
> > frequency at which the computation is triggered, computation time, ...
>
>These are useful factors to consider, but we need to keep in mind
>that no amount of implementation efficiency would provide an exact
>(optimal) solution to an NP-complete problem in log or polynomial
>time. (There are approximate algorithms that allow to solve NP-complete
>problems in log or polynomial time, but these algorithms by no means
>provide an optimal solution).

Again I do agree but here we're not thinking about any NP-complete pb, just 
CSPF, not sure why Jim pointed out some potential scalability issue. I 
guess he's thinking about the signalling aspect of a solution providing an 
end to end shortest path.

Thanks.

JP.


>Yakov.