Subject: constraint-based routing algorithms

From: "Wayne W. Szeto" <[email-masked]>
Date: Thu, 14 Jun 2001 16:13:34 -0400 (EDT)

I have been looking at constraint-based routing algorithms for a while and
the ones that I encountered are all based on minimum interference routing
algorithm (mira), including s-mira, l-mira, lbu (link based utilization
qos routing algorithm), and profile-based routing.  I would like to know
the trend for routing algorithms in MPLS networks.  Are MPLS networks
deployed today or in the near future going to use the simplest routing
algorithm (i.e. minimum-hop)?  Is there any MPLS networks using mira?  or
is there some other more popular algorithms that I'm missing?  Thanks for
any help.

---

From: Bala Rajagopalan <[email-masked]>
Date: Fri, 15 Jun 2001 18:12:27 -0400

Hello,

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

This is an interesting issue. It's usually the case that
the nature of the
path computation algorithm dictates the kind of metrics that
need to be measured/propagated. Given that algorithms are not
standard, we have to potentially allow for the superset
of metrics to be made standard. Also, given that
ultimately it is the service provider (or owner of
the network) who wants to realize a certain result
from path computation (e.g., optimize something),
it is not clear to me
how multiple path computation algorithms can exist
in the same (multi-vendor) network.

It seems like in practice there must be a few commonly
agreed upon path computation paradigms
(e.g., least cost of some type,
with policy constraints) if not algorithms. 
Different vendors may have
their own algorithms to fit the common paradigms,
and a multivendor network operator can 
make sure that different boxes are at least working
on the same objective.

Regards,

Bala

---

From: Hang Liu <[email-masked]>
Date: Fri, 15 Jun 2001 19:31:16 -0400

Hello,

Note that different vendors or network operators may want to use different
algorithms, metrics and/or constraints to compute optimal path in their
networks. Some algorithms, metrics and/or constraints may be only suitable
for certain networks (optical, IP, MPLS, etc.) Moreover, networks are also
divided into AS and areas, which can accommodate this kind of diversity. 

Therefore, instead of standardizing every metric and constraint in the
routing protocols such as OSPF-TE, it is more practical to standardize only
part of commonly used items. Equipment vendors and network operators can use
their private message fields (private opaque LSAs or Sub-TLVs in OSPF-TE) to
distribute the metrics and constraints required for their own algorithms. 

Regards

Hang Liu
Tellium

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

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: [email-masked]
Date: Sat, 16 Jun 2001 11:11:41 +0500

Dear all

      I have a related question on the CSPF. 
      The OSPF extension floods the Traffic Engineering
      data (LSA) on an Area. But if i want to compute a Constraint
      shortest path to the other Area or to the other AS i have 
      to have the TE database of all the area/ all the AS. So can 
      anyone please tell me how it works for the path computation outside
      an Area/Autonomus System ?

Thanks in advance
Ashwin