The MPLS WG Archive

["John Strand" <jls@research.att.com>]

Kireeti,
What's needed is a way for you to ask for a lightpath that's physically
diverse from one or more other lightpaths, whether or not the other
lightpaths have the same terminals as the new lightpath. This is done
routinely at DS3 and (I think) OC-n levels today by PL services like
AT&T's EDRO (Enhanced Diversity Routing Option). There are 2 general
options:
(1) If all the circuits are new, they can be routed simultaneously.
    This is an NP-complete problem and probably would have to be done
    in the management plane. This is essentially the EDRO approach.
(2) To do dynamically (real time) a pragmatic approach would be to request the
    circuits sequentially, one at a time, with each request including
    a requirement that it be diverse from the previously routed ones.
    This ought to be easy to implement algorithmically but won't
    always work (give diverse paths). The problem cases would come if
    (in your example) X and W are close together (same metro), and
     Y and Z are also, and the 2 metros are far apart. Then the 1st lightpath
    routed might inadvertently mess up routing options for the 2nd.

The heuristics to simultaneously route a number of circuits simultaneously
subject to diversity constraints essentially require zillions of calls
to a Dijkstra algorithm and so don't seem to lend themselves to incorporation
in the control plane. (Am I being too pessimistic?) This however is not just an 
Optical Layer problem - the IP layer would have the same computation to do.

I'd be interested in hearing more about the drivers for your example. I would
expect that if you want physical diversity you are setting up lightpaths that
are going to be around for a while. If this is the case would it be OK to take
a little longer (but < 1 minute) to do the provisioning? If so simultaneous
routing ought to be possible. I'd be interested in hearing from control plane
developers their reactions to incorporating an algorithm requiring (say)
10**2 calls to a Dijkstra algorithm on a large (10**3 node) network.

There's a book by Ramesh Bhandari that addresses some of the algorithm issues.
I don't believe that the heuristics used for services like EDRO are in the
public domain though. I have a long-standing interest in these algorithms (I
did the ones used in EDRO) and would be most interested in hearing from people
working in this area.

John

John Strand
AT&T
Lightwave Networks Research Dept.
100 Schulz Drive, Room 4-212
Red Bank, N.J. 07701-7033
(732)345-3255
jls@research.att.com 

-----Original Message-----
From: ip-optical-admin@lists.bell-labs.com
[mailto:ip-optical-admin@lists.bell-labs.com]On Behalf Of Kireeti
Kompella
Sent: Monday, October 23, 2000 1:58 PM
To: kireeti@juniper.net; sc@tellium.com; xuyg@lucent.com; yxue@UU.NET
Cc: ip-optical@lists.bell-labs.com; mpls@UU.NET
Subject: RE: [IP-Optical] RE: Optical link bundling. Was Re:
DraftMinutes From Pittsburgh


> I don't see why TE and protection require the routers to specify explicit
> routes.
> The routers can simply specify to the optical layer what type of optical
> layer protection
> it requires.

Suppose router A wants to get to router B, and wants to take two
different ingress and egress points in the optical domain, X->Y
for the primary LSP, and W->Z for the backup.  A does not require
optical protection for the X->Y path, nor for the W->Z path.  A
*does* require that the X->Y path and the W->Z path do not share
common links.  How is this to be done?

If A did the full path computation, this is simplicity itself.

> Based on its traffic flow a router only needs to know between
> which
> two routers it needs to establish a new lightpath.  How the lightpath is
> routed in the
> optical layer seems to me irrelevant to TE.

It's not up to you or me to say "irrelevant to TE"; the judge of
relevancy is the user (SP), and it depends very much on how
integrated the TE is between the optical domain and the routing
domain.  I know several SPs that would like *in the long term* to
have a tightly integrated TE between the two domains; of course
the majority today prefer loose or no coupling, as that fits their
current mode of operation.

>From an analytical point of view, though, if you define TE as the
mapping of flows to physical links, then it seems to me that how
the lightpath is routed in the optical domain is very relevant.

Kireeti.

_______________________________________________
IP-Optical mailing list
IP-Optical@lists.bell-labs.com
http://lists.bell-labs.com/mailman/listinfo/ip-optical