Abstract:
Improved detection of specific BFD LSP path failures is herein disclosed. The improved detection described herein allow for faster fault isolation of a failure along a LSP path, which in turn may allow for faster repair of the failure. When opening a BFD session with a LSP egress node, the LSP ingress node provides the LSP egress node a path descriptor along with the BFD Discriminator. If a BFD failure is detected at the LSP egress node, the LSP egress node can signal an alarm that includes a full description of the path.

Description:
FIELD OF THE INVENTION 
     The present disclosure relates generally to failure detection of network paths. For example, the present disclosure can facilitate the detection of which path, among a plurality of paths between a specific LSP ingress router and a specific LSP egress router, has failed. 
     BACKGROUND OF THE INVENTION 
     In computer networking and telecommunications, Multiprotocol Label Switching (“MPLS”) is a data-carrying mechanism, which emulates some properties of a circuit-switched network over a packet-switched network. MPLS is often used to transport data packets such as those already in the form of Internet Protocol (“IP”). MPLS is an Internet Engineering Task Force initiative that integrates Layer 2 (i.e., the data link layer) information about network links (bandwidth, latency, utilization) into Layer 3 (i.e., the network layer) within a particular autonomous system in order to simplify and improve IP packet exchange. Thus, MPLS operates at an OSI Model layer that is generally considered to lie between traditional definitions of Layer 2 and Layer 3. It can be used to carry many different kinds of traffic, including IP packets, as well as native ATM, SONET, and Ethernet frames. MPLS provides a number of powerful capabilities, such as traffic engineering, etc. 
     In MPLS, data transmission occurs on Label-Switch Paths (“LSPs”). LSPs are a sequence of labels at each and every node along the path from the source to the destination. Each data packet encapsulates and carries the labels during their journey from source to destination. High-speed switching of data is possible because the fixed-length labels are inserted at the very beginning of the packet or cell and can be used by hardware to switch packets quickly between links. 
     The Forwarding Equivalence Class (“FEC”) to which a packet is assigned is encoded as a short fixed length value known as a “label.” With MPLS, incoming packets are assigned with a label when the packets enter a MPLS network. When a packet is forwarded to its next hop, the label is sent along with it; that is, the packets are “labeled” before they are forwarded. At subsequent hops, there is no further analysis of the packet&#39;s network layer header. Rather, the label is used as an index into a table, which specifies the next hop, and a new label. The old label is replaced with the new label, and the packet is forwarded to its next hop. In the MPLS forwarding paradigm, once a packet is assigned to a FEC, subsequent routers do no further header analysis; the labels drive all forwarding. This has a number of advantages over conventional network layer forwarding. 
     Bidirectional Forwarding Detection (“BFD”) is a network protocol used to detect forwarding. It provides low-overhead detection of faults even on physical media that don&#39;t support failure detection of any kind, such as Ethernet, virtual circuits, tunnels, and MPLS LSPs. BFD establishes a session between two endpoints over one or more links. 
     One desirable application of BFD is to detect a MPLS LSP data plane failure. LSP-Ping is an existing mechanism for detecting MPLS data plane failures and for verifying the MPLS LSP data plane against the control plane. A combination of LSP-Ping and BFD can be used to provide faster data plane failure detection and/or make it possible to provide such detection on a greater number of LSPs. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above and further advantages of this invention may be better understood by referring to the following description in conjunction with the accompanying drawings, in which like numerals indicate like structural elements and features in the various figures. The drawings are not meant to limit the scope of the invention. For clarity, not every element may be labeled in every figure. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention. 
         FIG. 1  illustrates an example network comprising a plurality of LSP paths from a LSP ingress node to a LSP egress node. 
         FIG. 2  illustrates an example computer system architecture for a computer system that performs operations useful in detecting LSP path failures in accordance with embodiments disclosed herein. 
         FIG. 3  illustrates example operations performable by a LSP ingress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. 
         FIG. 4  illustrates additional example operations performable by a LSP ingress node and useful in detecting LSP path failure in accordance with embodiments disclosed herein. 
         FIG. 5  illustrates additional example operations performable by a LSP ingress node and useful in detecting LSP path failure in accordance with embodiments disclosed herein. 
         FIG. 6  illustrates an example time-length-value entry useful in detecting LSP path failure in accordance with embodiments disclosed herein. 
         FIG. 7  illustrates example operations performable by a LSP egress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. 
         FIG. 8  illustrates additional example operations performable by a LSP egress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. 
     
    
    
     DESCRIPTION OF EXAMPLE EMBODIMENTS 
     Overview 
     When running a multihop Bidirectional Forwarding Detection (“BFD”) session between a conventional ingress node of the BFD session and a conventional egress node of the BFD session, multiple paths may exist between the ingress node and the egress node. Because of the existence of the multiple paths, an egress node detecting a BFD fault is unaware of which specific path of the multiple paths has experienced the fault. For example, when running multihop Bidirectional Forwarding Detection (“BFD”) for Multiprotocol Label Switching (“MPLS”) with multiple Label Switched Paths (“LSPs”) from a conventional LSP ingress node to a conventional LSP egress node, the BFD session at the conventional LSP egress node is unable to report which specific LSP path has experienced a fault. 
     Inventive matter discussed herein deviates with respect to and improves upon conventional detection of path failures in a BFD session and other technology known in the prior art. Embodiments described herein allow for faster fault isolation of a failure along a path, such as a LSP, in a BFD session, which in turn may allow for faster repair of the failure. 
     A first embodiment disclosed herein provides logic encoded in one or more tangible media for execution and, when executed, operable to perform operations useful in detecting specific path failures in a BFD session. The operations can be performed at an ingress node, such as a LSP ingress node, and include discovering a plurality of paths between an ingress node and an egress node. A path descriptor for each of the plurality of paths is then constructed; wherein each path descriptor includes a plurality of node descriptors and each node descriptor includes a downstream IP address. Each path descriptor is then associated with a BFD discriminator that is locally unique to the path&#39;s ingress node. For each of the plurality of paths, a BFD session with the path&#39;s egress node is bootstrapped, wherein the bootstrapping of the BFD session includes providing the path&#39;s egress node with the path descriptor and the associated BFD discriminator. 
     A second embodiment disclosed herein provides logic encoded in one or more tangible media for execution and, when executed, operable to perform operations useful in detecting specific path failures in a BFD session. The operations can be performed at an egress node, such as a LSP egress node, and include bootstrapping a BFD session with an ingress node of a path, wherein the bootstrapping includes receiving, from the path&#39;s ingress node, a path descriptor for the path and a BFD discriminator associated with the path descriptor, wherein the path descriptor includes a plurality of node descriptors and each node descriptor includes a downstream IP address. The logic may then detect a failure in the BFD session. If the logic detects such a failure, the logic may signal an alarm to indicate the detected failure, wherein the alarm includes the path descriptor for the path and the associated BFD discriminator. 
     It is to be understood that the inventive matter disclosed herein may be embodied as logic encoded in one or more tangible media for execution and, when executed, operable to perform operations disclosed herein. The logic may be embodied strictly as a software program, as software and hardware, or as hardware alone. The features disclosed herein may be employed in data communications devices and other computerized devices and software systems for such devices, such as those manufactured by Cisco Systems, Inc. of San Jose, Calif. 
     DETAILED DESCRIPTION 
       FIG. 1  illustrates an example network  100  comprising a plurality of (i.e., multiple) LSPs from a LSP ingress node to a LSP egress node. Two LSPs are shown in  FIG. 1 . The first LSP comprises, in order, the LSP Ingress node, LSR- 1 A, LSR- 1 B, LSR- 1 C, LSR- 1 D, and the LSP egress node. The second LSP comprises, in order, the LSP Ingress node, LSR- 2 A, LSR- 2 B, LSR- 2 C, LSR- 2 D, and the LSP egress node. In particular embodiments, the two LSPs may be equal-cost multiple paths (“ECMPs”). The cost in determining whether multiple paths are equal cost may be path latency, jitter, delay, number of links, or other link/path attributes. In operation, packets may enter a LSP at the LSP ingress node from the customer edge (“CE”) router CE 1  and exit the LSP at the LSP egress router where they are sent to the customer edge router CE 2 . 
     Embodiments disclosed herein may be advantageously utilized in networks other that the network  100  shown in  FIG. 1 . For example, particular embodiments may include networks comprising multiple autonomous systems. Autonomous systems may be “stitched” together at routers commonly referred to as Autonomous System Border routers or AS-BRs. Thus, LSPs may be “stitched” together between autonomous systems and run the same BFD session end-to-end. 
       FIG. 2  illustrates an example computer system architecture  200  for a computer system  210  that performs operations useful in detecting LSP path failures in accordance with embodiments disclosed herein. The computer system  210  may be any type of computerized system such as a personal computer, workstation, portable computing device, mainframe, server, or the like. In this example, the computer system  210  includes an interconnection mechanism  211  that couples a memory system  212 , a processor  213 , and a communications interface  214 . The communications interface  214  allows the computer system  210  to communicate with external devices or systems. 
     The memory system  212  may be any type of computer-readable medium that is encoded with an application  220 -A that represents software code such as data and/or logic instructions (e.g., stored in the memory or on another computer-readable medium such as a disk) that embody the processing functionality of embodiments of the invention as explained above. The processor  213  can access the memory system  212  via the interconnection mechanism  211  in order to launch, run, execute, interpret, or otherwise perform the logic instructions of the application  220 -A for the host in order to produce a corresponding process  220 -B. In other words, the process  220 -B represents one or more portions of the application  220 -A performing within or upon the processor  213  in the computer system  210 . 
     It is to be understood that embodiments of the invention include the applications (i.e., the un-executed or non-performing logic instructions and/or data) encoded within a computer-readable medium such as a floppy disk, hard disk or in an optical medium, or in a memory type system such as in firmware, read only memory (ROM), or, as in this example, as executable code within the memory system  212  (e.g., within random access memory or RAM). It is also to be understood that other embodiments of the invention can provide the applications operating within the processor  213  as the processes. While not shown in this example, those skilled in the art will understand that the computer system  210  may include other processes and/or software and hardware components, such as an operating system, which have been left out of this illustration for ease of description of the invention. 
       FIG. 3  illustrates example operations  300  performable by a LSP ingress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. That is, the ingress node may comprise logic encoded in one or more tangible media for execution and, when executed, operable to perform the operations  300  illustrated in  FIG. 3 . For example, the LSP ingress node may be implemented by the computer system  210  of  FIG. 2 . 
     In step  310 , a LSP ingress node discovers a plurality of label switched paths (“LSPs”) between the LSP ingress node and a LSP egress node. In particular embodiments, the ingress node will discover all LSPs between the LSP ingress node and the LSP egress node. The LSP ingress node may use techniques known in the art for discovering multiple LSPs between the LSP ingress node and the LSP egress node. For example, the LSP ingress node may perform an ECMP Tree Trace as specified in RFC 4379 to discover all ECMPs for a Forwarding Equivalence Class (“FEC”). A FEC is used in MPLS to describe a set of packets with similar or identical characteristics that may be forwarded the same way. That is, the packets may be bound to the same MPLS label. Characteristics determining the FEC of a higher-layer packet depend on the configuration of the router, but typically this is at least the destination IP address. Quality of Service class is also often used. Thus, a FEC tends to correspond to a LSP. However, the reverse is not true. A LSP may be, and usually is, used for multiple FECs. 
     In step  320 , the LSP ingress node constructs a path descriptor for each of the plurality of LSPs, wherein each path descriptor includes a plurality of node descriptors and each node descriptor includes a downstream IP address. In particular embodiments, each path descriptor may include other information in additional to the node descriptors. In particular embodiments, the node descriptor may include other information in addition to the downstream IP address. The precise format of the path descriptor may vary from embodiment to embodiment. In particular embodiments, the path descriptor is constructed in the form of a type-length-value (“TLV”) entry. In step  330 , the LSP ingress node associates each path descriptor with a BFD discriminator that is locally unique to the LSP ingress node. 
     In step  340 , the LSP ingress node bootstraps a BFD session with the LSP egress node for each of the plurality of LSPs. Conventional technologies provide multiple means for bootstrapping a BFD session. Techniques for bootstrapping a BFD session include, for example, automatic bootstrapping using a protocol such as LSP ping, internal code detecting protocol/neighbor adjacency, or strictly manual. In embodiments disclosed herein, the bootstrapping of the BFD session includes providing the LSP egress node with the path descriptor and the associated BFD discriminator. The LSP ingress node may use different techniques, in different embodiments, for bootstrapping the BFD session and providing the LSP egress node with the path descriptor and the associated BFD discriminator. Thus, conventional techniques for bootstrapping a BFD session can be modified to provide the LSP egress node with the path descriptor and the associated BFD discriminator. 
       FIGS. 4 and 5  illustrate additional example operations performable by a LSP ingress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. In step  410 , the LSP ingress node discovers a plurality of LSPs between the LSP ingress node and a LSP egress node. Step  410  comprises step  412 . In step  412 , the LSP ingress node performs a tree trace to discover all equal-cost multiple paths for a forwarding equivalence class. After step  410 , the LSP ingress node performs step  320  and  330  as described above. 
     After step  330 , the LSP ingress node performs step  540 . In step  540 , the LSP ingress node bootstraps a BFD session with the LSP egress node for each of the plurality of LSPs. The bootstrapping of the BFD session includes providing the LSP egress node with the path descriptor and the associated BFD discriminator. In particular embodiments, step  540  may comprise at least one of the steps in the group consisting of step  542 , step  544 , step  546 , and step  548 . 
     In step  542 , the LSP ingress node sends a LSP-ping echo-request containing the path descriptor and the associated BFD discriminator to the LSP egress node. In response to the LSP-ping echo-request, the LSP egress node may send a LSP-ping echo-reply to the LSP ingress node. Other means of bootstrapping a BFD session may be used in other embodiments. For example, in particular embodiments static programming may be utilized to bootstrap a BFD session between the LSP ingress node and the LSP egress node. 
     In step  544 , the LSP ingress node provides the LSP egress node with the path descriptor in a TLV entry. TLV entries are generally known in the art. In particular embodiments, step  544  may be combined with step  542 . That is, the LSP ingress node may send, to the LSP egress node, a LSP-ping echo-request containing the path descriptor in a TLV entry. In step  546 , the LSP ingress node provides the LSP egress node with the path descriptor in a TLV entry that also includes a field indicating the number of node descriptors in the path descriptor. In step  548 , the LSP ingress node provides the LSP egress node with the path descriptor in a TLV entry that also includes a field indicating the address type and length (e.g., in number of octets) of the downstream IP addresses as well as the length (e.g., in number of octets) of any downstream interface fields. 
       FIG. 6  illustrates an example TLV entry  600  useful in detecting LSP path failures in accordance with embodiments disclosed herein. The TLV entry  600  includes an Address Type field  602 . The Address Type field  602  contains a value that indicates the address type and length of the downstream IP addresses (i.e., IP address of nodes in the LSP, such as LSR- 1 A of  FIG. 1 ) as well as the length of any downstream interface fields. For example, the Address Type field  602  may be set to one of the values shown in the rows of Table 1. Other address types, in addition to or in place of the types listed in Table 1 may be advantageously utilized in particular embodiments. 
     
       
         
               
               
               
             
           
               
                 TABLE 1 
               
               
                   
               
               
                 Type No. 
                 Address Type 
                 Octets 
               
               
                   
               
             
             
               
                 1 
                 IPv4 Numbered 
                 16 
               
               
                 2 
                 IPv4 Unnumbered 
                 16 
               
               
                 3 
                 IPv6 Numbered 
                 40 
               
               
                 4 
                 IPv6 Unnumbered 
                 28 
               
               
                   
               
             
          
         
       
     
     The Number of Addresses field  604  in the TLV entry  600  contains a value indicating the number of IP Address/BFD Discriminator pairs in the TLV entry  600 . The Downstream IP Address field  606  contains the IP Address of one of the nodes in the LSP. The Downstream IP Address field  608  contains the IP Address of another one of the nodes in the LSP. The TLV entry  600  may contain additional Downstream IP Addresses  610  so that the total number of IP Addresses in the TLV entry  600  equals the value in the Number of Addresses field  604 . 
       FIG. 7  illustrates example operations  700  performable by a LSP egress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. That is, the ingress node may comprise logic encoded in one or more tangible media for execution and, when executed, operable to perform the operations  700  illustrated in  FIG. 7 . For example, the LSP egress node may be implemented by the computer system  210  of  FIG. 2 . 
     In step  710 , a LSP egress node bootstraps a BFD session with a LSP ingress node of a LSP, wherein the bootstrapping includes receiving, from the LSP ingress node, a path descriptor for the LSP and a BFD discriminator associated with the path descriptor, wherein the path descriptor includes a plurality of node descriptors and each node descriptor includes a downstream IP address. In step  720 , the LSP egress node detects a failure in the BFD session. The LSP egress node may use conventional techniques for detecting a BFD session failure. In step  730 , the LSP egress node signals an alarm to indicate the detected failure, wherein the alarm includes the path descriptor for the LSP and the associated BFD discriminator. 
       FIG. 8  illustrates additional example operations performable by a LSP egress node and useful in detecting LSP path failures in accordance with embodiments disclosed herein. In step  810 , a LSP egress node bootstraps a BFD session with a LSP ingress node of a LSP, wherein the bootstrapping includes receiving, from the LSP ingress node, a path descriptor for the LSP and a BFD discriminator associated with the path descriptor, wherein the path descriptor includes a plurality of node descriptors and each node descriptor includes a downstream IP address. Step  810  may comprise at least one of the steps in the group consisting of step  812 , step  814 , step  816 , and step  818 . 
     In step  812 , the LSP egress node receives a LSP-ping echo-request containing the path descriptor and the associated BFD discriminator from the LSP ingress node. In particular embodiments, step  812  corresponds to step  542 . For example, the LSP-ping echo-request sent by the LSP ingress node in step  542  may be the LSP-ping echo-request received by the LSP egress node in step  812 . 
     In step  814 , the LSP egress node receives, from the LSP ingress node, the path descriptor in a TLV entry. In particular embodiments, step  814  corresponds to step  544 . For example, the TLV entry provided by the LSP ingress node in step  544  may be the TLV entry received by the LSP egress node in step  814 . 
     In step  816 , the LSP egress node receives, from the LSP ingress node, the path descriptor in a TLV entry that also includes a field indicating the number of node descriptors in the path descriptor. In particular embodiments, step  816  corresponds to step  546 . For example, the TLV entry provided by the LSP ingress node in step  546  may be the TLV entry received by the LSP egress node in step  816 . 
     In step  818 , the LSP egress node receives, from the LSP ingress node, the path descriptor in a TLV entry that also includes an address-type field indicating the address type and length of the downstream IP addresses as well as the length of any downstream interface fields. In particular embodiments, step  818  corresponds to step  548 . For example, the TLV entry provided by the LSP ingress node in step  548  may be the TLV entry received by the LSP egress node in step  818 . 
     Having described preferred embodiments of the invention it will now become apparent to those of ordinary skill in the art that other embodiments incorporating these concepts may be used. Additionally, the software included as part of the invention may be embodied in a computer program product that includes a computer-readable medium. For example, such a computer-readable medium can include a readable memory device, such as a hard drive device, a CD-ROM, a DVD-ROM, or a computer diskette, having computer-readable program code segments stored thereon. The computer-readable medium can also include a communications link, either optical, wired, or wireless, having program code segments carried thereon as digital or analog signals. 
     Improved detection of specific BFD LSP path failures is herein disclosed. While the present invention has been shown and described herein with reference to specific embodiments thereof, it should be understood by those skilled in the art that variations, alterations, changes in form and detail, and equivalents may be made or conceived of without departing from the spirit and scope of the invention. Accordingly, the scope of the present invention should be assessed as that of the appended claims and by equivalents thereto.