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

From: Kireeti Kompella <[email-masked]>
Date: Mon, 18 Sep 2000 20:47:06 -0700 (PDT)

Hi Curtis,

> > 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.

Computing a shortest path with bounded delay is NP-complete.  There
are heuristic algorithms that run in poly time but are approximate.

Note that constraint-based routing is itself trivially undecidable if
the constraint language is expressive enough.  Currently, constraints
are link-local (affinities and bandwidth), which makes the problem
very tractable.

Kireeti.