Subject: minimising wavelength conversion in MPLambdaS systems

From: John Hopkins <[email-masked]>
Date: Mon, 31 Jan 2000 16:27:13 -0000

Hi All,

	I have been considering label(lambda) allocation in MPLmS systems supporting wavelength re-use. 

	One issue is how to minimise the number of nodes along a lambda-switched lightpath where wavelength conversion occurs (or alternatively how to maximise the number of nodes though which the lightpath can traverse transparently). 

	Another issue is how to determine the most appropriate lambda to use for a particular lightpath, and wether lambda-assignment should be integrated with the process of determing a route for the LmSP, or be a follow-on activity from determing the route. Maxmimum lambda-reuse in the network would be a goal in order to support more LmSPs than the number of available wavelengths.

	In ordinary MPLS, LSRs swap input and output labels and it is assumed that there is negliable cost in changing an input label (e.g. VPI/VCI) to an output label. When a wavelength is used as a label, lambda-swapping between different lamba-in and lambda-out implies a wavelength conversion device, which is a scarce resource. In future all optical networks, wavelength conversion will very likely be required at some locations, such as Optical Cross Connects (OXC) sites. However in simpler ring-based optical networks where an optical path may traverse a number of relatively low-cost Optical Add-Drop-Mux (OADM) devices it is very advantageous if the same wavelength can be used along an entire lightpath traversing many nodes transparently (i.e. with the same lambda-in and lamba-out). Even in OXC or OADM systems supporting wavelength conversion, it is desirable to use it sparingly.

	This would require that the source node has either :-
	a) the knowledge of other nodes' optical switching limitations (e.g. advertised lambda add/drop/passthru range), AND the currrent status of other nodes'  wavelength usage. This is the information needed by a source node to compute the most appropriate lambda for the lightpath (e.g. using minimal number of required wavelength conversions as one constraint), or 
	b) there is some type of crankback mechanism in MPLmS LDP which can be invoked when one node on the setup path discovers that the lightpath cannot be established because the initial lambda allocated for the lightpath by the source node is already in use by another lightpath at that node, or
	c) require that each OADM node supports wavelength conversion (ugh) so that blocking can be avoided by a wavelength conversion.

	I prefer the 1st approach for a ring-based network, complemented by wavelength conversion at OXC sites between rings. One possible soultion would invlove the following :-

	1) a distributed wavelength usage database for the optical domain (so that source nodes have the information to compute a lambda that will not lead to blocking on the lightpath)
	This could involve protocol support to distribute wavelength usage status updates between all MPLmS aware nodes in an optical domain, possibly piggybacking these status updates in IGP protocol messages. The idea would be that each node periodically (or following changes in lightpath topology) sends status updates describing wavelength allocation on its interfaces. (One issue is how to keep this information up to date.) If this information is received by all nodes in an optical domain (such as a ring), then all nodes in the domain have a domain-wide view of lightpath assignments and lambda usage and are in a position to compute 'optimal' routes and lambda-assignments for new lightpaths. That is to say they would be in a position to compute a non-blocking shortest lightpath with minimal (hopefully zero) requirement for wavelength conversion. Either these two processes could be seperate (e.g. route determination firstbased on shortest-path, followed by lamnda-assignement) or the!
!
!
!
y could be integrated in a multiple-constraint search for non-blocking path.

	2) a  wider distribution of lambda-range advertisements than just neigbour-to-neighbour . 
	Basic MPLS LDP initialisation supports the exchange of this information between adjecent LSRs which is fine if all nodes can swap labels. However this won't work when non-adjacent ingress/egress nodes are the only ones add/dropping the lambda, and there is a desire for the intervening transit nodes to pass the lambda through transparently. Without this information about distant nodes, there is a danger that a lambda-could be assigned for a lightpath that is non-blocking at all intervening nodes, but which can't be dropped by the egress node because it is outside its advertised lambda-range. A possible solution is extension of the LmDP initialisation phase to broadcast/flood lambda-range advertisements to all nodes in a domain. This then allows a source node to know the lambda-swapping limititations of all the nodes through which a lightpath may traverse, and take this into account when establishing the route and lambda that the lightpath should use. Note that this is only nec!
!
!
!
essary if nodes on the path have differing capabilities, e.g. can add/drop different subsets of the complete range of lambdas supported in a network, but this may be a likely situation.

	Any thoughts?

	John Hopkins

---

From: "Alexander Marhold" <[email-masked]>
Date: Mon, 31 Jan 2000 19:18:32 +0100

John !

What you describe in 1)
> 	1) a distributed wavelength usage database for the
> optical domain (so that source nodes have the information to
> compute a lambda that will not lead to blocking on the lightpath)
> 	This could involve protocol support to distribute
> wavelength usage status updates between all MPLmS aware nodes
> in an optical domain, possibly piggybacking these status
> updates in IGP protocol messages. The idea would be that each
> node periodically (or following changes in lightpath
> topology) sends status updates describing wavelength
> allocation on its interfaces.

for me your algo looks quite similar to traffic engineering in
normal MPLS where the tunnelheadend knows the topology,
gets reservation status via ISIS or via OSPF and establishes a path
via RSVP.
If you take one priority per wavelength and a fictive bandwidth of 1
and a reservation of 1, the headend has the almost the same task as
in traffic engineering,only he is not allowed to kickoff another tunnel
and he has to look from priority 1 to n to find a possible path through
the network.
Different is that the priority equals to the label value which is then
the same for the whole path.
So eventually using a Virtual Switch Controller and the VSI-interface to
the OXC a pretty similar algo as in traffic engineering can be used to
find a path through the network. The VSC´s could be connected either via
the outband network or via one "control" wavelength.

When in near future wavelength conversion on the fly is easier the algo can
be extended to use that possibility.

regards
Alexander

__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/__/
     __/
    __/   Dipl.Ing. Alexander Marhold MBA
   __/   CCIE #3324, CCNP, CCNA, CCDP, CCDA, CCSI #20642
  __/   PRO IN <Senior Consultant, PM and Trainer>
 __/   Mobile: ++43-(0)664-16 28 234
__/

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On Behalf Of John
> Hopkins
> Sent: Monday, January 31, 2000 5:27 PM
> To: [email-masked]'
> Subject: minimising wavelength conversion in MPLambdaS systems
>
>
> 	Hi All,
>
> 	I have been considering label(lambda) allocation in
> MPLmS systems supporting wavelength re-use.
>
> 	One issue is how to minimise the number of nodes along
> a lambda-switched lightpath where wavelength conversion
> occurs (or alternatively how to maximise the number of nodes
> though which the lightpath can traverse transparently).
>
> 	Another issue is how to determine the most appropriate
> lambda to use for a particular lightpath, and wether
> lambda-assignment should be integrated with the process of
> determing a route for the LmSP, or be a follow-on activity
> from determing the route. Maxmimum lambda-reuse in the
> network would be a goal in order to support more LmSPs than
> the number of available wavelengths.
>
> 	In ordinary MPLS, LSRs swap input and output labels and
> it is assumed that there is negliable cost in changing an
> input label (e.g. VPI/VCI) to an output label. When a
> wavelength is used as a label, lambda-swapping between
> different lamba-in and lambda-out implies a wavelength
> conversion device, which is a scarce resource. In future all
> optical networks, wavelength conversion will very likely be
> required at some locations, such as Optical Cross Connects
> (OXC) sites. However in simpler ring-based optical networks
> where an optical path may traverse a number of relatively
> low-cost Optical Add-Drop-Mux (OADM) devices it is very
> advantageous if the same wavelength can be used along an
> entire lightpath traversing many nodes transparently (i.e.
> with the same lambda-in and lamba-out). Even in OXC or OADM
> systems supporting wavelength conversion, it is desirable to
> use it sparingly.
>
> 	a) the knowledge of other nodes' optical switching
> limitations (e.g. advertised lambda add/drop/passthru range),
> AND the currrent status of other nodes'  wavelength usage.
> This is the information needed by a source node to compute
> the most appropriate lambda for the lightpath (e.g. using
> minimal number of required wavelength conversions as one
> constraint), or
> 	b) there is some type of crankback mechanism in MPLmS
> LDP which can be invoked when one node on the setup path
> discovers that the lightpath cannot be established because
> the initial lambda allocated for the lightpath by the source
> node is already in use by another lightpath at that node, or
> 	c) require that each OADM node supports wavelength
> conversion (ugh) so that blocking can be avoided by a
> wavelength conversion.
>
> 	I prefer the 1st approach for a ring-based network,
> complemented by wavelength conversion at OXC sites between
> rings. One possible soultion would invlove the following :-
>
> 	1) a distributed wavelength usage database for the
> optical domain (so that source nodes have the information to
> compute a lambda that will not lead to blocking on the lightpath)
> 	This could involve protocol support to distribute
> wavelength usage status updates between all MPLmS aware nodes
> in an optical domain, possibly piggybacking these status
> updates in IGP protocol messages. The idea would be that each
> node periodically (or following changes in lightpath
> topology) sends status updates describing wavelength
> allocation on its interfaces. (One issue is how to keep this
> information up to date.) If this information is received by
> all nodes in an optical domain (such as a ring), then all
> nodes in the domain have a domain-wide view of lightpath
> assignments and lambda usage and are in a position to compute
> 'optimal' routes and lambda-assignments for new lightpaths.
> That is to say they would be in a position to compute a
> non-blocking shortest lightpath with minimal (hopefully zero)
> requirement for wavelength conversion. Either these two
> processes could be seperate (e.g. route determination
> firstbased on shortest-path, followed by lamnda-assignement) or the!
> !
> !
> !
> 	Basic MPLS LDP initialisation supports the exchange of
> this information between adjecent LSRs which is fine if all
> nodes can swap labels. However this won't work when
> non-adjacent ingress/egress nodes are the only ones
> add/dropping the lambda, and there is a desire for the
> intervening transit nodes to pass the lambda through
> transparently. Without this information about distant nodes,
> there is a danger that a lambda-could be assigned for a
> lightpath that is non-blocking at all intervening nodes, but
> which can't be dropped by the egress node because it is
> outside its advertised lambda-range. A possible solution is
> extension of the LmDP initialisation phase to broadcast/flood
> lambda-range advertisements to all nodes in a domain. This
> then allows a source node to know the lambda-swapping
> limititations of all the nodes through which a lightpath may
> traverse, and take this into account when establishing the
> route and lambda that the lightpath should use. Note that
> this is only nec!
> !
> !
> !
> essary if nodes on the path have differing capabilities, e.g.
> can add/drop different subsets of the complete range of
> lambdas supported in a network, but this may be a likely situation.
>
> 	Any thoughts?
>
> 	John Hopkins
>

---

From: Curtis Villamizar <[email-masked]>
Date: Mon, 31 Jan 2000 17:34:19 -0500

In message <AE676F938C58D3119F6A0010A80009960A1F11@NTSERVER4>, John Hopkins wri
tes:
[...snip...]
> 	John Hopkins

John,

For dynamic layout, the traffic engineering extensions would need to
advertise a bitmap of lambdas (with a bitmap size so that the bitmap
is extensible rather than fixed size).

There is already some interesting work in the area of optimally
routing LSPs and the harder problem of optimally routing active and
backup paths.  Lakshman has two good papers on the Infocom web sight.
For example his Minimum Interference Routing Algorithm (MIRA) is shown
to produce significantly better results than Widest Shortest Path
(WSP).

I havn't done a tour of the literature to find the best published
algorithms to do optical routing (I don't think there is much).  The
problem gets a lot harder if you add the restrictions that you have to
take the same wavelength.  If you put OEOs into the mesh, the chances
of not finding a path is reduced but it gets even harder to compute
optimal paths.

For example, here is a naive way to compute paths.  Foreach
wavelength, determine which links are available.  Sort the links and
compute a digest over the set of links.  Look in a cache for an SPF
result matching the digest.  If none is found, do an SPF.  The link
costs can be set using something like MIRA (costs need only be
determined once) with the costs taking into account how many lambdas
remain on each link.  The cache of SPF results at least reduces the
number of SPF that must be computed.  Each unique SPF produces a best
route.  The best of these can be choosen.  This already sounds close
to infeasible for a very high number of lambdas.  Adding OEOs makes
the problem still more complex.

Offline computations might be required.  The disadvantage is that
these typically cover single failures and require lengthy
recomputation when multiple failures do occur.  [Multiple fiber cuts
all too often happen.  Sometimes lots of capacity disappears at the
same time.  Train derailments along railway right of ways (Amtrak near
West Orange).  Bridge repairs (Raritan River).  Floods putting
facilities under water (St Louis area).  Exploding rat in the primary
to backup power cutover switch (Bay Area).  Emergency power shut down
due to gas line leak.  Fiber cut due to gas line repair.  These are
some of the most massive and better known ones in the last few years.
The list goes on.  People in Internet operations (or telco) know about
tons of multiple fiber failures.]

Those are some of my thoughts on this.

Any pointers to papers on algorithms for layout through optical cores
would be greatly appreciated.

Curtis

ps- I thought IRTF did research.  Isn't MPLS in the IETF?