Internet Engineering Task Force Der-Hwa Gan Internet Draft Ping Pan draft-gan-fast-reroute-00.txt Arthi Ayyangar April 10, 2001 Kireeti Kompella Expires: October, 2001 Juniper Networks A Method for MPLS LSP Fast-Reroute Using RSVP Detours 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 To view the list Internet-Draft Shadow Directories, see http://www.ietf.org/shadow.html. Abstract In this document, we introduce a method to establish backup LSP tunnels in large-scale networks. Two additional RSVP objects are proposed. These objects together make possible for routers using RSVP to create detours that can route around downstream links and nodes. As a result, an LSP can quickly and automatically repair itself, while redirecting the user traffic to the pre-computed and pre- established detour routes in event of network link and node failures. Packet loss is therefore minimized. 1 Introduction The ability to quickly re-route traffic around failed links and nodes in a label switched path (LSP) can be extremely important to users. Gan, et. al. [Page 1] Internet Draft fast-reroute April 10, 2001 When a network failure takes place, user data need to be re-directed over a detour path. The usefulness of a re-route mechanism is determined by the speed that a detour (or backup) path is established, the time it takes to re-route traffic, and how easy it is to configure detour path within the network. To achieve timely detour path setup, one cannot establish a path after a failure is detected. Thus using pre-computed and pre- established detour path is essential for data traffic where packet loss is undesirable. In order to achieve shortest re-route time, the detour decision must be made as close to the failure point as possible, since it may take significant time to notify other nodes in the LSP of such failure. Since it is almost impossible to predict where failure may occur along an LSP, an ideal detour mechanism is to protect the entire LSP by establishing detour paths throughout the LSP. In the extreme, a fully protected LSP might require (N - 1) detour paths, where N is the number of hops that the LSP traverses. To minimize the path computation overhead, it is desirable for the detour paths to merge back to the main LSP as soon as possible. To simplify detour configuration, we need to automate how detour paths are established inside the network. This document describes a method for automatically setting up detour paths over a RSVP signaled LSP[1,2], that offers the highest possible quality service to users while minimizing network overhead wherever possible. Detours are computed and established in a distributed fashion, continuously adapting to latest topology without manual intervention. The procedures described in this document only protect unidirectional LSPs. Protecting bidirectional LSPs is left for further study. Throughout the document, the terms MPLS LSP and RSVP Session are used interchangeably. 2 Operation Overview To protect from potential downstream link or node failures, a detour may be setup between the current node and one of the downstream nodes. The current node can be any node along a LSP except the LSP's egress, for the obvious reason that the egress node has no downstream link or node failure to speak of. Any downstream node of a LSP, which is more than one hop away from the current node, can be the detour merge point. For penultimate node, only the immediate downstream link need to be protect, so egress node is the detour merge point. Gan, et. al. [Page 2] Internet Draft fast-reroute April 10, 2001 +-----------------------+ +-------------------------+ | | | | ^ v ^ v Node1 ====> Node2 ======> Node3 =====> Node4 ======> Egress v ^ v ^ | | | | +-----------------------+ +-------------+ Main RSVP LSP ===== Detours ----- Figure 1: Example on where to initiate and terminate detour paths. In Figure 1, detour (Node1, Node3) is created to protect against link failures between Node1-Node2 and Node2-Node3, as well as a node failure at Node2. This detour path is computed and initiated at Node1, and merges at Node3. In this case, Node2 and Node4 are not aware of the detour. Likewise, detour (Node2, Node4) is created by Node2, to protect against link failures at Node2-Node3 and Node3-Node4, and node failure at Node3. Detour (Node4, Egress) is established to protect a local link between Node4 and Egress only. A detour may traverse any number of transit nodes before merging at a downstream node. To be maximal flexible, there is no limitation on who the transit nodes are. The only hard limitation is that detour cannot traverse immediate downstream link and node. We will describe the procedure on setting up detours in Section 4. But first, in the next section, we define two new RSVP objects that are used for the fast-reroute and detour operation. 3 RSVP Extension Two new objects are defined to support LSP fast-reroute. The objects are the FAST_ROUTE object and the DETOUR object. Both objects can only be carried in RSVP Path messages. To support the proposed fast reroute functionality, an implementation MUST support both objects. The objects are defined to be compatible with routers that do not recognize them (see Section 3.10 in [1]). For the routers that don't Gan, et. al. [Page 3] Internet Draft fast-reroute April 10, 2001 support the FAST_REROUTE objects, they MUST forward the objects downstream unchanged. For the routers that don't support the DETOUR objects, the routers MUST reject the message and send a PathErr to notify the sender. This implies that, even if some nodes along a main LSP do not recognize or support the new objects, it is still possible to establish detour LSP's between the nodes that can support the new objects. At worst, the detour LSP's will not be established to protect the links between the non-supporting nodes. This feature can be very useful and important for network providers to deploy backup MPLS tunnels inside their networks. 3.1 FAST_REROUTE Objects FAST_REROUTE Object Class = 205 (use form 11bbbbbb for compatibility) C-Type = 7 0 1 2 3 +-------------+-------------+-------------+-------------+ | Length (bytes) | Class-Num | C-Type | +-------------+-------------+-------------+-------------+ | Setup Prio | Hold Prio | Hop-limit | Reserved | +-------------+-------------+-------------+-------------+ | Bandwidth | +-------------+-------------+-------------+-------------+ | Exclude colors | +-------------+-------------+-------------+-------------+ | Include colors | +-------------+-------------+-------------+-------------+ Setup Priority The priority of the detour with respect to taking resources, in the range of 0 to 7. The value 0 is the highest priority. Setup Priority is used in deciding whether this session can preempt another session. See RSVP-TE draft for usage of priority. Holding Priority The priority of the detour with respect to holding resources, in the range of 0 to 7. The value 0 is the highest priority. Gan, et. al. [Page 4] Internet Draft fast-reroute April 10, 2001 Holding Priority is used in deciding whether this session can be preempted by another session. See RSVP-TE for usage of priority. Hop-limit The maximum number of extra hops the detour is allowed to take, from current node (branching point) to merging node, with current node and merging node excluded in counting. For example, hop-limit of 0 means only direct links between current and merging nodes can be considered. Reserved This field is reserved. It MUST be set to zero on transmission and MUST be ignored on receipt. Bandwidth Bandwidth estimate (32-bit IEEE floating point integer) in bytes-per-second. Exclude colors A 32-bit vector representing a set of attribute filters associated with a detour any of which renders a link unacceptable. Include colors A 32-bit vector representing a set of attribute filters associated with a detour any of which renders a link acceptable (with respect to this test). A null set (all bits set to zero) automatically passes. 3.2 DETOUR Object DETOUR Object Class = 63 (to conform 0bbbbbbb format for compatibility) C-Type = 7 0 1 2 3 +-------------+-------------+-------------+-------------+ | Length (bytes) | Class-Num | C-Type | Gan, et. al. [Page 5] Internet Draft fast-reroute April 10, 2001 +-------------+-------------+-------------+-------------+ | Source ID | +-------------+-------------+-------------+-------------+ | Downstream Node ID | +-------------+-------------+-------------+-------------+ Source ID IPv4 address identifying the beginning point of detour. Any address on the branching node can be used. Downstream Node ID IP address identifying the downstream node that source is trying to avoid. Router ID of downstream node is preferred. 3.3 Message Formats Both FAST_REROUTE and DETOUR objects MUST be carried in RSVP Path messages. To request for a fast-reroute, the Path message MUST carry a FAST_REROUTE object. RSVP object ordering makes no logical difference, and an implementation should be ready to accept objects in any order. A recommended message format is the following: ::= [ ] [ ] [ ] [ ... ] ::= [ ] Gan, et. al. [Page 6] Internet Draft fast-reroute April 10, 2001 The presence of FAST_REROUTE object in a RSVP session indicates that the fast reroute service is requested. The object itself contains the information in aiding detour computations and setup. After being processed at a node, the FAST_REROUTE MUST be stored by the node for later Path refreshes. A node, that recognizes FAST_REROUTE but cannot support it (possibly because temporary failure to compute a viable detour), should silently retry periodically. No PathErr should be sent. A RSVP node that does not recognize FAST_REROUTE MUST forward it unchanged. This has no impact on the main LSP. The worst result is that some transit nodes do not establish detours. A node which accepts FAST_REROUTE MUST be ready to accept and correctly process DETOUR object for the same LSP. To create a detour, a branching node MUST send out a Path message with DETOUR object in the following format. Once again, object placement and ordering make no logical difference. ::= [ ] [ ] [ ] [ ... ] ::= [ ] At downstream nodes, the presence of DETOUR object indicates that this session is a detour. After being processed at a node, the DETOUR object MUST be stored for later Path refreshes. A RSVP node that does not recognize DETOUR MUST send a PathErr with error code "Unknown object class" toward the sender. A sender here is the branching node that creates the DETOUR object, not ingress of the LSP. The sender should stop propagating PathErr further upstream. The PathErr causes the detour setup to fail, while the main LSP remains unaffected. The sender may choose to recompute a different detour, or Gan, et. al. [Page 7] Internet Draft fast-reroute April 10, 2001 notify management that detour cannot be established. It is illegal to have a Path message containing both FAST_REROUTE and DETOUR objects, since a session cannot be main and detour at the same time. FAST_REROUTE object MUST only be present on main LSP, not on detours, whereas DETOUR object is only used for building a detour LSP. On downstream nodes, the presence of DETOUR object indicates that this session is a detour. Applying the fast-reroute mechanism creates detour LSP's at intermediate nodes. Currently, the branching and merging procedures (described below) only support FF reservation style sessions. Supporting for shared reservation styles is left for future study. RSVP is designed to cope gracefully with non-RSVP routers anywhere between senders and receivers. However, since LSP tunnels[2] doesn't work over non-RSVP cloud, and our extension only deals with LSP tunnels, thus the proposed RSVP extension does not work over non-RSVP cloud. 4 Setting up Detours 4.1 Detour Path Computation Algorithm When a node receives FAST_REROUTE objects from the Path messages, it can trigger CSPF computation periodically to find out where to setup the detour paths. To protect an LSP, the node needs to first collect the following information: 1. A list of all downstream nodes that the LSP goes through. This information is readily available from the RECORD_ROUTE objects[2] during label setup. 2. The immediate outgoing link that the LSP goes through. 3. The downstream nodes that we want to protect against. Once again, this information is learnt from the RECORD_ROUTE objects. 4. The bandwidth requirement, hop-count limit, priority, and link coloring information for the detour. The FAST_REROUTE object can provide such information. The node applies a typical CSPF algorithm to compute the route and the destination for a detour path. The path computation must satisfies the following constraints: Gan, et. al. [Page 8] Internet Draft fast-reroute April 10, 2001 o The detour path originates from current node. o It should not traverse to the immediate outgoing link. o It should not traverse the downstream nodes that we try to protect against. o It should satisfy all the requirements as specified in the FAST_REROUTE object. If such computation succeeds, the node should trigger RSVP to establish a detour path immediately, and schedule a re-computation at a later time. The detour path should be as short as possible, and must merge back into the main LSP automatically at its destination. If for any reason, the node is unable to bring up a detour path, it must schedule a retry at a later time. The node has the option to apply other constraints during the CSPF computation. For example, a simple method can be to terminate the computation as soon as a detour path is found. On the other hand, an implementation may wish to continue exhaustive search to discover an optimal path with lowest cost (or highest available bandwidth). The node also has the option to re-compute the detour path periodically even after the detour is up and running to ensure continuous adaptation to the latest network conditions. The main advantage for running CSPF[3] here is to eliminate the needs for manual configuring detours, thus reduce the administrative overheads. However, it is important to be aware that the detour paths cannot cross the traffic engineering boundaries. A traffic engineering boundary is currently deliminated by an OSPF area, or an ISIS level. 4.2 Originating a Detour Request At a detour branching node, a successful detour computation (described in Section 4.1) yields enough information to construct a LSP detour request. The information includes: o A DETOUR object that specifies the detour's destination. o A new EXPLICIT_ROUTE object toward the detour's destination. o A new next-hop router's address to construct a new RSVP_HOP object. o The out-going interface information to send the detour request. The out-going interface must be different from the Gan, et. al. [Page 9] Internet Draft fast-reroute April 10, 2001 one used by the main LSP. A Path message that is used to setup a detour path MUST consists of the new DETOUR, ERO and RSVP_HOP objects. In addition, the SENDER_TSPEC object contains the bandwidth information from the previously received FAST_REROUTE objects. However, the Path message MUST not have a FAST_REROUTE object. The branching node MUST not mix the messages for the main and the detour LSP's. When it receives Resv, ResvTear and PathErr messages from the downstream detour destination, the messages MUST not be forwarded upstream. Similarly, when it receives ResvErr and ResvConf messages from upstream, the node MUST not propagate them onto the detour LSP. In RSVP-TE operation, the session tear-down request is normally originated by the sender via PathTear messages. During error conditions, the network routers can send ResvTear messages to fix problems on the failing path. Thus, when the branching node receives a PathTear message from upstream, it MUST tear-down both the main and detour LSP's. The PathTear messages MUST propagate to both main and detour LSP's. On the other hand, the branching node may receive ResvTear messages from downstream for the main LSP. As long as a detour is up, the ResvTear messages MUST not sent further upstream to ingress. 4.3 Detour Merging Nodes A detour merging node is where a detour LSP merges back onto a main LSP. A merging node may receive multiple Path messages from different interfaces, but with identical SESSION and SENDER_TEMPLATE objects. To maintain the LSP's, it is important for the non-egress node to identify the main LSP's from the detour LSP's (by the way, it is possible to have multiple detour LSP's to merge at a single node). Generally, a Path message for a detour LSP MUST contain a DETOUR object, whereas a Path that has a FAST_REROUTE object MUST represent a main LSP. 4.4 Loop detection It is possible to have detours traversing through the same nodes as the main LSP. To make the proposed detour method working, the nodes MUST process the detour LSP's independently from the main LSP's during the LSP loop detection procedure as suggested in [2]. 5 Security Considerations This document does not introduce new security issues. The Gan, et. al. [Page 10] Internet Draft fast-reroute April 10, 2001 specification adds new objects to RSVP. Therefore, the security considerations pertaining to the original RSVP protocol[1] remain relevant. 6 Intellectual Property Considerations Juniper Networks, Inc. is seeking patent protection on technology described in this Internet-Draft. If technology in this Internet- Draft is adopted as a standard, Juniper Networks agrees to license, on reasonable and non-discriminatory terms, any patent rights it obtains covering such technology to the extent necessary to comply with the standard. 7 Acknowledgments We acknowledge the helpful comments from Yakov Rekhter, Manoj Leelanivas, Nischal Sheth and Cliff DeGuzman. 8 Bibliography [1] R. Braden, Ed., L. Zhang, S. Berson, S. Herzog, and S. Jamin, "Resource ReSerVation protocol (RSVP) -- version 1 functional specification," Request for Comments 2205, Internet Engineering Task Force, Sept. 1997. [2] D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, and G. Swallow, "RSVP-TE: Extensions to RSVP for LSP tunnels," Internet Draft, Internet Engineering Task Force, Feb. 2001. Work in progress. [3] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, and J. McManus, "Requirements for traffic engineering over MPLS," Request for Comments 2702, Internet Engineering Task Force, Sept. 1999. 9 Authors Der-Hwa Gan (dhg@juniper.net) Ping Pan (pingpan@juniper.net) Arthi Ayyangar (arthi@juniper.net) Kireeti Kompella (kireeti@juniper.net) Juniper Networks, Inc. 1194 N. Mathilda Avenue Sunnyvale, CA 94089 Gan, et. al. [Page 11] Internet Draft fast-reroute April 10, 2001 Table of Contents 1 Introduction ........................................ 1 2 Operation Overview .................................. 2 3 RSVP Extension ...................................... 3 3.1 FAST_REROUTE Objects ................................ 4 3.2 DETOUR Object ....................................... 5 3.3 Message Formats ..................................... 6 4 Setting up Detours .................................. 8 4.1 Detour Path Computation Algorithm ................... 8 4.2 Originating a Detour Request ........................ 9 4.3 Detour Merging Nodes ................................ 10 4.4 Loop detection ...................................... 10 5 Security Considerations ............................. 10 6 Intellectual Property Considerations ................ 11 7 Acknowledgments ..................................... 11 8 Bibliography ........................................ 11 9 Authors ............................................. 11 Gan, et. al. [Page 12]