The MPLS-OPS Archive

[sven.van_den_bosch@alcatel.be]

Hi Mathew,

In the mail below you mention the difficulty to simultaneously optimizing
primary and protection paths with offline TE. Incidentally, we have written
a number of papers on this subject including e.g.:
Sven Van den Bosch, Fabrice Poppe and Guido Petit, "Single-Path
Traffic-Engineering with Explicit Routes in a Flat Differentiated Services
Network," International Conference on Communications, June 11-14, 2001,
Helsinki, Finland.

Best regards,
Sven.





mpls-ops-request@mplsrc.com on 10/07/2002 03:02:42

To:   Christopher Lewis <chrlewis@cisco.com>
cc:   mpls-ops@mplsrc.com
Subject:  RE: [MPLS-OPS]: IGP


At 03:35 PM 7/9/2002 -0500, Christopher Lewis wrote:
My main issue is that in what I described, the path selected for a given
MPLS TE LSP tunnel may or may not be the same as the shortest IGP path.
Ah, I think I see the confusion. In many routers, IP and MPLS share
topological information even though IP's OSPF/IS-IS calculation is
different to MPLS' OSPF/IS-IS calculation. But in both cases they compute
the shortest path -- they just differ in their understanding of the path
details because they operate a different layers. IP's IGP sees all LSPs as
a single hop -- they're like a virtual interface that magically deposits
the packet at the destination LER. IP's IGP doesn't know about the details
of the label switched path.

At the MPLS layer, any variant of OSPF or IS-IS always calculates the
shortest MPLS switch path -- as defined as the sum of the metrics for each
MPLS hop. Whenever you use OSPF-TE, CSPF or IS-IS-TE in an MPLS network,
the router will run the Dijkstra shortest path first algorithm to compute
the label switched paths. How that path is installed -- whether by LDP,
RSVP-TE or any other method -- is irrelevant to the path computation.

What the "-TE" and "C-" versions of these protocols offer is the ability to
tinker with the MPLS hop metrics to fudge the "shortest" comparison by
giving some or all hops a metric other than 1, and the ability to exchange
the required constraint information with other routers. The latter is, of
course,  necessary to make these "extended" protocols work at all -- you
have to have a way to flood all the pertinent information to all the
routers.

So, even if you know what LSP layout you want, the only way to get it is to
try to figure out the hop metrics to get what you want. Constraints (a la
RFC 2702) are one way to simplify the process, but have the drawbacks I
mentioned in an earlier e-mail.

The main problem is that while you might get the LSP you want for some
traffic, it is very easy to foul up the LSPs for other traffic. And, you
can get very odd, unexpected network behavior.

That's why the majority of MPLS TE tools (but not CPLANE's :-) are based
around simulation. They let you tinker with the hop metrics and simulate to
see what the routers will calculate as the shortest path as a result. After
some number of iterations -- whenever you're happy with the result -- you
then manually implement all the hop metric changes.

All of this puts the burden on the network engineer to magically arrive at
the right constraints and/or metrics, and even then you can't quantify what
you have in any meaningful way that you care to define. And you're still
stuck with separately figuring out what the backup LSPs would be -- while
ensuring that each does not have any single point of failure with the
primaries that you simulated. The number of possible outcomes also grows
geometrically with the number of failure cases you might see in a live
network, so it's impractical to simulate every possible outcome. And then
you have to hand-configure the entire network, one router at a time.

I'll stop there...

Cheers,

Mathew


 Administrative constraints can also be imposed on MPLS TE LSP tunnels in
addition to bandwidth requirements. Available resources are flooded via
extensions to a link-state-based IGP like IS-IS or OSPF. RSVP, with traffic
engineering extensions, is used as the label distribution protocol and the
admission control mechanism to set up MPLS TE LSP tunnels. No other label
distribution protocols (like LDP/TDP) are needed for setting up MPLS TE LSP
tunnels.

I just want to make sure no-one was thinking that TE paths are
characterized the by the Dijkstra derived shortest path. To suggest that
off-line calculations are the only way to avoid the shortest path being
selected is not true. IMHO off line tools for modelling traffic are very
useful and have been in use by Telcos for many years in the voice networks
and will prove to be useful in MPLS networks.

Chris

At 02:54 PM 7/9/2002, Mathew Lodge wrote:
At 12:22 PM 7/9/2002 -0500, Christopher Lewis wrote:
Matthew, I don't understand what you're saying here. We may  be talking at
cross purposes.
I'm not sure. The ideas that go into offline TE are fairly radical to many
people because the way that routes have been computed in the Internet
hasn't changed for the last 25 years or so. Cheap computing power and the
software sophistication to make it simple to implement these alternative
schemes also has not existed until relatively recently.

Traffic engineering (to me at least) is about controlling how traffic flows
on your network. OSPF and IS-IS extensions allow those protocols to
communicate resource reservations made on a router.
Yes, the *extensions* communicate the resource reservations. But they are
extensions to protocols that mandate the use of a single algorithm --
Dijkstra's -- to compute the paths in the first place. You can't separate
the communication of the reservations from the path computation of OSPF and
IS-IS.

At 08:25 PM 7/8/2002, you wrote:
At 08:25 AM 7/5/2002 -0500, Christopher Lewis wrote:
Plain MPLS or MPLS VPN will work fine with distance vector protocols like
EIGRP, but as mentioned a link state routing protocol is needed for MPLS
traffic engineering, as each node needs the topology information those
protocols provide and OSPF and IS-IS have the opaque LSA extensions
necessary for traffic engineering.
To add to Chris' comments, note that this is for online "on the router"
traffic engineering only. If you're doing off-line traffic engineering, any
routing protocol that allows the control plane to operate will do.

Three benefits that offline TE offers vs. OSPF/IS-IS TE:
1) You can implement a routing algorithm that does a lot better than
Dijkstra shortest path. For example, you can minimize overall network
utilization and avoid bottlenecks.
MPLS TE using OSPF or IS-IS to communicate reserved resources does not rely
on the Dijkstra algorthim to compute a path.
No, they do force the use of Dijkstra's algorithm. OSPF and IS-IS construct
the reachability graph for the network and compute the shortest path using
Dijkstra's algorithm. The protocol messages allow the flooding of the
network reachability information to all participating routers so that the
graph can be constructed in the first place. In the "-TE" versions,
resource reservations piggyback on the protocol messages. So, the process
of computing the paths and communicating the reservations are intertwined
in OSPF-TE and IS-IS-TE, and you can't just get the reservation capability
without also getting Dijkstra's algorithm.

RSVP-TE is an example of a protocol that *just* communicates reserved
resources. In offline TE, you figure out the path (using whatever algorithm
you want), and then install it using the RSVP-TE explicit route object. In
OSPF and IS-IS, there is no way to use some other algorithm for determining
the best path. All you can do are set constraints such as resource class
affinity, or tinker with path metrics. Constraints merely eliminate some
number of paths from the input set to the Dijkstra algorithm -- they do not
change the algorithm. Path metrics are summed by the Dijkstra algorithm for
the purpose of determining which one is "shortest" -- they do not change
the algorithm.

2) You can pre-calculate and install backup LSPs and ensure that there are
no single points of failure, thereby dramatically improving LSP restoration
time and guaranteeing resiliency.
As you can with MPLS TE and have fast re-route handle swap overs in less
than 50 ms without operator intervention.
Yes, offline TE should support both since fast re-route and backup paths
are complimentary technologies. You can view fast re-route as a fast "band
aid" around a failure, with the backup path as the preferred longer term
solution. Fast re-route is very fast but hard to control. Backup LSPs are
slower to turn on (the failure needs to be signaled back to the head of the
LSP before traffic can be switched over) but offer more control.

The problem with fast re-route is the lack of control. If you don't reserve
the FRR paths in advance, there's no guarantee that FRR is going to keep
your network running. You don't know if there will be enough bandwidth on
the re-route path to carry the traffic, so you may end up dropping that
traffic, as well as impacting other traffic carried by neighboring nodes.
If you reserve all of the fast re-route paths in advance, you're going to
waste a lot of bandwidth in backup paths that overlap and aren't used most
of the time. The sub-50ms requirement comes from SONET's protection scheme,
which is criticized because it wastes 50% of bandwidth for protection
purposes. Pre-reserved FRR would be more wasteful than that because of the
overlapping re-route paths.

Clearly, the solution lies with careful FRR path selection and reservation
based on network demands and revenues, failure group information, and
integration with a backup LSP scheme. You want management software to
compute what that is based on your network design, operational  and
financial criteria -- i.e. an easy to understand application that doesn't
demand manual calculations and/or hand configuring data into every router
in your network.

3) You can support LSP constraints that are non-additive in nature -- since
shortest path works by adding hop metrics.
As you can with MPLS TE using OSPF or IS-IS extensions, things like
affinity allow you to have the path include or exclude specified types of
links in the path selection process for example.
Resource class affinities are an example of a constraint that can be
expressed in additive fashion. They result in the raising of some hop
metrics to infinity. A counter example might help: what if you wanted to
select the most reliable path, where you have to multiply reliability
factors for each hop to calculate end-to-end reliability? You can't do that
with an algorithm that insists on adding hop metrics.

Cheers,

Mathew


| Mathew Lodge                 | mathew@cplane.com     |
| Director, Product Management | Ph: +1 408 789 4068   |
| CPLANE, Inc.                 | http://www.cplane.com |

| Mathew Lodge                 | mathew@cplane.com     |
| Director, Product Management | Ph: +1 408 789 4068   |
| CPLANE, Inc.                 | http://www.cplane.com |




-------
The MPLS-OPS Mailing List
Subscribe/Unsubscribe:  http://www.mplsrc.com/mplsops.shtml
Archive: http://www.mplsrc.com/mpls-ops_archive.shtml