Subject: RE: draft-gray-mpls-rsvp-oif-uni-ext

From: Fong Liaw <[email-masked]>
Date: Mon, 18 Sep 2000 20:13:05 -0700

Hi, Curtis

I certainly believe an optimal solution can be NP-hard,
but if one can satisfied with sub-optimal path that
meet the requirement, this can be done. 
I actually heard ATM switches are doing things in 
this sort. No URLs though. 

I also would appreciate any URL to good path selection 
algorithms, in particular those consider the proposed 
MPLambda attributes, such as risk sharing group, 
protection type, priority, etc.  I thought these 
problems would also be NP-complete or NP-hard :-) 

-Fong

>  -----Original Message-----
>  From: Curtis Villamizar [mailto:[email-masked]]
>  Sent: Monday, September 18, 2000 7:46 PM
>  To: Fong Liaw
>  Cc: Eric Gray; 'Adrian Farrel'; [email-masked]
>  Subject: Re: draft-gray-mpls-rsvp-oif-uni-ext 
>  
>  
>  
>  In message <4D3F9F2BEC58D4118FCE009027B0A662079EA4@ICARIAN>, 
>  Fong Liaw writes:
>  > >  
>  > >  	Yes, the propagation delay object is - as far as
>  > >  I know - wholly new.  It comes from Optical UNI signaling 
>  > >  requirements (draft-bala-mpls-optical-uni-signaling-00).
>  > >  As for what it looks like, it should be straight-forward 
>  > >  since the description is:
>  > >  
>  > >  "6.3.2  Service-Related
>  > >     ...
>  > >     5. Propagation delay: This specifies the maximum acceptable
>  > >        propagation delay in milliseconds.  Defaults to infinity."
>  > >  
>  > >  We will be working with the folks doing the corresponding
>  > >  CR-LDP UNI signaling draft to come up with a reasonably
>  > >  consistent format - give that it should be simple.
>  > >  
>  > >  
>  > 
>  > An alternative way of specifying propagation delay
>  > is to use sub-object in Tspec and AdSep (which is 
>  > what we propsed in the OIF contribution). Use Tspec
>  > and AdSpec has it appeal since the procedure is well 
>  > defined.
>  > 
>  > -Fong
>  
>  
>  Just out of curriousity, am I mistaken or isn't constraint based
>  routing using cummulative delay bound constraints inherently NP-hard.
>  If there is anything in the literature on algorithms please forward
>  some URLs (or other pointers).  Thanks.
>  
>  Carry on.
>  
>  Curtis
>

---

From: Curtis Villamizar <[email-masked]>
Date: Tue, 19 Sep 2000 12:12:24 -0400

> this sort. No URLs though. 

I know of two approaches.  One is apply link constraints and then set
metrics to optimize for delay.  This yields the minimum delay path.
The other is to optimize for other cirteria (like available bandwidth)
and if the path delay cirteria is not met, apply a bias to the metric
proportional to link delay and repeat.  This converges in linear time
(sometimes determining failure) according to the speed at which the
metric bias for delay completely overshadows any administratively set
metric or metric bias for other factors (such as available bw).  The
latter yields a good approximation but it may require a few iterations
rather than a single CR-SPF.

> problems would also be NP-complete or NP-hard :-) 

@INPROCEEDINGS{Kodi0003:Dynamic,
AUTHOR="Kodialam, Murali and Lakshman, T. V.",
TITLE="Dynamic Routing of Bandwidth Guaranteed Tunnels with Restoration",
BOOKTITLE=infocom,
ADDRESS="Tel Aviv, Israel",
DAYS="28--30",
MONTH=mar,
URL="http://www.ieee-infocom.org/2000/papers/460.ps",
}

This also calls for the use of an iterative technique.  Doesn't
considr MPLambda attributes (but the authors are known to be brewing
an internet-draft).

Which MPLambda attributes besides SRLG should be considered.  Pointing
to the drafts would be sufficient.  Naming the attributes that need to
considered would be a bonus.  (Saves me time / provides double-check).

Curtis

ps- thanks to the people who sent private email with advice and
references.  The references are:

Tony Przygienda's thesis (no URL given).

The Zhang/Crowcroft paper?  (no URL given).

Gary and Johnson's book is the canonical reference for NP-complete
problems, if that's of any interest.

... general advice that optimizing one path criteria is polynomial,
more than one NP complete.