[Search] [txt|pdfized|bibtex] [Tracker] [WG] [Email] [Nits]

Versions: 00 01 rfc3906                                                 
Network Working Group                                     Naiming Shen
INTERNET DRAFT                                        Redback Networks
Category: Informational                                      Henk Smit
Expiration Date: October 2004
                                                            April 2004

        Calculating IGP Routes Over Traffic Engineering Tunnels


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-

   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

   The list of Internet-Draft Shadow Directories can be accessed at

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.
   New traffic engineering algorithms calculate explicit routes to one

Shen, Smit                 Expires October 2004                 [Page 1]

Internet Draft          IGP ShortCut Over MPLS LSPs           April 2004

   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 inherits 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
   intermediate nodes on the path to destination node X, traffic will

Shen, Smit                 Expires October 2004                 [Page 2]

Internet Draft          IGP ShortCut Over MPLS LSPs           April 2004

   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 moves rtrD from the
   TENTative list to the PATHS 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.

6. Metric adjustment of IP routes over TE-tunnels

   When an IGP route is installed in the routing table with a TE-tunnel

Shen, Smit                 Expires October 2004                 [Page 3]

Internet Draft          IGP ShortCut Over MPLS LSPs           April 2004

   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

   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

   This mechanism is loop free since the TE-tunnels are source-routed
   and the tunnel egress is a downstream node to reach the computed
   destinations.  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.

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

Shen, Smit                 Expires October 2004                 [Page 4]

Internet Draft          IGP ShortCut Over MPLS LSPs           April 2004

   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

   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. Acknowledgments

   The authors would like to thank Christian Hopps for his comments
   to this document.

9.  Full Copyright Statement

   Copyright (C) The Internet Society (2002). All Rights Reserved.
   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published

Shen, Smit                 Expires October 2004                 [Page 5]

Internet Draft          IGP ShortCut Over MPLS LSPs           April 2004

   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the  purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an

10. 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.

11. 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 October 2004                   [Page 6]