Internet Draft Network Working Group Naiming Shen INTERNET DRAFT Cisco Systems Expiration Date: December 1999 Henk Smit Cisco Systems Calculating IGP routes over Traffic Engineering tunnels draft-hsmit-mpls-igp-spf-00.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 except that the right to produce derivative works is not granted. 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. Such capabilities are specified in [1], [2], [3] and [4]. 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. Shen, Smit [Page 1] Internet Draft draft-hsmit-mpls-igp-spf-00.txt June 1999 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 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). 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. Shen, Smit [Page 2] Internet Draft draft-hsmit-mpls-igp-spf-00.txt June 1999 - 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 flow over the TE-tunnel whose tail-end node is closest to node X. 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). Shen, Smit [Page 3] Internet Draft draft-hsmit-mpls-igp-spf-00.txt June 1999 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. Shen, Smit [Page 4] Internet Draft draft-hsmit-mpls-igp-spf-00.txt June 1999 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. 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 metric 5 in the routing table. Shen, Smit [Page 5] Internet Draft draft-hsmit-mpls-igp-spf-00.txt June 1999 7. Security Considerations This document raises no new security issues. 8. References [1] draft-ietf-mpls-traffic-eng-00.txt, "Requirements for Traffic Engineering Over MPLS", D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, work in progress. [2] draft-li-mpls-igp-te-00.txt, "IGP Requirements for Traffic Engineering with MPLS", T. Li, G. Swallow, D. Awduche, work in progress. [3] draft-ietf-isis-traffic-00.txt, "IS-IS extensions for Traffic Engineering", T. Li, H. Smit, work in progress. [4] draft-katz-yeung-ospf-traffic-00.txt, "OSPF extensions for Traffic Engineering", D. Katz, D. Yeung, work in progress. 9. Authors' Addresses Henk Smit Cisco Systems, Inc. 210 West Tasman Drive San Jose, CA 95134 Email: hsmit@cisco.com Voice: +31 20 342 3736 Naiming Shen Cisco Systems, Inc. 210 West Tasman Drive San Jose, CA 95134 Email: naiming@cisco.com Phone: +1 408 525 6483 Shen, Smit Expires December 1999 [Page 6]