Subject: RE: constraint-based routing algorithms

From: Sudipta Sengupta <[email-masked]>
Date: Fri, 15 Jun 2001 18:15:27 -0400

kireeti,

i came across a reference to the expired draft you mentioned. would be
interested in having a look. do you have the last revised version ?

we (at tellium) have been looking at path computation algorithms in the
context of diverse routing of primary and backup paths in optical networks.
algorithms like MIRA (lakshman, et al) have recently been proposed for LSP
computation in an online model with the objective of minimizing blocking. 

given the NP-hardness of most constraint-based routing algorithms, there is
always scope for improvement. through standardization efforts of protocol
packet formats (e.g., for TE extensions to topology/resource discovery
protocols like OSPF), the IETF is INDIRECTLY STANDARDIZING the information
model that is available as input for path computation. this information
model could be inadequate for intelligent computation of traffic engineered
paths as algorithmic complexity evolves (dictated by resource utilization
and application needs). for example, in the context of optical networks,
there is a need for multi-dimensional cost metric (link cost and fiber
miles) for computing delay bounded minimum-cost paths. also, information on
the backup bandwidth allocated on a link can be used for efficient
computation of shared backup LSPs. it seems that there is an increased need
for awareness of constraint-based routing algorithms while designing TE
extensions to existing protocols.

given the generality of some of the OSPF-TE drafts (like the one on link
bundling) in use of terminology and applicability to different types of
networks, we have had some confusion in interpreting/mapping the fields in
the context of optical networks. this might hinder the development of truly
"interoperable" implementations. there is probably a need for clear and
concrete interpretation of general drafts for specific underlying transport
technologies like optical mesh networks.

--sudipta

__________________________________
Sudipta Sengupta
Tellium Optical Networking Systems
2 Crescent Place PO box 901
Oceanport, NJ 07757-0901.
Email: [email-masked]
Phone: +1-732-483-2837

-----Original Message-----
From: Kireeti Kompella [mailto:[email-masked]]
Sent: Friday, June 15, 2001 5:43 PM
To: [email-masked]; [email-masked]; [email-masked]
Subject: RE: constraint-based routing algorithms

Note that, unlike "regular" SPF, constraint-based routing is used
for computing source routes.  In regular SPF, if each node were to
compute different paths, one could easily have routing loops.  In
constraint-based routing, each node only needs to ensure that it
doesn't compute a looped path.

Another point is that the constraint-based routing problem can
easily be NP-hard, depending on what constraints are allowed.  So,
there is much scope for heuristics, etc., which could (would) be
considered value-add or even intellectual property.

The first point says that there is no great need to standardize
the algorithm; the second that there is adequate reason to not
standardize it.

What should be reasonably uniform is the semantics of some of the
more common constraints, so that a SP can have at least a rough
idea of how to set the constraints.  Daniel Awduche and I had
once written a draft on this, but it has expired.  It could of
course be resurrected, but only if there is adequate interest.

Kireeti.

---

From: Kireeti Kompella <[email-masked]>
Date: Fri, 15 Jun 2001 16:57:00 -0700 (PDT)

> interested in having a look. do you have the last revised version ?

I've gotten a couple of emails about this; if I get some more, I
will re-post it.

I'll send you a copy off-line.

Kireeti.

---

From: Jing Shen <[email-masked]>
Date: Sat, 16 Jun 2001 15:09:55 +0800

I'd like to got a copy of your draft, would you please do me a favor to
send one ?

Thanks a lot.

James

---

From: "Dmitri Krioukov" <[email-masked]>
Date: Mon, 18 Jun 2001 17:58:37 -0400

I also think that the draft was really useful
and should be resurrected. Its original version
is still available at
http://www.watersprings.org/links/mlr/id/draft-kompella-te-pathcomp-00.txt

I'd suggest to add more references to incremental
Dijkstra and fill in the "NPC" reference (Section 5)
that currently leads nowhere.
--
dima.

> From: [email-masked] [mailto:[email-masked]]On Behalf Of Sudipta
> Sengupta
> Sent: Friday, June 15, 2001 6:15 PM
> To: 'Kireeti Kompella'; [email-masked]; [email-masked]