Patent Description:
A computer network is a collection of interconnected computing devices that can exchange data and share resources. Example network devices include layer two devices that operate within the second layer of the Open Systems Interconnection (OSI) reference model, i.e., the data link layer, and layer three devices that operate within the third layer of the OSI reference model, i.e., the network layer. Network devices within computer networks often include a control unit that provides control plane functionality for the network device and forwarding components for routing or switching data units. In some cases, for example, a network device may include a one or more line cards, one or more packet processors, and one or more ports coupled to a switch fabric that collectively can provide a forwarding plane for forwarding network traffic.

The control plane functions provided by the control unit include storing network topologies in the form of a routing information base (RIB), executing routing protocols to communicate with peer routing devices to maintain and update the RIB, and providing a management interface to allow user access and configuration of the network device. The control unit maintains routing information that represents the overall topology of the network and defines routes to destinations within the network.

The control unit derives a forwarding information base (FIB) that includes a number of forwarding entries generated by the control unit in accordance with the routing information and control information. The control unit installs the forwarding structures within the data plane to programmatically configure the forwarding components. The data and instructions that constitute the forwarding entries define an internal forwarding path for each incoming packet received by the network device. For example, to generate a route table lookup forwarding entry, the control unit selects routes defined by the network topology and maps packet key information (e.g., destination information and other select information from a packet header) to one or more specific next hop network devices and ultimately to one or more specific output interfaces of interface cards of the network device. In some cases, the control unit may install the forwarding structures into each of the packet processors to update the forwarding table within each of the packet processors and control traffic forwarding within the data plane. Bifurcating control and data plane functionality allows the forwarding table in each of packet processors to be updated without degrading packet forwarding performance of the network device. <CIT> discloses a method and device for establishing a backup path, and a method and device for selecting backup path.

In general, the disclosure describes techniques to determine backup paths from a first network device to a second network device that reduce the risk of failure in network traffic communication between the first network device and the second network device. A routing protocol process (e.g., a routing protocol daemon (RPD)) of the first network device can determine a primary path and multiple backup paths between the first network device and the second network device. The backup paths include network device components involved in forwarding packets through the first network device. Examples of such components include line cards, packet processors, and ports. A path between the first network device and the second network device typically includes line card, a packet processor, and a port coupling the line card to a network medium. The RPD can assign a priority to the backup paths based on which, if any, network device components in the primary path are also result in a backup path. In the event of a failure of the primary path, the RPD can reconfigure the network device to use the highest priority backup path.

Techniques described herein determine one or more backup paths for a primary path from a network device to another network device. A routing protocol process (e.g., RPD) of the network device can determine a primary path and multiple backup paths between the first network device and the second network device. The primary path and backup paths include network device components internal to the network device that are involved in forwarding packets through the network device. For example, a path between the network device and the other network device typically includes a line card, a packet processor, and a port coupling the line card to a network medium. As noted above, the RPD can assign a priority to the backup paths based on which, if any, network device components in the primary path are also result in a backup path. In the event of a failure of the primary path, the network device can implement a local repair mechanism that reconfigures the network device to use the highest priority backup path.

As an example, a network device may determine a primary path that includes a line card, a packet processor, and a port, where the line card, packet processor and port can be in what will be referred to as a failure hierarchy. In such a hierarchy, a network device component failure at one level of the hierarchy results in the failure in the ability of network component devices lower in the hierarchy to be able to transmit network packets. For example, a line card may include one or more packet processors, such as packet forwarding engines (PFEs). The packet processor may process network packets for transmission through a port on the line card. In this example, the line card is at the highest level of the hierarchy, the packet processor is at a middle level of the hierarchy, and the port is at the lowest level of the hierarchy. A failure of the line card results in failure of any packet processors and any ports associated with those packet engines to be able to transmit network packets. A failure in the packet processor results in failure of any ports associated with the packet engine to transmit network packets. However, other packet processors on the line card may still be functional and may be able to transmit packets through their associated ports. A failure in a port affects only the port. Other ports associated with the packet processor may still be able to transmit network packets, and ports associated with other packet processors may still be able to transmit network packets.

Thus, a backup path that shares a line card with the primary path will likely fail when the shared line card fails, but will not fail if the backup path uses a different line card. A backup path that shares a packet processor will likely fail when the shared packet processor fails, but will not necessarily fail if it uses a different packet processor on the same line card. A backup path that shares a port will likely fail if the port fails, but will not necessarily fail if assigned a different port, even if the different port is associated with the same packet engine.

According to the techniques described herein, backup paths are selected in a priority that favors paths that do not share network device components, or if shared, do so at a lower level in the hierarchy. In the event of a failure in the primary path, the backup path having the highest priority is selected to replace the primary path. This highest priority backup path is less likely to share any network device components, or, if it does share network device components, does so at a low level in the failure hierarchy.

Current network devices typically do not take the risk of failure associated with shared network device components into account when determining backup paths for a primary path. Instead, current systems typically select a "next best" path as a backup path. However, the next best path may share network device components with the primary path such that a failure in the primary path may also result in a failure in the backup path. The techniques described herein can provide technical advantages over such current systems. For example, a current network device may utilize heuristics to determine a "best path" to a network destination. Additionally, the network device may utilize the same or similar heuristics to determine a "next best" path as a backup path. The primary path and the backup path can be programmed into a packet processor. However, the heuristics used by the current network device may compute a primary path and the backup path that utilize the same packet processor. In the event of a failure in the packet processor used in the primary path, the network device will attempt to use the backup path regardless of whether it is on the same packet processor as the primary path. Because both the primary path and the backup path share the failed packet processor, there may be no available path currently computed for the network destination. As a result, the current network device must recompute the primary path and backup path, which can take an undesirable amount of time and further result in lost packets. Thus, the purpose of having a predefined backup path can be defeated if the backup path shares a packet processor or line card with the primary path and the shared resource fails.

The techniques described herein prioritize selection of backup paths that do not share network device components, or share network device components at a lower level in the above-described failure hierarchy. As a result, a failure of a network device component in the primary path is less likely to be the cause of failure in a backup path. This can result dropping fewer network packets, thus improving network device performance. Further, recovery from a failure in the primary backup path may be quicker because the network device may not need to try multiple backup paths in order to reestablish communications with another network device, further improving network device performance.

<FIG> is a block diagram illustrating an example network environment in which a network includes a network device configured in accordance with techniques described in this disclosure. For purposes of example, the principles of the invention are described with respect to a simplified network environment <NUM> of <FIG> in which a network device <NUM> (sometimes referred to as a "core router") communicates with edge routers 104A and 104B (collectively "edge routers <NUM>") to provide customer networks 106A-106C (collectively "customer networks <NUM>") with access to network <NUM>. Network <NUM> may be, for example, a service provider network or a cloud computing network.

Although not illustrated, the network <NUM> may be coupled to one or more networks administered by other providers, and may thus form part of a large-scale public network infrastructure, e.g., the Internet. Consequently, the customer networks <NUM> may be viewed as edge networks of the Internet. The network <NUM> may provide computing devices within the customer networks <NUM> with access to the Internet, and may allow the computing devices within the customer networks <NUM> to communicate with each other. In another example, the service provider network <NUM> may provide network services within the core of the Internet. As another example, the network <NUM> may provide services (e.g., cloud computing services, etc.) to the computing devices with the customer networks <NUM>. In either case, the network <NUM> may include a variety of network devices (not shown) other than the router <NUM> and the edge routers <NUM>, such as additional routers, switches, servers, or other devices.

In the illustrated example, the edge router 104A is coupled to the customer network 106A via access link 110A, and the edge router 104B is coupled to the customer networks 106B and 106C via additional access links 110B and 110C. The customer networks <NUM> may be networks for geographically separated sites of an enterprise. The customer networks <NUM> may include one or more computing devices (not shown), such as personal computers, laptop computers, handheld computers, workstations, servers, switches, printers, customer data centers or other devices. The configuration of the network environment <NUM> illustrated in <FIG> is merely an example. The service provider network <NUM> may be coupled to any number of the customer networks <NUM>. Nonetheless, for ease of description, only an example number of customer networks 106A-106C are illustrated in <FIG>. Many different types of networks beside networks <NUM> may employ an instance of the router <NUM>, including customer/enterprise networks, transport networks, aggregation or access networks, and so forth. Network traffic may flow, for example, from one customer network 106A to another customer network 106C through network device <NUM>.

Network device <NUM> may communicate with other network devices (e.g., other core routers, switches etc.) for communications within network <NUM> in addition to communicating with edge routers <NUM>. The network device <NUM> may exchange routing information with the edge routers <NUM> and/or controller <NUM> in order to maintain an accurate representation of the topology of the network environment <NUM>. As described below, the network device <NUM> may consist of a plurality of cooperative routing components operating as a single node within the service provider network <NUM>. The network device <NUM> includes a chassis (not shown in <FIG>) that couples various internal routing components such as line cards, switching fabric cards, packet processors, routing engine cards, etc. together. A line card may be a flexible physical interface card (PIC) concentrator (FPC), dense port concentrators (DPCs), and modular port concentrators (MPCs). Network device <NUM> may determine internal paths to edge routers <NUM> and other core routers that utilize these internal routing components. A routing protocol process, e.g., daemon (RPD) on network device <NUM> may determine a line card, packet processor and a port as a primary path of internal routing components to use when forwarding network packets to a next hop (e.g., another core router or edge router <NUM>). In some aspects, the RPD may use various heuristics to determine a "best path" as the primary path. The RPD can also use the techniques described herein to determine a backup path.

One of the internal routing components of a primary path through network device <NUM> may, from time to time, fail (i.e., become unavailable to process and forward network traffic through network device <NUM> to the next hop). In this case, the network device may begin to use the backup path for forwarding network packets to the next hop.

In the illustrated example, service provider network <NUM> includes a controller <NUM>. In some examples, controller <NUM> may comprises software-defined networking controller. Controller <NUM> may monitor service provider network <NUM> and provide an interface for administrators to configure and/or monitor devices within service provider network <NUM> (e.g., network device <NUM>, edge routers <NUM>, etc.). In some examples, controller <NUM> may perform diagnostic functions and display health of network <NUM> in a graphical user interface to facilitate maintenance of network <NUM>. In other examples, controller <NUM> may advertise the topology of network <NUM> and/or perform path computation based on the topology of network <NUM> and advertise routing updates to the devices within network <NUM>.

<FIG> is a block diagram illustrating an example network device that determines backup paths in accordance with principles described in this disclosure. In this example, network device <NUM> includes a control unit <NUM> that provides control plane functionality for the device. Network device <NUM> can be an example of network device <NUM> and edge routers <NUM>. In the example illustrated in <FIG>, network device <NUM> includes line card A 204A and line card B 204B (generically referred to as "line card <NUM>"). Line card 204A and line card 204B each include two forwarding components in the form of example packet processors 206A-206B and packet processors 206C - 202D respectively (collectively referred to as "packet processors <NUM>"). Packet processors <NUM> receive and send data packets via associated ports 208A - 208D of line cards 204A and 204B. Each of ports 208A - 208D can be associated with a respective one of packet processors <NUM>. Each of packet processors <NUM> and its associated ports <NUM> may reside on a separate line card for network device <NUM>. As noted above, line cards <NUM> may be PICs, FPCs, DPCs, MPCs, or other types of forwarding units. Each of ports <NUM> may include interfaces for various combinations of layer two (L2) technologies, including Ethernet, Gigabit Ethernet (GigE), and Synchronous Optical Networking (SONET) interfaces. The number of line cards <NUM>, packet processors <NUM> and ports <NUM> for network device <NUM> shown in <FIG> is merely an example. A network device can have a greater or lesser number of line cards <NUM>, packet processors <NUM> and ports <NUM> than that shown in <FIG>.

Packet processors <NUM> process packets by performing a series of operations on each packet over respective internal packet forwarding paths as the packets traverse the internal architecture of network device <NUM>. Packet processors <NUM> can include hardware and/or software packet processors that examine the contents of each packet (or another packet property, e.g., incoming interface) to make forwarding decisions, apply filters, and/or perform accounting, management, traffic analysis, and/or load balancing. The result of packet processing determines the manner in which a packet is forwarded or otherwise processed by packet processors <NUM> to an associated port <NUM>.

Control unit <NUM> can be connected to each of packet processors <NUM> by internal communication link (not shown in <FIG>). The internal communication link may comprise a <NUM> Mbps Ethernet connection, for instance. Control unit <NUM> may include one or more processors (not shown in <FIG>) that execute software instructions, such as those used to define a software or computer program, stored to a computer-readable storage medium (again, not shown in <FIG>), such as non-transitory computer-readable mediums including a storage device (e.g., a disk drive, or an optical drive) and/or a memory such as random-access memory (RAM) (including various forms of dynamic RAM (DRAM), e.g., DDR2 SDRAM, or static RAM (SRAM)), Flash memory, another form of fixed or removable storage medium that can be used to carry or store desired program code and program data in the form of instructions or data structures and that can be accessed by a processor, or any other type of volatile or non-volatile memory that stores instructions to cause the one or more processors to perform techniques described herein. A computer readable medium may also or alternatively include transient media such as carrier signals and transmission media. Alternatively, or in addition, control unit <NUM> may include dedicated hardware, such as one or more integrated circuits, one or more Application Specific Integrated Circuits (ASICs), one or more Application Specific Special Processors (ASSPs), one or more Field Programmable Gate Arrays (FPGAs), or any combination of one or more of the foregoing examples of dedicated hardware, for performing the techniques described herein.

Control unit <NUM> may include a routing protocol daemon (RPD). The RPD can determine a line card, packet processor and a port as a primary path of internal routing components to use when forwarding network packets to a next hop (e.g., another core router or edge router <NUM>). In some aspects, the RPD may use various heuristics to determine a "best path" as the primary path. This primary may be programmed into a packet processor, for example in a forwarding table used by the packet processor. The RPD can use the techniques described herein to determine a backup path that has a relatively low risk of failure should there be a failure in the primary path. For example, one of the internal routing components of a primary path through network device <NUM> may, from time to time, fail (i.e., become unavailable to process and forward network traffic through network device <NUM> to the next hop). The packet processor can utilize the backup path to forward packets to the next hop.

In the example illustrated in <FIG>, an RPD of network device <NUM> has used known techniques to select path 212A as the primary path through to reach router <NUM> via network <NUM>. Path 212A includes line card 204A, packet processor 206A and port P0 208A. Additionally, the RPD has determined three candidate backup paths 212B - 212D. A candidate backup path may have a priority assigned to it based on whether or not the candidate backup path meets the selection criteria for the priority. In some aspects, there can be three priorities, each with their own selection criteria. The three priorities are associated with a risk that the candidate backup path will also fail should the primary path fail. A first priority has a selection criteria that specifies that the primary path and the candidate backup path may both fail only if the network device itself fails. A second priority has a selection criteria that the primary path and the candidate backup path both fail if the primary path and candidate backup path share a line card that fails. A third priority has a selection criteria that the primary path and candidate backup path may both fail if the primary path and the backup path share a packet processor that fails. The priorities can be ordered based on the risk that both the primary path and candidate backup path fail. For example, the first priority is associated with the relatively low risk that both the primary path and backup path fail if the network device fails. The second priority is associated with a risk higher than that of the first priority in that the risk is present that both the primary path and backup path may fail should either the network device or a shared line card fails. The third priority is associated with a risk that is higher than that of the second and first priorities because the risk of failure of both the primary path and backup path is present should any of a shared packet processor, shared line card or the network device itself fails.

Thus, in the example illustrated in <FIG>, candidate backup path 212D meets the selection criteria for the first priority because the path does not share a line card or packet processor with the primary path 212A. That is, candidate backup path 212D utilizes line card 204B, packet processor 206C, and port P0 208D. None of these internal routing components are shared with primary path 212A, thus both primary path 212A and candidate backup path 212D will typically fail only if network device <NUM> fails.

In the example illustrated in <FIG>, candidate backup path 212C meets the selection criteria for the second priority because while the path shares line card 204A with primary path 212A, candidate backup path 212C utilizes packet processor 206B, which is different from packet processor 206A used by primary path 212A. Thus, both primary path 212A and candidate backup path 212C may fail if either network device <NUM> or shared line card 204A fails, but candidate backup path 212C will not necessarily fail if packet processor 206A fails.

In the example illustrated in <FIG>, candidate backup path 212B meets the selection criteria for the third priority because candidate backup path 212B shares line card 204A and packet processor 206A with primary path 212A. Thus, should any of packet processor 206A, line card 204A or network device <NUM> fail, it is likely that both the primary path 212A and candidate backup path 212B will fail. In this example, primary path 212A and candidate backup path 212B share a line card and packet processor, but have different ports (port P0 208A and P1 208B respectively) associated with the same packet processor.

In this example, an RPD or protocol implementing the techniques described herein selects candidate backup path 212D as the backup path because it is the highest priority candidate backup path. The RPD can program packet processors 206A and 206C with the primary path 212A and backup path 212D respectively. Should an internal routing component along primary path 212A fail, packet processing can be performed via backup path 212D.

In some aspects, the selection of a backup path as disclosed herein may be in response to an event. As an example, network device <NUM> may select a backup path using the techniques disclosed herein in response to learning a route for another network device via a routing protocol such as Interior Gateway Protocol (IGP). Further, network device <NUM> may select a backup path in response to the addition of resources such as a new line card or new packet processor.

In some aspects, the techniques to select a backup path as disclosed herein may be enabled or disabled as part of a configuration for network device <NUM>. For example, the network device may enable backup path selection as disclosed herein as a default case, with an option provided for an administrator to disable use of the backup path selection techniques. For example, and administrator may want to avoid loading network device <NUM> with additional functions and checks. In such cases, the administrator can disable the enhanced backup path selection techniques disclosed herein and network device <NUM> may revert to conventional backup path selection techniques, or may avoid backup path calculation altogether. In some aspects, there may be two levels of configuration. A first level determines whether link protection or node protection is enabled, and a second level determines if the enhanced backup path selection techniques disclosed herein are used or if other, perhaps conventional, backup path selection techniques are used. Again, the backup selection techniques disclosed herein may be enabled by default if link protection or node protection is enabled for network device <NUM>.

Line cards <NUM> and packet processors <NUM> may have identifiers (shown in parentheses in <FIG>) associated with them. The identifiers may be numeric or alphanumeric identifiers. In some aspects, the identifiers can be unique within network device <NUM>. In some aspects, the identifiers may be unique within a network system <NUM>. In some aspects, packet processors <NUM> discover the identifiers of line cards <NUM> and forward the identifiers to an RPD of control unit <NUM> for use in determining backup paths.

The identifiers may be used to determine if the candidate backup path shares an internal routing component with the primary path. For example, an RPD or protocol can compare the identifiers of internal routing components of the primary path and the backup path. If the identifiers are the same, then the RPD or protocol can determine that the primary path shares the internal routing component with the candidate backup path.

In some aspects, control unit <NUM> can forward the identifiers to other network devices such as router <NUM> as part of a link state protocol communication. For example, the identifiers can be advertised to other devices within an Interior Gateway Protocol (IGP) domain. These other network devices can use the identifiers to compute desirable paths between network devices sharing such identifiers. As an example, the identifiers may be advertised in a "constrained shortest path first" (CSPF) algorithm to determine paths between network devices, such as by an ingress network device, a network controller or a path computation engine (PCE). This may be beneficial in network deployments having different vendors or platforms across different network devices.

<FIG> is a block diagram illustrating an example embodiment of network device <NUM> of <FIG> in further detail. In this example, control unit <NUM> provides a control plane <NUM> operating environment for execution of various user-level daemons such as RPD <NUM> executing in user space <NUM>. Control plane <NUM> may provide routing plane, service plane, and management plane functionality for network device <NUM>. Various instances of control unit <NUM> may include additional daemons not shown in <FIG> that perform other control, management, or service plane functionality and/or drive and otherwise manage data plane functionality for network device <NUM>.

RPD <NUM> operates over, and interacts with, kernel <NUM>, which provides a run-time operating environment for user-level processes. Kernel <NUM> may comprise, for example, a UNIX operating system derivative such as Linux or Berkeley Software Distribution (BSD). Kernel <NUM> offers libraries and drivers by which RPD <NUM> may interact with the underlying system. Line card interface <NUM> of kernel <NUM> comprises a kernel-level library by which RPD <NUM> and other user-level processes or user-level libraries may interact with packet processors <NUM>. Line card interface <NUM> may include, for example, a sockets library for communicating with packet processors <NUM> over dedicated network links.

Hardware environment <NUM> of control unit <NUM> comprises microprocessor <NUM> that executes program instructions loaded into a main memory (not shown in <FIG>) from storage (also not shown in <FIG>) in order to execute the software stack, including both kernel <NUM> and user space <NUM> of control unit <NUM>. Microprocessor <NUM> may comprise one or more general- or special-purpose processors such as a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), or any other equivalent logic device. Accordingly, the terms "processor" or "controller," as used herein, may refer to any one or more of the foregoing structures, processing circuitry, or any other structure operable to perform techniques described herein.

RPD <NUM> executes one or more interior and/or exterior routing protocols <NUM> to exchange routing information with other network devices and store received routing information in routing information base <NUM> ("RIB <NUM>"). RIB <NUM> may include information defining a topology of a network, including one or more routing tables and/or link-state databases. RPD <NUM> resolves the topology defined by routing information in RIB <NUM> to select or determine one or more active routes through the network and then installs these routes to forwarding information base (FIB) <NUM>. As used here, the information in the RIB <NUM> used to define each route is referred to as a "routing entry. " Typically, RPD <NUM> generates FIB <NUM> in the form of a radix or other lookup tree to map packet information (e.g., header information having destination information and/or a label stack) to next hops and ultimately to interface ports of line cards <NUM> associated with respective packet processors <NUM>.

In some aspects, RPD <NUM> may implement the techniques described herein to select a backup path from candidate backup paths. In some aspects, a protocol <NUM> may implement the techniques described herein to select a backup path from candidate backup paths. In some aspects, RPD <NUM> and a protocol <NUM> may cooperate to implement techniques described herein to select a backup path from candidate backup paths. In the example shown in <FIG>, protocols that may implement the techniques described herein include IGP <NUM>, Resource Reservation Protocol (RSVP) <NUM>, Protocol Independent Multicast (PIM) <NUM>, PIM Multicast only Fast ReRoute (MoFRR) <NUM>, and Intermediate System to Intermediate System (ISIS) Loop Free Alternate (LFA) <NUM>. Other protocols not shown in <FIG> may also implement the techniques described herein.

Packet processors <NUM> implement data plane <NUM> (also known as a "forwarding plane") functionality to handle packet processing from ingress interfaces on which packets are received to egress interfaces (e.g., ports <NUM>, <FIG>) to which packets are sent. Data plane <NUM> determines data packet forwarding through network device <NUM>, applies services, rate limits packet flows, filters packets, and otherwise processes the packets using forwarding table <NUM> installed by control plane <NUM> to data plane <NUM>. RPD <NUM> may program a primary path and a backup path in the appropriate forwarding table <NUM> of a packet processor <NUM> using line card interface <NUM> to communicate the primary path and backup path to the packet processor 206A. Line card 204A may include a microprocessor <NUM> that may execute a microkernel to provide an operating environment for processing packets through packet processor <NUM>.

Each packet processor of packet processors <NUM> processes packets by performing a series of operations on each packet over respective internal packet forwarding paths as the packets traverse the internal architecture of network device <NUM>. Packet processor 206A, for instance, may include one or more configurable hardware chips (e.g., a chipset) that, when configured by applications executing on control unit <NUM>, define the operations to be performed by packets received by packet processor 206A. Each chipset may in some examples represent a "packet forwarding engine" (PFE). Each chipset may include different chips each having a specialized function, such as queuing, buffering, interfacing, and lookup/packet processing. Each of the chips may represent application specific integrated circuit (ASIC)-based, field programmable gate array (FPGA)-based, or other programmable hardware logic. A single line card may include one or more packet processors <NUM>.

Operations may be performed, for example, on each packet by any of a corresponding ingress interface, packet processor <NUM>, an egress interface or other components of network device <NUM> to which the packet is directed prior to egress, such as one or more service cards. Packet processors <NUM> process packets to identify packet properties and perform actions bound to the properties. Each of packet processors <NUM> includes forwarding path elements that, when executed, cause the packet processor to examine the contents of each packet (or another packet property, e.g., incoming interface) and on that basis make forwarding decisions, apply filters, and/or perform accounting, management, traffic analysis, and load balancing, for example. In one example, each of packet processors <NUM> arranges forwarding path elements as next hop data that can be chained together as a series of "hops" in a forwarding topology along an internal packet forwarding path for the network device (e.g., a primary path). The result of packet processing determines the manner in which a packet is forwarded or otherwise processed by packet processors <NUM> from its input interface to, at least in some cases, its output interface (e.g., one of ports <NUM>).

A packet processor <NUM> can include a lookup data structure (e.g., forwarding table <NUM>) to perform lookup operations, such as a tree (or trie) search, a table (or index) search, a filter determination and application, or a rate limiter determination and application. Lookup operations locate a routing entry that matches packet contents or another property of the packet or packet flow, such as the inbound interface of the packet. The routing entry can be used to determine a port to use to forward a network packet to the next hop.

Line card 204A and/or packet processor 206A can communicate information regarding components of data plane <NUM> to RPD <NUM> via line card interface <NUM>. For example, packet processor 206A may communicate Maximum Transmission Unit (MTU), encapsulation type etc. to RPD <NUM>, which can store the information using various conventional data objects such as if_link data object <NUM>, if_device data object <NUM>, and/or if_family data object <NUM>. As noted above, line cards <NUM> and packet processors <NUM> may have identifiers (shown in parentheses in <FIG>) associated with them that can be used to determine if the candidate backup path shares an internal routing component with the primary path. Line cards <NUM> and/or packet processors <NUM> can discover the identifiers of line cards <NUM> and packet processors <NUM>, and can forward the identifiers to an RPD of control unit <NUM> for use in determining backup paths. In some implementations, if_link data object <NUM>, if_device data object <NUM>, and/or if_family data object <NUM> may be modified to include the line card identifiers and the packet processor identifiers. Line card 204A and/or packet processor 206A may use interprocess communication facilities such as sockets to communicate information to RPD <NUM> via line card interface <NUM>.

While <FIG> illustrates only line card 204A in detail, each of line cards <NUM> comprises similar components that perform substantially similar functionality.

<FIG> is a flowchart of an example method to determine backup paths accordance with aspects of techniques described in this disclosure. An RPD receives line card IDs and packet processor IDs from line cards and/or packet processors on a network devices (<NUM>). The RPD or protocol used by the RPD determines a primary path and set of candidate backup paths (<NUM>). The RPD determines if there is a candidate backup path in the set of candidate backup paths that satisfies priority one criteria (<NUM>). For example, the RPD can compare a line card ID and packet processor ID of a line card and packet processor that are in the primary path with line card IDs and packet processor IDs of line cards and packet processors in the set of candidate backup paths. If there is a candidate backup path that has a line card ID and packet processor ID where both are different from the line card ID and packet processor ID of the primary path, that candidate backup path satisfies the priority one criteria and can be selected as the backup path ("YES" branch of <NUM>). The RPD can program the appropriate packet processors with the primary path and priority one backup path (<NUM>).

If no candidate backup path exists that satisfies the priority one criteria ("NO" branch of <NUM>), the RPD can next determine if there is a candidate backup path in the set of candidate backup paths that satisfies the priority two criteria (<NUM>). For example, the RPD can compare line a card ID and packet processor ID of a line card and packet processor that are in the primary path with line card IDs and packet processor IDs of line cards and packet processors in the set of candidate backup paths. If there is a candidate backup path that has a line card ID in the primary path that is the same the line card ID in the candidate backup path, but the packet processor IDs of the primary path and backup paths are different, that candidate backup path satisfies the priority two criteria. This candidate backup path can be selected as the backup path ("YES" branch of <NUM>). The RPD can program the appropriate packet processors with the primary path and priority two backup path (<NUM>).

If no candidate backup path exists that satisfies the priority one criteria or priority two criteria ("NO" branch of <NUM>), the RPD can next determine if there is a candidate backup path in the set of candidate backup paths that satisfies the priority three criteria (<NUM>). For example, the RPD can compare line a card ID and packet processor ID of a line card and packet processor that are in the primary path with line card IDs and packet processor IDs of line cards and packet processors in the set of candidate backup paths. If there is a candidate backup path that has a line card ID and packet processor ID that are the same as those in the primary path, but the port IDs are different, that candidate backup path satisfies the priority three criteria. This candidate backup path can be selected as the backup path ("YES" branch of <NUM>). The RPD can program the appropriate packet processors with the primary path and priority three backup path (<NUM>).

If no candidate backup path exists that satisfies the priority one criteria, priority two criteria, or priority three criteria ("NO" branch of <NUM>), the RPD can determine that no backup plan is available to be provisioned for the destination next hop, and allow a backup path for the primary path to remain unprovisioned (<NUM>).

In some situations, there may be multiple candidate backup paths that satisfy a given priority criteria. In such cases, network device <NUM> can use various factors to select one of the backup paths that satisfy the given priority criteria. As an example, network device <NUM> may select the backup path that has a lowest index number, a backup path that was calculated first, the backup path that uses a line card or packet processor having the lowest (or highest) identifier etc..

As noted above, an administrator may configure a network device to implement link protection or node protection, and may enable or disable backup path selection using the techniques described herein. In some aspects, backup path selection using the techniques described herein is enabled by default when node protection or link protection are selected for a network device. <FIG> and <FIG> illustrate output of a command line interpreter (CLI) based user interface that displays example configuration output for different use cases of the techniques described herein.

<FIG> is a conceptual view of an example user interface output for a network device having an IS-IS LFA interface with a backup path determined according to the techniques described herein. In the example output <NUM> illustrated in <FIG>, an administrator or other user has issued a "run show isis interface detail" command. The example output <NUM> shows configuration details for a loopback interface <NUM> and two ethernet interfaces, interface <NUM> and interface <NUM>. As can be seen in the example output, ethernet interface <NUM> has been configured with link protection. Further, output portion <NUM> indicates that enhanced backup path selection techniques as described herein are enabled for ethernet interface <NUM>. In this example, the output portion <NUM> indicates that the enhanced protection is "LC level", indicating that the backup path satisfies the criteria for priority one and the backup path will only fail if the network device fails. Alternatively, an indication of "PFE level" would indicate that the backup path satisfies the criteria for priority two, and both the primary path and backup path may fail if the line card fails. As a further alternative, an indication of "enhanced protection" without a level indicator can indicate that the backup path satisfies the priority three criteria and may fail if the packet processor fails. Interfaces <NUM> and <NUM> are not configured for link protection in this example.

<FIG> is a conceptual view of an example user interface output for a network device having PIM MoFRR interface with a backup path determined according to the techniques described herein. In the example output <NUM> illustrated in <FIG>, an administrator or other user has issued a "run show pim join extensive" command. The example output <NUM> shows various configuration details for an interface using the PIM protocol. As can be seen in the example output , the interface has been configured with link protection. Further, output portion <NUM> indicates that enhanced backup path selection techniques as described herein are enabled for the interface. In this example, the output portion <NUM> indicates that the enhanced protection is "LC level", indicating that the backup path satisfies the criteria for priority one and the backup path will only fail if the network device fails.

Another use case (not shown in the figures) involves the RSVP protocol. RSVP characterizes network nodes (i.e., network devices) as ingress nodes, transit nodes, and egress nodes. In some aspects, the techniques described herein may be implemented on ingress nodes to select bypass label-switched paths (LSPs) and detour LSPs. Similarly, the techniques described herein may be implemented on transit nodes for selecting bypass LSPs.

RSVP may be used in Multi-Protocol Label Switching (MPLS). In MPLS traffic engineering, a Shared Risk Link Group (SRLG) may be defined. An SRLG is a set of links sharing a common resource, which affects all links in the set if the common resource fails. These links share the same risk of failure and are therefore considered to belong to the same SRLG. For example, links sharing a common fiber are said to be in the same SRLG because a fault with the fiber might cause all links in the group to fail.

A link might belong to multiple SRLGs. The SRLG of a path in an LSP is the set of SRLGs for all the links in the path. When computing the secondary path for an LSP, it is preferable to find a path such that the secondary and primary paths do not have any links in common in case the SRLGs for the primary and secondary paths are disjoint. This ensures that a single point of failure on a particular link does not bring down both the primary and secondary paths in the LSP.

When the SRLG is configured, the device uses the Constrained Shortest Path First (CSPF) algorithm and tries to keep the links used for the primary and secondary paths mutually exclusive. If the primary path goes down, the CSPF algorithm computes the secondary path by trying to avoid links that share any SRLG with the primary path. In addition, when computing the path for a bypass LSP, CSPF tries to avoid links that share any SRLG with the protected links. The CSPF algorithm may be modified to use the techniques described herein to compute bypass LSPs where the primary links and secondary links are mutually exclusive and that avoid links that share resources with protected links.

In some aspects, if an administrator has already determined constraints on the selection of backup paths, those constraints will take precedence of backup path selection according to the techniques described herein. For example, and administrator may have configured interface admin-group constraints, Explicit Route Object (ERO) constraints, or Shared Risk Link Group (SRLG) constraints. In such cases, these administrator created constraints may take precedence over selection of backup paths as described herein.

In some aspects, the techniques may be used to automatically determine and configure SRLGs. In current systems, an administrator typically uses manual methods to define an SRLG. The techniques described herein may be used to automatically analyze a network system for shared resources and define SRLGs accordingly.

<FIG> is a flowchart of another example method to determine backup paths according to the techniques disclosed herein. A network device may determine a primary path between the first network device and a second network device (<NUM>). Next, a network device may determine a plurality of candidate backup paths between the first network device and the second network device (<NUM>). Next, a network device may determine whether a first candidate backup path of the plurality of candidate backup paths satisfies a first priority criteria (<NUM>). If the first candidate backup path satisfies the first priority criteria ("YES" branch of <NUM>), the network device may select the first candidate backup path as a backup path for the primary path (<NUM>). If the first candidate path does not satisfy the first priority criteria ("NO" branch of <NUM>), the network device may determine whether a second candidate backup path of the plurality of candidate backup paths satisfies a first priority criteria (<NUM>). If the second candidate backup path of the plurality of candidate backup paths satisfies the second priority criteria ("YES" branch of <NUM>), the network device may select the second candidate backup path as the backup path for the primary path instead of the first candidate backup path (<NUM>). Next, a network device may program one or more packet processors with either or both the primary path and the backup path (<NUM>).

For example, various aspects of the described techniques may be implemented within one or more processors, including one or more microprocessors, digital signal processors (DSPs), application specific integrated circuits (ASICs), field programmable gate arrays (FPGAs), or any other equivalent integrated or discrete logic circuitry, as well as any combination of such components.

Rather, functionality associated with one or more modules or units may be performed by separate hardware or software components or integrated within common or separate hardware or software components.

Claim 1:
A method comprising:
determining, by processing circuitry of a first network device (<NUM>), a primary path (212A) between the first network device and a second network device (<NUM>);
determining, by the processing circuitry, a plurality of candidate backup paths between the first network device and the second network device;
determining, by the processing circuitry, whether a first candidate backup path (212D) of the plurality of candidate backup paths satisfies a first priority criteria;
in response to determining that the first candidate backup path satisfies the first priority criteria, selecting the first candidate backup path as a backup path for the primary path;
in response to determining that the first candidate backup path does not satisfy the first priority criteria, determining whether a second candidate backup path (212C) of the plurality of candidate backup paths satisfies a second priority criteria;
in response to determining that the second candidate backup path of the plurality of candidate backup paths satisfies the second priority criteria, selecting the second candidate backup path as the backup path for the primary path instead of the first candidate backup path, wherein the first priority criteria and the second priority criteria are based, at least in part, on corresponding risks of simultaneous failure of the primary path and a candidate backup path of the plurality of backup paths and wherein the second priority criteria comprise a requirement that the primary path and the candidate backup path are arranged such that they both fail when a line card (204A) shared by the primary path and the candidate backup path fails;
programming one or more packet processors of the first network device with either or both the primary path and the backup path;
receiving, by a routing protocol process of the first network device, line card identifiers, IDs, for a plurality of line cards of the first network device; and
determining, by the routing protocol process, that the primary path and the candidate backup path share the line card based on determining that a first line card ID for the line card in the primary path matches a second line card ID for the line card in the candidate backup path.