Internet Draft R. Nagarajan M.A. Qureshi Expires Date: September 2002 Y.T. Wang Lucent Technologies March 2002 A Packet 1+1 Path Protection Service for MPLS Networks 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 To provide resiliency from failures in MPLS-based networks, various protection and restoration approaches have been proposed and discussed in the literature. One important application is the support of a highly reliable control plane of the transport network. This informational draft discusses a packet level 1+1 path protection scheme in MPLS networks. The scheme is simple and recovers transparently and instantly from any single failures in the network without explicit failure detection, notification and switchover, in contrast to the LSP level 1+1 path protection approach. We describe the minimum requirements to support the packet level 1+1 path protection service. We conclude the discussions with an example implementation. 3. Introduction MPLS provides a basic framework, among others, to effectively traffic engineer data networks. Recently protection and reroute of LSPs in MPLS networks has received considerable attention and several schemes packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 2] have been proposed in the literature (see e.g., [1,2,3,4]). From the end-user standpoint, the protection and restoration attributes of most interest are restoration time, the failure coverage, and network capacity needed for restoration. Restoration time is the time taken to restore the end-user service upon failure. This includes in the general case, failure detection, notification and signaling to switchover the traffic from the failed LSP to a backup LSP. Many different types of failures are possible in a MPLS network such as cable cuts at physical layer, link layer failures, signaling failures etc.,. Failure coverage indicates which failures are protected against and which are not recoverable. Finally, redundant capacity is needed in the network to restore traffic on failures. Different restoration approaches use differing amounts of redundant network capacity thus impacting the price the user may pay for that service. The ideal restoration scheme would provide smallest restoration time with maximum failure coverage while requiring the smallest amount of restoration capacity and cost. In reality, there are a number of significant tradeoffs. For example, local restoration schemes proposed in the literature (see e.g., [3]) provides a fast recovery using fault indication from the physical layer. This requires the underlying physical transport network to propagate any of its failure in the downstream direction to the network element supporting local re-route restoration. When switches are connected by a transport cloud with multiple transport elements or by leased pipes, failures in the transport cloud or in the leased pipe may not always be conveyed faithfully to the MPLS switches. That is, schemes based on fast local re-route cover only those physical failures that can be detected at the downstream node. The benefit however is the recovery can be fast when such detection is available. Many path recovery schemes, on the other hand, require the fault indication be propagated to the end nodes of the LSPs. Schemes in this category may use a variety of failure detection mechanisms such as RSVP refresh, etc.. These schemes tend to be slower compared to the local re-route schemes that use the local physical indication. However, the path recovery schemes could provide coverage of a larger set of failures: all physical layer failures irrespective of capability of underlying transport network to propagate failure information to the downstream node. In this draft, we propose a packet level 1+1 path protection scheme. It provides an instantaneous recovery from failures without loosing the in-transit packets on the failed LSP. Failure coverage includes any single failures in physical layer, link layer and MPLS layer (label processing and switching). It employs dual diverse LSPs and requires dedicated network capacity on both paths. 4. Packet 1+1 Overview Packet 1+1 path protection provides a packet level protection service similar in some respects to the well-known transport 1+1 service with packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 3] several important distinctions. Packet level 1+1 allows selection of incoming packet from any LSP irrespective of the LSP from which the last packet was selected. That is, packet 1+1 protection treats both LSPs as working LSP. This is different from the traditional LSP level 1+1 scheme where one LSP is designated as working LSP while the other is the protection one. Packets are selected from the primary until a detection of failure on the working LSP causes a switching to the protection LSP. In contrast, packet 1+1 does not require explicit failure detection and protection switching. This allows the packet level 1+1 scheme to recover from any layer-1 or layer-2 single failure instantaneously and transparently. Similar to the LSP level 1+1 protection, only edge nodes need to be service-aware which makes interoperability easier. To provide packet 1+1 protection service between two MPLS network edge LERs, a pair of MPLS LSPs are established along disjoint paths. Packets from an application flow subscribing to the service are dual-fed at the ingress node onto the two LSPs. Disjoint paths in the simplest case may be link or node disjoint but in general may involve more complicated notion such as shared risk link groups [5]. At the egress LER node, one of the two copies of the packet is selected and forwarded from the two possible received copies, each traversing a disjoint path. Given this, any single failure in the network, other than the ingress or egress node itself, can affect at most one copy of each packet. This allows the service to withstand a single failure transparently. In terms of restoration time, this can be characterized as an instantaneous recovery from a failure since there is no need to detect, notify and switch to protection path explicitly. The scheme can be easily extended to protect against multiple failures by employing more than two disjoint paths. 5. Requirements The minimum requirements to provide packet 1+1 protection service are as follows: a) There is no new requirement on the interior nodes of the network. b) The network should support the establishment of diversely routed LSPs. c) Ingress Node: 1. Must be able to associate the two LSPs that are used to provide packet level 1+1 protection between two end nodes. 2. Must support the carrying of an identifier in the packet which will be used to identify duplicate copies of a packet at the egress node 3. Must be able to dual-feed each packet on these two mated LSPs. d) Egress Node: packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 4] 1. Must be able to associate the two LSPs that are used to provide packet level 1+1 protection between two end nodes. 2. Must be able to identify the duplicate copies of a dual-fed packet using the identifier 3. Must be able to select and forward one and only one of the copies of a packet. The above stated requirements describe the minimal functionality necessary to implement a packet level 1+1 scheme. These functions can obviously be implemented in various fashions achieving different properties. To aid the discussions, we illustrate an example implementation. Further, we comment on the resulting service properties of this particular example implementation. 6. An Example Implementation 6.1 Implementation Architecture Overview Figure 1 illustrates a realization of the service using sequence numbers as identifiers. After passing through the classifier, each packet that needs to be forwarded on the mated LSPs is assigned a distinct sequence number by the service-aware ource edge node. This packet with the distinct identification is then duplicated and forwarded onto the two disjoint LSPs. On the service-aware egress node a counter is used to keep track of expected sequence number of the next packet. The details of an example selection algorithm are described in section 6.5 below. +-----------+ +-----------+ +---+ | IP/others | | IP/Others | | |--------> | | -----> +---+ | | | | | | +------|----+ +------|----| | +---+ | | +---+ | | | 8 | | |SHIM| | | | +---+ | | +---+ | | SHIM | Dual-feed |- | | | <----> | counter-value |6| |Select | | | | |- ->-<- | | | | | | | | | +--|------|-+ +---+ +---+ +---+ +---|-----|-+ | | --->--| 7 |----| 6 |--| 5 |->----- | | | | LINK | +---+ +---+ +---+ | | | | | | | LINK | | | | | +---+ +---+ | | | | ---------->-----| 7 |-----| 6 |--->------------ | +-----------+ +---+ +---+ +-----------+ Figure 1: Packet 1+1 Protection Service packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 5] 6.2 Transport of Sequence Number For a scheme based on sequence number as illustrated in our example implementation, every packet needs to carry the sequence number. The sequence number can be carried as the first four bytes inside the shim header of the LSP providing packet 1+1. Since the ingress and egress nodes must be aware of each LSP participating in the packet 1+1, the egress node will recognize that there is a sequence number inside the label. It will use the sequence number for selection purpose and then remove it before forwarding the accepted packet further. Note packet 1+1 can be provided at any level of hierarchy of a nested LSP. Figure 2 illustrates the sequence number position behind the 4-bytes MPLS encapsulation header. 4-bytes shim-header 4-bytes sequence # +--------------------------+--------------------------+ | Encapsulation Header | Sequence Number | +--------------------------+--------------------------+ Figure 2: An Illustration for Sequence Number Transport For transporting L2 frames over MPLS, one possibility is to use the control word [6] to carry the sequence number in the packet. In this case, the use and definition of control word would need to be enhanced. 6.3 Enhancement in NHLFE and ILM Dual-feed and select capabilities can be implemented at the MPLS shim layer by enhancing the Next-Hop-Label-Forward-Entry (NHLFE) entries. At the ingress node, to provide the dual-feed functionality the NHLFE needs to support two instead of one outgoing LSP. This is easily achieved by using two next-hop/label entries instead of one, each corresponding to one of the mated diverse LSPs. Figure 3 illustrates this case. Given this, when the IP layer forwards an packet to the NHLFE supporting dual-feed it first duplicates the packet and then forwards it to the next hops with appropriate labels according to its two next-hop/label entries. In the middle of the network each copy of the packet traverses the LSP in the standard way, as any other packet would traverse an LSP; thus transparent to the LSRs. On the egress node, the Incoming Label Map (ILM) needs to map the labels of the two diverse LSPs to a single NHLFE entry that enables the receive side to select one of possibly two received copies. Figure 4 illustrates this case. Note that the ingress/egress node needs to keep track of all the originating/terminating LSP pairs that provide 1+1 service. packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 6] +--------------------------+-------------------------+ | Dual-feed operation | Current Sequence # |--> +--------------------------+-------------------------+ | | | <-------------------------------<--------------------------- | | | | | Entry for LSP-1 | Entry for LSP-2 | +-------+----------+------+ | +-------+----------+------+ ->| Label | Next Hop | .... | ->| Label | Next Hop | .... | +-------+----------+------+ +-------+----------+------+ Figure 3: Enhanced NHLFE Functionality to Support Dual-feed ILM: LSP-1 +---------+ | Label +-- +---------+ | | Egress NHLFE Entry ---> +-----------------+------------+------+ | Pop with Select | Sequence # | .... | ---> +-----------------+------------+------+ | ILM: LSP-2 | +---------+-- | Label | +---------+ Figure 4: Enhanced NHLFE Functionality to Support Selection 6.4: Signaling Enhancement Ingress and egress need to realize the disjoint LSPs supporting packet 1+1. This will allow them to properly program the NHLFE entries and ILM to NHLFE mapping. This association of LSPs at ingress and egress nodes can be achieved either statically through provisioning or dynamically using the signaling protocol. To set up the mated LSPs dynamically, signaling support is required to associate the right pair of LSPs at the ingress and egress nodes. RSVP-TE or CR-LDP MPLS signaling protocols can be enhanced to provide this additional functionality. At the ingress node, at the time of establishment of packet 1+1 service, RSVP-TE can query the routing database to obtain two diverse paths. After successful response, it can initiate establishment of an LSP along each of the diverse paths. The two LSPs need to be bound at the ingress and egress nodes with the association conveyed to the label processing functions in order to implement the dual-feed and select function. This can be packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 7] accomplished by associating a unique connection ID with each of the two diverse LSPs. This connection ID is carried as part of, for example, the RSVP-TE PATH connection setup message for both LSPs and conveyed to the label processing function at both ingress and egress nodes. The connection ID and other information can be carried as an opaque object in RSVP-TE messages and is not processed at intermediate nodes. 6.5 Dual-Feed and Select Mechanism Dual-feed mechanism at ingress node is relatively straightforward and involves duplicating the packet and forwarding it according to two NHLFE entries. At the egress node, a critical requirement of the packet 1+1 protection service is the ability to select one and only one of a pair of dual-fed packets while considering that these duplicate packets will not arrive at the same time due to propagation delay and buffering. Further, any of the packets may be lost in the network due to transmission errors or buffer overflows. One way to implement the dual-feed and select mechanism is to have the two copies of the packet carry an identical ID which is carried in the inside of the MPLS shim header as shown in Figure 2. In particular this ID is a sequence number, which is assigned consecutively to packets that will enable the destination to differentiate different packets and between two duplicates of the same packet. Each pair of duplicated packets will get the same sequence number but distinct from the other pairs of duplicate packets. The basic idea behind the selector design is that the destination selector keeps a counter that indicates the sequence number of the next packet it is waiting for. If it receives a packet less or larger than the sequence number in the counter, it will reject the packet on the basis that a copy of this packet has already been received (from the other diversely routed LSP). When it receives the packet whose sequence number equals the sequence number in the counter then the destination accepts that packet and increases the sequence number by 1 in the counter. This mechanism works fine and requires no buffering at the selector as long as there is no loss of packets in the network. With possible packet losses in the network, the packet with the next sequence number may never arrive which presents a serious problem. Further, since the sequence number space is finite, there could be wrap around of the sequence numbers and old packets can be mistaken for new if packet delay differentials of two paths in the network are large. The example algorithm below shows a method that addresses all these issues. Example Algorithm Variables: N /* number of bits to be used for sequence number */ rec_seq_no /* the sequence number of the received packet */ select_counter /* N bits counter at the receiver that keeps track of the sequence number of next expected packet */ packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 8] window_sz /* size of the window; must be less than 2^N */ Initialization: Rec_seq_no = 0; select_counter = 0; Algorithm: Sender insert rec_seq_no to the inner "label" of the packet; transmit one copy of the packet on each mated LSPs; rec_seq_no ++; Selector If(rec_seq_no is outside the sliding window defined by [select_counter, select_counter+window_sz]) reject the packet; else /* the rec_seq_no is in the window*/ { accept the packet; select_counter = rec_seq_no +1; } 7. Remarks on the example packet 1+1 protection scheme a) The scheme requires intelligence at the edge nodes only. Further, the scheme does not require any explicit fault detection or notification. This is implied by the packet selection scheme at the egress, which is carried out based on the sequence number and the locally maintained counters. b) Dual feed requires duplication of packets at ingress. This introduces some additional minimum processing at the ingress. Selection requires comparisons of the sequence number carried in the packet with the counter value maintained at the receiver leading to a packet accept or reject condition. For hardware or software implementation, the processing cost is minimum. Another performance impact is the bandwidth cost due to the sequence number carried in the packets. This introduces some additional packet overhead depending on the length of sequence number. With a 32-bit sequence number using the whole 4 Bytes label, the bandwidth overhead is merely 4% for short 100 Bytes packets. c) The loss performance of the proposed service can be seen as follows. As the selection mechanism at the egress node takes packets from either LSP, the service in fact may compensate, although not required, the packet losses in the network. In the best case, this could result in zero loss although each LSP may experience losses. On the other hand, in the worse case, the net packet loss would be the sum of the losses of both LSPs. In other words, the loss performance of the service is no worse and at the same order of magnitude of the worst performing LSP and sometimes could be much packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 9] better. d) The delay performance of the proposed service can be seen as follows. Since the algorithm always selects, without buffering, the first eligible arriving packet of the pair, the delay performance is always better than either of the LSPs. e) The size of the window should be sized to be larger than the maximum number of consecutive packets a working LSP can loose. As a result, it is assured that the sequence number of the next packet from the same LSP will always fall within the window and will be accepted. f) The size of the window should be sized such that the delay differential of the packet pairs traversing the mated LSPs, if not lost, is never more than (2^N - size of the window) packets. As a result, it is assured that an old packet will not be mistaken new and causes mis-delivery. g) In case of a single failure in the network, other than the ingress or egress nodes, only one of the mated diverse LSPs will be affected. The surviving LSP will continue on delivering the packets. If the surviving LSP is the leading LSP, i.e., last received and selected packet was from this LSP, then the select function at the egress node will continue to accept packets from it whereas if the surviving LSP is the trailing LSP then the select function rejects packets until it sees a packet whose sequence number falls within the sliding window. Upon successful repair of the failed LSP, one may wish to put it back to service. In this "reverted restoration mode", the simplest approach would be to have the first dual-fed packet get the usual next sequence number, next to the one assigned to the last packet fed only on the surviving LSP alone. Various enhancements can be made to manage the service loss performance during this operation, if desired. 8. Security Considerations This document does not introduce new security issues. 9. Acknowledgements The authors thank their colleagues Autumn Liu, Tao Liu, John Oliva, Bharath Ramanna, and Ajay Sathyanath for their implementation suggestions. The authors would like to thank Vinay Purohit for suggesting the use of a window in the example packet selection algorithm; and Antonio DeSimone, Bharat Doshi, Enrique Hernandez- Valencia, Wing-Cheong Lau, and John Vargas for their comments on this work. 10. References [1] V. Sharma et. al, "Framework for MPLS-based Recovery", draft- ietf-mpls-recovery-frmwrk-03.txt. packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 10] [2] "Protection Switching for MPLS Networks", ITU - Study Group 13, Draft Recommendation Y.1720, 2002 [3] S. Kini, et. al, "Shared Backup label Switched Path Restoration", draft-kini-restoration-shared-backup-01.txt. [4] D. Gan et. al, "A Method for MPLS LSP Fast-Reroute Using RSVP Detours, " draft-gan-fast-reroute-00.txt [5] A. Chiu et. al, "Features and Requirements for the Optical Layer Control Plane", raft-chiu-strand-unique-olcp-02.txt. [6] L. Martini et. al, "Encapsulation methods for Transport of layer 2 Frames over IP and MPLS Networks", draft-martini-l2circuit-encap- mpls-04.txt. 11. Authors' Addresses Ramesh Nagarajan Lucent Technologies, Bell Labs Room 3M-335, 101 Crawfords Corner Road Holmdel, NJ 07733-3030 Phone: 732 949 2761 Email: rameshn@lucent.com Akber Qureshi Lucent Technologies, Bell Labs Room 3M-320, 101 Crawfords Corner Road Holmdel, NJ 07733-3030 Phone: 732 949 4791 Email: mqureshi@lucent.com Y.T. Wang Lucent Technologies, Bell Labs Room 3J-302, 101 Crawfords Corner Road Holmdel, NJ 07733-3030 Phone: 732 949 0676 Email: ytwang@lucent.com 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 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 packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002 draft-nagarajan-ccamp-mpls-packet-protection-00.txt [Page 11] in the Internet Standards process must be followed, or as required to translate it into 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. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. packet-protection-mpls-Nagarajan-Qureshi-Wang March 2002