Subject: RE: constraint-based routing algorithms

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

OSPF TE extensions have been proposed to disseminate link bandwidth
information for facilitating distributed traffic engineered route
computation. one important metric for evaluating the efficiency of
constraint-based routing algorithms is reduced path blocking. most of the
algorithms mentioned below (mira, etc.) try to minimize path blocking in an
online routing model. vendors look upon the path computation module of their
MPLS software as proprietary and would not want to reveal the precise
algorithms used. the interest of customers (carriers/ISPs) in such
sophisticated algorithms is also not clear. a case needs to be made for the
direct or indirect translation of efficient routing into network deployment
and operational cost savings. to the best of my knowledge, MPLS
implementations continue to use a simple shortest-hop or shortest-cost (with
user defined cost) based algorithms for path computation. 

--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: Wayne W. Szeto [mailto:[email-masked]]
Sent: Thursday, June 14, 2001 4:14 PM
To: [email-masked]
Subject: constraint-based routing algorithms

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: "Frank Hujber" <[email-masked]>
Date: Fri, 15 Jun 2001 16:47:10 -0400

Can you give a clue as to any public domain documents for these protocols?

Frank Hujber
Alphion Corporation
[email-masked]

---

From: Kireeti Kompella <[email-masked]>
Date: Fri, 15 Jun 2001 14:43:09 -0700 (PDT)

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.