INTERNET DRAFT Expiration Date: January 2001 Vaibhav Shandilya C-DOT July 2001 Fault Tolerant LSP establishment in an MPLS network 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/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract One of the fundamental requirements of traffic engineering is rerouting the path of an established LSP tunnel. It could be because of an administrative policy or, a link or node failure. Its the latter requirement that is focussed in this document. The routing protocol running in the MPLS network must have the capability of path computation of a backup disjoint path and that shandilya [Page 1] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 of calculation of local fast reroute for each of the node of an E-LSP (explicitly routed Label Switched Path). This document extends the modified OSPF protocol [1], for finding a secondary fault-tolerant backup path (disjoint to the primary). The document brings forth extension to the OSPF to allow finding local fast rerouting paths on all the nodes along an LSP. In addition, the document proposes to run instance of another algorithm [4] on LERs to calculate explicit routes (E-LSPs) satisfying end-to-end delay QoS criterion. Table of Contents 1 Conventions used in the Document ......................... 1 2 Introduction ............................................. 2 3. Secondary Fault-Tolerant Path (secondary E-LSP) .......... 3 3.1 Explaining secondary path (secondary E-LSP) switchover ... 4 3.2 Procedure of establishing the secondary path (E-LSP) ..... 4 3.2.1 Computing a fault tolerant disjoint secondary path ....... 4 3.2.2 Establishment of the secondary path ...................... 4 4 Fast Local Rerouting ..................................... 5 4.1 Explaining fast local routing ............................ 5 4.2 Procedure of establishing the local fast reroute ......... 5 4.2.1 Computing a fast rerouting path at each node along an LSP . 5 4.2.1.1 Local fast reroute sharing nodes with segmentI ........... 5 4.2.1.2 Local fast reroute sharing nodes with segmentII .......... 5 4.2.1.3 Local fast reroute sharing nodes with both the segments .. 5 4.3 Optimizing the computed local fast reroute ............... 6 5 Establishing paths with strict end-to-end delay requirements 7 5.1 Routing not following a tree structure ................... 7 5.2 Use of an approximation algorithm ........................ 7 5.3 Delay metric, part of the link state advertisments ....... 8 6 Security considerations .................................. 8 7 Acknowledgements ......................................... 8 8 References ............................................... 8 9 Author's address ......................................... 8 10 Full Copyright Statement ................................. 9 1. Conventions Used in this Document LER : Label Edge Router LSR : Label Switch Router E-LSPs : Explicitly routed LSPs n : the Faulting node (the router outage or link failure) nPrev : node prior to n in the LSP. nNext : node next to n in the LSP. SegmentI : segment consisting of nodes which lie prior to the faulting node in an LSP. SegmentII: segment consisting of nodes which lie after the faulting node in an LSP. shandilya [Page 2] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 2. Introduction This document specifies a method of adding fault-tolerant E-LSP establishment to MPLS by proposing enhancements to the QoS extended OSPF [1]. The enhancements proposed in the document concern with : Computing a fault-tolerant, disjoint secondary path to a primary E-LSP. Computing local fast rerouting paths at each node along an already established E-LSP. Computing paths satisfying user's stringent end-to-end delay requirements. The proposals in the document take care of both the link and the node failure along an E-LSP. It is assumed that the network doesn't rely only on the IP self-healing property to recover from the failure which may take a time of the order of a few minutes when all the routing tables converge. It relies on the multilayer communication (a trigger from the physical layer) also, enforcing the expiration of the Router Dead OSPF timer and switching the MPLS traffic to either a fault-tolerant secondary E-LSP or, to a fast reroute, depending upon the degree of the recovery and the availabilty of the resources. 3. Secondary Fault-Tolerant path (secondary E-LSP) /---->Primary path link failure -r1------r2------r3------r4---X---r5------r6------r6-----r8------r9- \ <--------RSVP / \ / \ / r10----r11----r12------r13-----r14-----r15----r16------r17 \-->Secondary path switch over shandilya [Page 3] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 fig. 1 : Switch over to the backup E-LSP r1, r9 = LERs 3.1 Explaining secondary path (secondary E-LSP) switchover Node r4 on detection of failure in the link shall send an RSVP signalling message to r1 (the LER for the E-LSP) which would switch the MPLS traffic to an existing backup Fault-tolerant path (secondary E-LSP). Note: 1. The nodes of the secondary path are disjoint to that of the nodes in the original E-LSP (barring the LERs). 2. Any two nodes are connected by a single link. 3.2 Procedure of establishing the secondary path (secondary E-LSP) 3.2.1 Finding a Fault Tolerant disjoint path to the primary path by the LER. The LER after having calculated the primary path, calculates a secondary Fault tolerant path by deleting all the links of the primary path from its Topology table and then running the usual modified OSPF algorithm [1], over the new (temporary) Topology Table. The new path so calculated would be disjoint to the older one. 3.2.2 Establishment of the secondary path (secondary E-LSP) Just like the case of the primary path (E-LSP) establishment the fault-tolerant secondary path (E-LSP) is also established using RSVP signaling. By just switching the labels for the traffic coming on the primary, the whole traffic can be switched on to the secondary LSP in time of the order of ms. The fault tolerant paths corresponding to various primary paths are stored in FTED (Fault Traffic Engineering Database). The fault tolerant path is switched to in case of the primary path breakdown. shandilya [Page 4] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 4. Fast Local Rerouting /--> link or node failure nPrev / n nNext r1------r2------r3------r4---X---r5------r6------r6-----r8------r9 <---- | | RSVP Mesg \ / ------r11----- \-->local fast reroute fig 2 : Switching the traffic locally to a fast reroute r1, r9 = LERs n = the Faulting Node nPrev = the node before the Faulting node in the LSP. nNext = the node after the faulting node in the LSP. 4.1 Explaining fast local rerouting Node r4 on detection of fault in the link to r5, (it could be r5 router outage also, in which case OSPF Router dead interval timer will timeout.) shall route the traffic through alternative path to r6 ( every router along the E-LSP would have established a local fast reroute to the node next to the next node i.e. to nNext). In addition, r4 shall send an RSVP message to r1 informing it of the change in the E-LSP configuration. Node r1 (the LER for the E-LSP), may take necessary administrative action thereafter. 4.2 Procedure of establishing the local fast reroute 4.2.1 Computing a fast rerouting path at each node along the path The local fast reroute is computed by the nprev node by deleting all the link-entries corresponding to the faulting node in its topology table and, recalculating a path to the nnext node (by invoking the path calculating OSPF algorithm on the new (temporary) Topology Table ). The local fast rerouting path (from nprev to nnext), so computed may share some of the nodes of the existing E-LSP . This can happen in the following ways: 4.2.1.1 The local fast rerouting path shares the nodes, which lie before the faulting node in the E-LSP (SegmentI). 4.2.1.2 The local fast rerouting path shares the nodes, which lie after the faulting node in the E-LSP (SegmentII). 4.2.1.3 The general case, where nodes of both the segments are shared by the local fast reroute. shandilya [Page 5] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 4.3 Optimizing the computed local Fast reroute The node nprev shall optimize the computed fast rerouting path to nnext node by using the following algorithm (estabFastReroute) which takes into account the overlapping of the new path with one of the segments. /* The algorithm estabFastReroute takes into account the overlapping of the calculated fast Reroute path (using OSPF algorithm) with the two segments, the faulting node would divide the LSP into. */ estabFastReroute ( char[] fastReRoutePath) { nodeSegmentI = nPrev; nodeSegmentII = NULL; While( Not the end of the fast rerouting path) { Examine the currentNode of the Fast rerouting path; If the curent node in the fast rerouting path shares a node with the segment II { nodeSegmentII = currentNode; break from the while loop; } If the current node in the fast rerouting path shares a node with the segment I { find the node (by traversing the fast rerouting path) where the fast rerouting path leaves the segment I. nodeSegmentI = the leaving node; } } /* end while */ Send an RSVP message to nodeSegmentI (with the path to nodeSegmentII); /* nodeSegmentI shall start sending the MPLS traffic for the LSP to nodeSegmentII directly bypassing all the nodes in between, in the event of failure of the node n. shandilya [Page 6] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 Note: nodeSegmentI will have to get the required label to send the MPLS traffic to nodeSegmentII using LDP, CR-LDP or, RSVP-tunnels [6]. */ } /* end estabFastReroute */ Note: The above algorithm may result in some of the nodes in SegmentI or SegmentII to be bypassed in the new E-LSP. 5. Establishing Paths with strict end-to-end delay requirements The fundamental problem in QoS sensitive routing for emerging services such as VoIP (Voice Over IP), video, interactive multimedia is to find the cheapest route from a source to destinations that satisfy one or more QoS criteria. One of most important of them is end-to-end delay threshold which is an additive metric [4]. 5.1 Routing not following a tree structure. Unlike monotone criteria (like bandwidth), additive metrics need not result in routing to a specific destination taking place along a tree. Since the routes donot form a tree, it is infeasible to store routing tables inside the network as simple next hop tables per destination like OSPF and RIP. Storing the entire path or even the next hop for each separate source-destination pair and delay threshold is impractical since the routing tables would grow too large. 5.2 Use of an approximation algorithm Since this problem is known to be NP-hard, it is proposed that an efficient algorithm for the computation of Delay-sensitive Routes from One source to all destination. One such algorithm is due to Ashish Goel, K. G. Ramakrishnan et. al.[4] Its a fully polynomial time approximation scheme, which uses a simple dynamic programming algorithm to calculate the delay-sensitive routes from one source to all destinations. shandilya [Page 7] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 5.3 Delay metric, part of the link state advertisments For supporting the delay QoS, link state advertisements will contain delay metric. A stringent delay requirement at the LER to any destination will use a separate delay-sensitive routing table, formed using the delay-sensitive algorithm [4] the instance of which is running along with the enhanced OSPF algorithm. Note : It suffices that the delay sensitive algorithm runs only on the LERs. 6. Security Considerations This document raises no new security issues for OSPF. The security mechanisms already proposed for OSPF may be used. 7. Acknowledgments I would like to thank to thank Dr. Naveen Garg and Piyush Gupta for their review and contributions. 8. References [1] [RFC-2676] R.Guerin, S.Kamat, Ariel Orda, T.Przygienda and D.Williams, "QoS Routing Mechanisms and OSPF Extensions". [2] [RFC-3031] E.Rosen, A.Viswanathan, "Multiprotocol Label Switching Architecture. [3] [RC-2702] Awduche, J.Malcolm, J.Agogbua and M.O'Dell, "Requirements for Traffic Engineering Over MPLS". [4] Ashish Goel, K.G. Ramakrishnan, Deepak Kataria, Dimitris Logothetis "Efficient Computation of Delay Sensitive Routes from one Source to All Destinations". [5] [RFC-2430] T.Li and Y.Rekhter, "Provider Architecture for Differentiated Services and Traffic Engineering (PASTE)". [6] "Extensions to RSVP for LSP Tunnels", Awduche, Berger, Gan, Li, Swallow, Srinivasan, Work in progress. 9. Author's Address Vaibhav Shandilya C-DOT B-200, Sarasawati-Vihar Delhi-110034 India Phone : 91-11-4104815 Fax : 91-11-4107518 Email : vaibhav@techie.com, vaibhav@cdotd.ernet.in shandilya [Page 8] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001 10. Full Copyright Statement Copyright (C) The Internet Society (date). 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 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 English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. shandilya [Page 9] Internet Draft draft-shandilya-fault-tolerant-lsp-00.txt July 2001