Internet DRAFT - draft-hsmit-shen-mpls-igp-spf
draft-hsmit-shen-mpls-igp-spf
Network Working Group Naiming Shen
INTERNET DRAFT Redback Networks
Category: Informational Henk Smit
Expiration Date: June 2004
December 2003
Calculating IGP Routes Over Traffic Engineering Tunnels
draft-hsmit-shen-mpls-igp-spf-01.txt
1. Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
2. Abstract
This document describes how conventional hop-by-hop link-state
routing protocols interact with new Traffic Engineering capabilities
to create IGP shortcuts. In particular this document describes how
Dijkstra's SPF algorithm should be adapted so that link-state IGPs
will calculate IP routes to forward traffic over tunnels that are
set up by Traffic Engineering.
3. Introduction
Link-state protocols like integrated IS-IS [1] and OSPF [2] use
Dijkstra's SPF algorithm to compute a shortest path tree to all nodes
in the network. Routing tables are derived from this shortest path
tree. The routing tables contain tuples of destination and first-hop
information. If a router does normal hop-by-hop routing, the first-
hop will be a physical interface attached to the router.
Shen, Smit Expires June 2004 [Page 1]
Internet Draft IGP ShortCut Over MPLS LSPs December 2003
New traffic engineering algorithms calculate explicit routes to one
or more nodes in the network. At the router that originates explicit
routes, such routes can be viewed as logical interfaces which supply
Label Switched Paths through the network. In the context of this
document we refer to these Label Switched Paths as Traffic
Engineering tunnels (TE-tunnels). Such capabilities are specified
in [3] and [4].
This document describes how Link-state IGPs can make use of these
shortcuts, and how they can install routes in the routing table that
point out over these TE-tunnels. Because these tunnels use explicit
routes, the path taken by a TE-tunnel is controlled by the router
that is the head-end of the tunnel. In the absence of errors, TE-
tunnels are guaranteed not to loop. But routers must agree on how to
use TE-tunnels. Otherwise traffic might loop via two or more tunnels.
4. Enhancement to the Shortest Path First computation
During each step of the SPF computation, a router discovers the path
to one node in the network. If that node is directly connected to the
calculating router, the first-hop information is derived from the
adjacency database. If a node is not directly connected to the
calculating router, it inherents the first-hop information from the
parent(s) of that node. Each node has one or more parents. Each node
is the parent of zero or more down-stream nodes.
For traffic engineering purposes each router maintains a list of all
TE-tunnels that originate at this router. For each of those TE-
tunnel, the router at the tail-end is known.
During SPF, when a router finds the path to a new node (in other
words, this new node is moved from the TENTative list to the PATHS
list), the router must determine the first-hop information. There
are three possible ways to do this:
- Examine the list of tail-end routers directly reachable via a
TE-tunnel. If there is a TE-tunnel to this node, we use the
TE-tunnel as the first-hop.
- If there is no TE-tunnel, and the node is directly connected, we
will use the first-hop information from the adjacency database.
- If the node is not directly connected, and is not directly
reachable via a TE-tunnel, we will copy the first-hop
information from the parent node(s) to the new node.
The result of this algorithm is that traffic to nodes that are the
tail-end of TE-tunnels, will flow over those TE-tunnels. Traffic to
nodes that are downstream of the tail-end nodes will also flow over
those TE-tunnels. If there are multiple TE-tunnels to different
Shen, Smit Expires June 2004 [Page 2]
Internet Draft IGP ShortCut Over MPLS LSPs December 2003
intermediate nodes on the path to destination node X, traffic will
flow over the TE-tunnel whose tail-end node is closest to node X.
In certain applications, there is a need to carry both the native
adjacency and the TE-tunnel next-hop information for the TE-tunnel
tail-end and its downstream nodes. The head-end node may
conditionally switch the data traffic onto TE-tunnels based on
user defined criteria or events; The head-end node may also split
flow of traffic towards either types of the next-hops; The head-end
node may install the routes with two different types of next-hops
into two separate RIBs. Multicast protocols running over physical
links may have to perform RPF checks using the native adjacency
next-hops rather than the TE-tunnel next-hops.
5. Special cases and exceptions
The Shortest Path First algorithm will find equal-cost parallel paths
to destinations. The enhancement described in this document does not
change this. Traffic can be forwarded over one or more native IP
paths, over one or more TE-tunnels, or over a combination of native
IP paths and TE-tunnels.
A special situation occurs in the following topology:
rtrA -- rtrB -- rtrC
| |
rtrD -- rtrE
Assume all links have the same cost. Assume a TE-tunnel is set up
from rtrA to rtrD. When the SPF calculation puts rtrC on the
TENTative list, it will realize that rtrC is not directly connected,
and thus it will use the first-hop information from the parent. Which
is rtrB. When the SPF calculation on rtrA puts rtrD on the TENTative
list, it realizes that rtrD is the tail-end of a TE-tunnel. Thus rtrA
will install a route to rtrD via the TE-tunnel, and not via rtrB.
When rtrA puts rtrE on the TENTative list, it realizes that rtrE is
not directly connected, and that rtrE is not the tail-end of a TE-
tunnel. Therefor rtrA will copy the first-hop information from the
parents (rtrC and rtrD) to the first-hop information of rtrE.
Traffic to rtrE will now load-balance over the native IP path via
rtrA->rtrB->rtrC, and the TE-tunnel rtrA->rtrD.
In the case where both parallel native IP paths and paths over TE-
tunnels are available, implementations can allow the network
administrator to force traffic to flow over only TE-tunnels (or only
over native IP paths) or both to be used for load sharing.
Shen, Smit Expires June 2004 [Page 3]
Internet Draft IGP ShortCut Over MPLS LSPs December 2003
6. Metric adjustment of IP routes over TE-tunnels
When an IGP route is installed in the routing table with a TE-tunnel
as next hop, an interesting question is what should be the cost or
metric of this route ? The most obvious answer is to assign a metric
that is the same as the IGP metric of the native IP path as if the
TE-tunnels did not exist. For example, rtrA can reach rtrC over a
path with a cost of 20. X is an IP prefix advertised by rtrC. We
install the route to X in rtrA's routing table with a cost of 20.
When a TE-tunnel from rtrA to rtrC comes up, by default the route is
still installed with metric of 20, only the next-hop information for
X is changed.
While this scheme works well, in some networks it might be useful to
change the cost of the path over a TE-tunnel, to make the route over
the TE-tunnel less or more preferred than other routes.
For instance when equal cost paths exist over a TE-tunnel and over a
native IP path, by adjusting the cost of the path over the TE-tunnel,
we can force traffic to prefer the path via the TE-tunnel, to prefer
the native IP path, or to load-balance among them. Another example is
when multiple TE-tunnels go to the same or different destinations.
Adjusting TE-tunnel metrics can force the traffic to prefer some TE-
tunnels over others regardless of underlining IGP cost to those
destinations.
Setting a manual metric on a TE-tunnel does not impact the SPF
algorithm itself. It only affects comparison of the new route with
existing routes in the routing table. Existing routes can be either
IP routes to another router that advertises the same IP prefix, or it
can be a path to the same router, but via a different outgoing
interface or different TE-tunnel. All routes to IP prefixes
advertised by the tail-end router will be affected by the TE-tunnel
metric. Also the metrics of paths to routers that are downstream of
the tail-end router will be influenced by the manual TE-tunnel
metric.
This mechanism is loop free since the TE-tunnels are source-routed.
The end result of TE-tunnel metric adjustment is more control over
traffic loadsharing. If there is only one way to reach a particular
IP prefix through a single TE-tunnel, then no matter what metric is
assigned, the traffic has only one path to go.
When the manual TE-tunnel metric is configured to be larger than
the IGP native path metric, this TE-tunnel can not be used in the
SPF calculation. Otherwise a routing loop may be formed. Here is
an example:
Shen, Smit Expires June 2004 [Page 4]
Internet Draft IGP ShortCut Over MPLS LSPs December 2003
(src) 2 2
A ------ B ------- C
| =========>|
5| 30 |2
| |
D ---------------- E (dst)
5
There is a TE-tunnel from B->C with manual tunnel metric of 30.
The shortest path from source A to destination E is A->B->C->E with
the path metric of 6, thus A will use B as the nexthop router. If
this TE tunnel could be used by B's SPF calculation with the
metric of 30 for the span of B->C, then B->C->E will have the path
metric of 32, but B->A->D->E path will only have the metric of 12.
So B would send the traffic back to A, a routing loop formed.
6.1. Absolute and relative metrics
It is possible to represent the TE-tunnel metric in two different
ways: an absolute (or fixed) metric or a relative metric, which is
merely an adjustment of the dynamic IGP metric as calculate by the
SPF computation. When using an absolute metric on a TE-tunnel, the
cost of the IP routes in the routing table does not depend on the
topology of the network. Note that this fixed metric is not only used
to compute the cost of IP routes advertised by the router that is the
tail-end of the TE-tunnel, but also for all the routes that are
downstream of this tail-end router. For example, if we have TE-
tunnels to two core routers in a remote POP, and one of them is
assigned with absolute metric of 1, then all the traffic going to
that POP will traverse this low-metric TE-tunnel.
By setting a relative metric, the cost of IP routes in the routing
table is based on the IGP metric as calculated by the SPF
computation. This relative metric can be a positive or a negative
number. Not configuring a metric on a TE-tunnel is a special case of
the relative metric scheme. No metric is the same as a relative
metric of 0. The relative metric is bounded by minimum and maximum
allowed metric values while the positive metric disables the
TE-tunnel in the SPF calculation.
6.2. Examples of metric adjustment
Assume the following topology. X, Y and Z are IP prefixes advertised
by rtrC, rtrD and rtrE respectively. T1 is a TE-tunnel from rtrA to
rtrC. Each link in the network has an IGP metric of 10.
===== T1 =====>
rtrA -- rtrB -- rtrC -- rtrD -- rtrE
10 10 | 10 | 10 |
X Y Z
Shen, Smit Expires June 2004 [Page 5]
Internet Draft IGP ShortCut Over MPLS LSPs December 2003
Without TE-tunnel T1, rtrA will install IP routes X, Y and Z in the
routing table with metrics 20, 30 and 40 respectively. When rtrA has
brought up TE-tunnel T1 to rtrC, and if rtrA is configured with the
relative metric of -5 on tunnel T1, then the routes X, Y, and Z will
be installed in the routing table with metrics 15, 25, and 35. If an
absolute metric of 5 is configured on tunnel T1, then rtrA will
install routes X, Y and Z all with metrics 5, 15 and 25 respectively.
7. Security Considerations
This document raises no new security issues.
8. References
[1] ISO. Information Technology - Telecommunications and
Information Exchange between Systems - Intermediate System
to Intermediate System Routing Exchange Protocol for
Use in Conjunction with the Protocol for Providing the
Connectionless-Mode Network Service. ISO, 1990.
[2] J. Moy. OSPF Version 2. Technical Report RFC2328 Internet
Engineering Task Force, 1998.
[3] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus,
"Requirements for Traffic Engineering Over MPLS", RFC 2702,
September 1999.
[4] D. Awduche, et al, "RSVP-TE: Extensions to RSVP for LSP
tunnels", RFC3029, December 2001.
9. Authors' Addresses
Naiming Shen
Redback Networks, Inc.
300 Holger Way
San Jose, CA 95134
Email: naiming@redback.com
Henk Smit
Email: hhwsmit@xs4all.nl
Shen, Smit Expires June 2004 [Page 6]
