Generating non-congruent paths having minimal latency difference in a loop-free routing topology having routing arcs

In one embodiment, a method comprises creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node; identifying, within the loop-free routing topology, non-congruent paths for a source network node to reach the destination node; and determining, from the non-congruent paths, a non-congruent path pair providing no more than a prescribed difference of latency from the source network node to the destination node, enabling the source network node to forward a data packet in a first direction of the one non-congruent path pair and a bicasted copy of the data packet in a second direction of the one non-congruent path pair, for reception of the data packet and the bicasted copy by the destination node within the prescribed difference of latency.

TECHNICAL FIELD

The present disclosure generally relates to generating non-congruent paths having a minimal latency difference in a loop-free routing topology having routing arcs.

BACKGROUND

This section describes approaches that could be employed, but are not necessarily approaches that have been previously conceived or employed. Hence, unless explicitly specified otherwise, any approaches described in this section are not prior art to the claims in this application, and any approaches described in this section are not admitted to be prior art by inclusion in this section.

Bicasting is employed in industrial wireless applications where both reliability and timeliness of data traffic must be guaranteed. However, prior routing protocols are not well suited for bicasting applications, as such routing protocols assume recalculation of routes can be performed in response to a detected failure (e.g., loss of a link or a connecting network node); however, recalculation of routes requires computation time that likely results in a loss of data traffic.

Existing bicasting solutions also do not address that the different available routes can have substantially different source-to-destination transmission times that can result in a substantially large difference in latency between the available routes.

DESCRIPTION OF EXAMPLE EMBODIMENTS

Overview

In one embodiment, a method comprises creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node; identifying, within the loop-free routing topology, non-congruent paths for a source network node to reach the destination node; and determining, from the non-congruent paths, a non-congruent path pair providing no more than a prescribed difference of latency from the source network node to the destination node, enabling the source network node to forward a data packet in a first direction of the one non-congruent path pair and a bicasted copy of the data packet in a second direction of the one non-congruent path pair, for reception of the data packet and the bicasted copy by the destination node within the prescribed difference of latency.

In another embodiment, an apparatus comprises a processor circuit and a network interface circuit. The processor circuit is configured for: creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node, identifying, within the loop-free routing topology, non-congruent paths for a source network node to reach the destination node, and determining, from the non-congruent paths, a non-congruent path pair providing no more than a prescribed difference of latency from the source network node to the destination node. The network interface circuit is configured for causing the source network node to forward a data packet in a first direction of the one non-congruent path pair and a bicasted copy of the data packet in a second direction of the one non-congruent path pair, for reception of the data packet and the bicasted copy by the destination node within the prescribed difference of latency.

In another embodiment, one or more non-transitory tangible media encoded with logic for execution by a machine and when executed by the machine operable for: creating, in a computing network by the machine, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node; identifying, within the loop-free routing topology, non-congruent paths for a source network node to reach the destination node; and determining, from the non-congruent paths, a non-congruent path pair providing no more than a prescribed difference of latency from the source network node to the destination node, enabling the source network node to forward a data packet in a first direction of the one non-congruent path pair and a bicasted copy of the data packet in a second direction of the one non-congruent path pair, for reception of the data packet and the bicasted copy by the destination node within the prescribed difference of latency.

DETAILED DESCRIPTION

U.S. Pat. No. 9,112,788 to Thubert et al. and assigned to Cisco Technology, Inc., describes creating a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network device, where the loop-free routing topology comprises first and second non-congruent paths for reaching the destination network device. Bicasting data can be forwarded toward the destination network device based on a source network device forwarding a data packet in a first direction via a first non-congruent path, and the source network device forwarding a bicasted copy in a second network direction via a second non-congruent path.

Particular embodiments enable the generation of non-congruent paths, within the loop-free routing topology as described in U.S. Pat. No. 9,112,788, where the non-congruent paths have a minimal latency difference that is less than a prescribed Delta of Latency (i.e., Difference of Latency) (DoL). The generation of non-congruent paths having a minimal DoL that is less than the prescribed DoL enables the destination network device (e.g., a router device) to enjoy reliable transmission of data traffic that is bicasted via the non-congruent paths, without the necessity of larger data buffers in the network device.

As described in further detail below with respect toFIGS. 19-20, the example embodiments enable identifying, from among multiple available paths in distinct first and second directions in the loop-free routing topology, one path from the first direction and a one path from the second direction that provide no more than the prescribed DoL, enabling the source network node to forward the bicasted traffic via the non-congruent path pair to the destination network device within the prescribed DoL. Hence, the destination network device can reliably process jitter-sensitive bicasted traffic based on instantaneously switching between either non-congruent path in the non-congruent path pair, with minimal buffer sizes.

The following description will begin with describing creation of a plurality of routing arcs (omega arcs), followed by a description of establishment of omega label switched paths for reaching a destination network node. The description of the omega arcs and the omega label switched paths are described with respect toFIGS. 1 through 15. The omega label switched paths enable fast rerouting to be implemented within the loop-free routing topology. The description of establishing the non-congruent paths will be described with respect toFIGS. 16 through 18. The description of generating non-congruent paths having minimal DoL will be described with respect toFIGS. 19-20.

Generating the Loop-Free Topology Using Routing Arcs

The particular embodiments apply the use of routing arcs to create at least two non-congruent paths within the loop-free routing topology: the term “non-congruent” is defined as any network path (between a source node and a destination node) that does not share any part of its path (including any intermediate network nodes or connecting data links) with any other network path. Hence, two network paths are non-congruent if they do not share any data link or any intermediate network node between the source node and the destination node. The use of non-congruent paths guarantees that any traffic that is bicasted concurrently along the non-congruent paths from the source node will reach the destination node, even if there is a failure in one of the non-congruent paths.

The non-congruent paths also can be used for multicasting, where a multicast registration bicasted by a multicast consumer is marked (i.e., recorded) by each intermediate network node and forwarded along the non-congruent paths. The destination network node (i.e., the multicast registration destination) can utilize the non-congruent paths for transmission of multicast streams via the non-congruent paths. Collision mediation also is employed to ensure multiple multicast subscribers do not create overlapping multicast streams.

FIGS. 1 through 6Idescribe the generation of routing arcs in loop-free topology using routing arcs, according to an example embodiment. Routing arcs can be generated in a loop-free routing topology that can guarantee that any network node having at least two data links can reach the destination network node via at least one of the routing arcs: the network traffic can be instantaneously rerouted toward another end of a routing arc in response to detected data link failure (or network node failure), based on reversing an identified reversible link within the routing arc. The reversal of the identified reversible link within the routing arc also is guaranteed to not introduce any loops into the loop-free routing topology.

In one embodiment, the loop-free routing topology is represented by generating a set of serialized representations describing the loop-free routing topology. In particular, each serialized representation describes one of the paths (e.g., routing arcs), in the loop-free routing topology; for example a serialized representation of a given path or routing arc can resemble a source route path from one end of the path (e.g., a first junction node of a routing arc) to another end of the path (e.g., a second junction node of a routing arc). Hence, the set of the serialized representations provides a complete representation of all the paths in the loop-free routing topology.

Moreover, any network node receiving the set of serialized representations can establish multiple paths for reaching the destination network node, for example in the form of loop-free label switched paths for reaching the destination network node. Hence, the propagation of the serialized representations throughout the network nodes in the computing network enables the automatic deployment of label switched paths by the network nodes.

In particular, the following description with respect toFIGS. 1 through 6Idescribe an apparatus creating, in a computing network, a loop-free routing topology comprising a plurality of routing arcs for reaching a destination network node: each routing arc comprises a first network node as a first end of the routing arc, a second network node as a second end of the routing arc, and at least a third network node configured for routing any network traffic along the routing arc toward the destination network node via any one of the first or second ends of the routing arc.

A junction node is defined as a network node (e.g., a computing network having a prescribed network topology, for example a prescribed ring topology) identified based on its relative position within a network topology) that has at least two data links providing respective non-congruent paths for reaching the destination network node: the term “non-congruent” in this specification and the attached claims requires that the paths from a junction node do not share any common data link for reaching the destination network node, rather each link belonging to one path (from the junction node to the destination network node) is distinct and independent of any link belonging to the second non-congruent path (from the junction node to the destination network node).

A data link of a junction node also can be deemed a “reversible link” if the data link enables an endpoint of the data link (i.e., a network node that is directly coupled to the junction node via the data link) to become a junction node having its own non-congruent paths for reaching the destination network node.

In one embodiment, one or more junction nodes coupled by a reversible link can be logically connected in sequence to create a routing arc as a first infrastructure arc having its two corresponding ends terminating at the destination network node. Additional routing arcs can be created that have at least one end terminating in a previously-created infrastructure arc (e.g., the first infrastructure arc), and the other end terminating in either a previously-created infrastructure arc or the destination network node, where each new routing arc includes network nodes that are distinct from any of the network nodes in previously-generated routing arcs. In other words, a network node assigned to one existing routing arc cannot later be assigned to another routing arc (except if the network node is a junction between the existing routing arc and an end of the newer routing arc).

In another embodiment, a routing arc can be created as an infrastructure arc based on identifying, within a first directed acyclic graph for reaching the destination network node, one or more junction nodes having reversible links for reaching the destination network node via non-congruent paths; a second routing arc can be created based on identifying, within the first directed acyclic graph, a second directed acyclic graph for reaching one of the junction nodes (as one end of the second routing arc) of the first directed acyclic graph, and identifying within the second directed acyclic graph a new junction node having a new non-congruent path for reaching the destination network node that is distinct from the one junction node, the new junction node providing the new non-congruent path via the second end of the second routing arc that terminates either at the destination network node or a previously-created infrastructure routing arc.

Hence, example embodiments enable any network node having two data links in the loop-free routing topology to be guaranteed reachability to the destination network node, even if any one data link in the loop-free routing topology encounters a failure, based on reversing an identified reversible link.

FIG. 1illustrates an example loop-free routing topology10comprising a plurality of routing arcs12for reaching a destination network node14, according to an example embodiment. Each routing arc12comprises a plurality of network nodes16each having at least two data links for reaching adjacent network nodes. As apparent fromFIG. 1, the loop-free routing topology10guarantees that any network node16along any point of any arc12(illustrated by “X” inFIG. 1) has at least two non-congruent paths for reaching the destination network node14, guaranteeing reachability to the destination network node14even if a link failure is encountered in the loop-free routing topology10. The term “node” in the specification and claims can refer to a network device or a network having a prescribed topology, for example a ring-based network having a prescribed ring topology.

As described in further detail below with respect toFIGS. 6A-6I, each routing arc (e.g., “ARC1” ofFIG. 6I)12comprises at least three network nodes16, namely a first network node (e.g., network node “K” ofFIG. 6I)16designated as a first end of the routing arc, a second network node (e.g., network node “J” ofFIG. 6I)16designated as a second end of the routing arc, and at least a third network node (e.g., network node “M” ofFIG. 6I)16identified as a junction node and configured for routing any network traffic along the routing arc toward the destination network node14via any one of two available non-congruent paths provided by the first or second ends of the routing arc. Hence, network traffic can be forwarded along at least one of the routing arcs12to the destination network node14.

As illustrated inFIG. 6I, the first and second ends of each routing arc12each terminate at a “safe network node”, for example either the destination network node14, another network node directly coupled to the destination network node (e.g., network node “A” or network node “B”), or a junction node of another routing arc. A network node (e.g., “A” ofFIG. 6I) directly coupled to the destination network node “R”14is referred to as an “heir network node”. Hence, a “safe network node” can be any one of the destination network node14, an heir network node (e.g., “A” or “B” ofFIG. 6I), or a junction node having two non-congruent paths for reaching the destination network node. For example, both ends of the routing arc “ARC2”12terminate at the destination network node “R”14, also referred to as the “root network node” or “root node”; a first end of the routing arc “ARC3”12terminates at the heir network node “A”16, and a second end of the routing arc “ARC3”12terminates at the junction node “C” of the routing arc “ARC2”12. The routing arc “ARC2”12also can be referred to as the “root arc”, since both ends of the routing arc “ARC2”12terminate at the destination network node “R”14

In an example embodiment illustrated inFIG. 5andFIG. 6I, each routing arc comprises one and only one arc cursor (18ofFIG. 6I) that provides exclusive control of directing the network traffic along the routing arc. One and only one junction node of the routing arc (i.e., one and only one network node assigned a position within the routing arc as a junction node) has possession of the arc cursor18at any given time: the junction node having possession of the arc cursor18can control the network traffic along the corresponding routing arc12based on possession of the arc cursor18. In particular, the junction node (e.g., “J” ofFIG. 6I) having possession of the arc cursor18can direct network traffic away from itself along either of its outwardly-oriented links toward the ends of the routing arc (e.g., “ARC2”)12. Hence, a junction node having possession of the arc cursor18(also referred to as an “arc cursor node”) has exclusive control over routing the network traffic along the corresponding routing arc, based on the junction node routing the network traffic away from itself along one of its outwardly-oriented links.

A second junction node (i.e., another network node a position within the routing arc as a junction node) can gain possession of the arc cursor (e.g., from the first junction node of the routing arc) based on a detected failure in the corresponding routing arc, for continued routing of the network traffic in the corresponding routing arc despite the detected failure. For example, the junction node “F” of the routing arc “ARC2”12can gain possession of the corresponding arc cursor18that was previously owned by the junction node “J”, based on a detected failure in the link “F-C” between network nodes “F” and network node “C”, enabling the network node “F” to reverse the link “F-J” toward the node “J” for continued reachability toward the destination network node “R”14(seeFIGS. 6H and 6I). Hence, the second junction node (e.g., “F” ofFIGS. 6H and 6I), upon gaining possession of the arc cursor18that provides exclusive control of directing the network traffic along the routing arc (e.g., “ARC2”)12, can reverse one of the connected reversible links without creating a loop in the loop-free routing topology10. Hence, data traffic along a routing arc (e.g., “ARC2”)12can be instantaneously rerouted for continued routing in the routing arc12toward the destination network node14in response to a detected failure in the routing arc (e.g., failure in link “F-C”), based on a junction node (e.g., “F”) in the routing arc gaining possession of the routing arc18previously owned by another junction node (e.g., “J”) in the same routing arc12.

FIGS. 2 and 6Aillustrate an example apparatus20for creating the loop-free routing topology10ofFIGS. 1, 6I, and 16-25, according to an example embodiment. The apparatus (i.e., device, machine) can be implemented as a router, a centralized server, a network management entity, etc. that executes the disclosed operations for creating the loop-free routing topology10, and distributing relevant routing arc parameters to each of the network nodes implementing the loop-free routing topology10as network nodes16within the topology10. The apparatus20is a physical machine (i.e., a hardware device) configured for implementing network communications with other physical machines14,16via data links establishing a link layer mesh topology network44(seeFIG. 2).

As illustrated inFIG. 2, the apparatus20includes a processor circuit22, a device interface circuit24, and a memory circuit26. The processor circuit22is configured for creating, for a computing network, the loop-free routing topology10comprising the routing arcs12for reaching the destination network node14. The memory circuit26is configured for storing parameters associated with the routing arcs12in a state table54and/or a topology table56, described in further detail below with respect toFIGS. 4 and 5. The device interface circuit24is configured for outputting at least selected parameters associated with the routing arcs12to a second apparatus, for deployment of the loop-free routing topology10: the second apparatus can be a network management entity for configuring the network nodes16, or at least one of the network nodes16that can be configured directly by the apparatus20. Hence, the output by the device interface circuit24of the selected parameters for deployment of the loop-free routing topology10causing the network traffic in the computing network to be forwarded along at least one of the routing arcs to the destination network node.

Any of the disclosed circuits of the apparatus20(including the processor circuit22, the device interface circuit24, the memory circuit26, and their associated components) can be implemented in multiple forms. Example implementations of the disclosed circuits include hardware logic that is implemented in a logic array such as a programmable logic array (PLA), a field programmable gate array (FPGA), or by mask programming of integrated circuits such as an application-specific integrated circuit (ASIC). Any of these circuits also can be implemented using a software-based executable resource that is executed by a corresponding internal processor circuit such as a microprocessor circuit (not shown) and implemented using one or more integrated circuits, where execution of executable code stored in an internal memory circuit (e.g., within the memory circuit26) causes the integrated circuit(s) implementing the processor circuit22to store application state variables in processor memory, creating an executable application resource (e.g., an application instance) that performs the operations of the circuit as described herein. Hence, use of the term “circuit” in this specification refers to both a hardware-based circuit implemented using one or more integrated circuits and that includes logic for performing the described operations, or a software-based circuit that includes a processor circuit (implemented using one or more integrated circuits), the processor circuit including a reserved portion of processor memory for storage of application state data and application variables that are modified by execution of the executable code by a processor circuit. The memory circuit26can be implemented, for example, using a non-volatile memory such as a programmable read only memory (PROM) or an EPROM, and/or a volatile memory such as a DRAM, etc.

Further, any reference to “outputting a message” or “outputting a packet” (or the like) can be implemented based on creating the message/packet in the form of a data structure and storing that data structure in a tangible memory medium in the disclosed apparatus (e.g., in a transmit buffer). Any reference to “outputting a message” or “outputting a packet” (or the like) also can include electrically transmitting (e.g., via wired electric current or wireless electric field, as appropriate) the message/packet stored in the tangible memory medium to another network node via a communications medium (e.g., a wired or wireless link, as appropriate) (optical transmission also can be used, as appropriate). Similarly, any reference to “receiving a message” or “receiving a packet” (or the like) can be implemented based on the disclosed apparatus detecting the electrical (or optical) transmission of the message/packet on the communications medium, and storing the detected transmission as a data structure in a tangible memory medium in the disclosed apparatus (e.g., in a receive buffer). Also note that the memory circuit23can be implemented dynamically by the processor circuit22, for example based on memory address assignment and partitioning executed by the processor circuit22.

The following definitions are provided prior to a description of the methods for creating the routing arcs.

A routing arc is defined as a double ended reversible path. A reversible arc is defined as a routing arc containing one or more reversible links, and the reversible arc can contain one or more non-reversible links at each end of the arc. Data links that are labeled “Rev” inFIGS. 6B through 6Hare reversible links, and links that are not labeled “Rev” inFIGS. 6B through 6Hare not reversible; hence, the end of a routing arc can be identified based on one or more successive non-reversible links, with one or more reversible links internal to the non-reversible links. A collapsed arc (e.g., “ARC1”, “ARC3”, “ARC6”, “ARC7”, and “ARC8” ofFIG. 6I) is defined as a routing arc12having no reversible link and consisting of a one network node that has fixed (i.e., non-transferable) possession of the arc cursor18, and two other network nodes16nodes serving as respective ends of the collapsed arc. For example, the collapsed arc “ARC1”12is illustrated inFIG. 5andFIG. 6Ias consisting of the network nodes “J”, “M”, and “K”, where the network node “M” has fixed possession of the arc cursor18between the network nodes “J” and “K” at the respective ends of the collapsed arc “ARC1”12.

A link designated with an arrow at one end and having a designation of “SPF” represents a link as found in a tree generated according to a conventional routing protocol such as Open Shortest Path First (OSPF), such that the network node at the end of the arrow represents a shortest path first (SPF) successor of the network node at the tail end of the arrow (e.g., network node “A” inFIG. 6Ais the SPF successor to network nodes “C” and “D”). Any link at the edge of the arc (i.e., that terminates the arc and connects the arc either to a second arc or to the destination) will be designated using the arrow at one end. A link designated with “TOP” (representing “then other path”) represents a link that has not been chosen by OSPF because it is not the shortest path successor, but that can be used as an alternate next hop (i.e., a feasible successor), for example for generating a directed acyclic graph (DAG) (see, e.g., U.S. Pat. No. 7,656,857).

As described previously, the network node having possession of the arc cursor can decide in which direction along the arc network traffic should be forwarded. Hence, a network node is determined to be a “safe network node” if the “safe network node” can forward network traffic in either direction along the arc (i.e., the “safe network node” can safely forward any packet in one direction along the arc even if the other direction fails).

A link designated with the reference “?-S” represents a candidate link that is unresolved for a junction node “S” that is identified as the nearest safe network node for the network node via the link having the designation “?-S”: reference to a candidate link denotes a transient state when the two ends of a routing arc have not yet been established, and it is not yet established whether the candidate link is to be used in the formation of a routing arc. As described in further detail below with respect toFIGS. 6B-6F, the links designated with the reference “?-S” also identify a subDAG (i.e., a DAG within a DAG) for reaching the safe node “S”.

A link designated with the reference “Rev” indicates a reversible link connecting two network nodes that are within a routing arc12: as illustrated inFIGS. 6H and 6I, a network node (e.g., “J”) having at least one reversible link is within the middle of the arc, and can have possession of the arc cursor18for the corresponding routing arc. As illustrated inFIGS. 6H and 6I, data links at the edge of a routing arc (e.g., that terminates at a first arc and enters into a second arc, or that terminates at the destination node D) are directed away from the middle of the routing arc (and the junction node having possession of the corresponding arc cursor18)12, and the data links at the edge of a routing arc12are not reversible.

A link designated with a square-shaped or diamond-shaped block at one end (e.g., “M→J” inFIG. 6C) indicates a blocked link that is not reversible, where the destination network node (e.g., network node “J” inFIG. 6C) cannot send any data traffic to the other sourcing network node (e.g., “M” ofFIG. 6C), but the sourcing network node (e.g., “M” ofFIG. 6C) can send data traffic to the destination network node (“J”) via the link (“M→J”). Blocked links are used during computation to prevent any formation of loops.

As described in further detail below, data links are oriented away from the junction node having possession of the arc cursor toward the edges of the routing arc12, and link orientation of a reversible link can be changed by moving the arc cursor18(i.e., passing ownership of the cursor from one network node to another network node).

Routing arcs12are built between network nodes identified as junction nodes. A junction node68is a network node connected to two or more safe network nodes (described below) over non-congruent paths (i.e., no single point of failure can stop reachability from the junction node to the root node). An edge junction is defined as a junction node68terminating one and only one reversible link, where the edge junction can have multiple nonreversible links oriented both inwards and/or outwards. An intermediate junction is defined as a junction node68that terminates two and only two reversible links, where all other links coupled to the intermediate junction are oriented inwards to avoid loops: a link can be safely reversed towards an intermediate junction. Hence, an intermediate junction consists of two reversible links and zero or more inward oriented links from any other network node. A collapsed arc does not have any intermediate junction, and an edge junction can belong to one or more collapsed arcs.

A root network node14is defined as a single network node in a network (i.e., a “destination network node”) that must be accessed to reach a resource, i.e., there never can be a second path that can bypass the root network node to reach the resource. Calculation of routing arcs12begins with identification of a root node (i.e., the destination node)14for a given routing topology10. Examples of a root node14can include a head end of an autonomous directed acyclic graph within the routing arcs12, a gateway to another network, or any identifiable destination. All of the root links always are oriented inwards toward the root node14and resolved.

An “heir” network node is a network node that is directly connected to a root network node14. As illustrated inFIGS. 1 and 6A-6I, a destination network node serving as a root network node14must have at least two heir network nodes (e.g. network nodes “A” and “B” ofFIGS. 6A-6I) that are directly connected to a root network node14: if a root network node has only one heir node, then the heir network node is designated as the new root node (based on the definition of a root network node as having no second path to reach a resource). The heir network node is used to identify a safe network node: if a network node can reach the root node alternatively via either a first heir network node or a second heir network node, then the network node is considered a safe network node because it can route a packet to the root via two non-congruent paths, namely either via the first heir network node or via the second heir network node, guaranteeing that reachability if one of the links toward the root node is broken.

A leaf network node is a node that has one and only one data link: a leaf node cannot be a junction node and cannot belong to a routing arc12. The data link coupled to the leaf network node is always oriented outwards (i.e., away from the leaf network node) and resolved.

A safe network node is a designation used to identify any one of a root network node14, an heir node (e.g., “A” or “B” ofFIGS. 6A-6I), or a junction node. Hence, a junction node is a network node that is neither a root network node14nor an heir network node, but that is a safe network node because it has two or more non-congruent paths to the root network node such that no single point of failure can cut off the junction node from the root network node. A network node can be identified as a junction node if the direction of a reversible link must be turned to obtain the alternate path.

Hence, a network node connected to an heir network node and the root network node is a junction node; a network node connected to two different heir network nodes is a junction node; a network node connected to an heir network node and a junction node also is a junction node; a network node connected to two different junction nodes also is a junction node. Since the root network node, the heir network node, and the junction node each are defined as safe network nodes, then a network node connected to two different safe network nodes is a junction node; a network node that has non-congruent paths to at least two different safe network nodes is a junction node (the junction node can be considered to “see” to safe network nodes, and then hide them so long as they are only reachable from via that junction node); a network node that can only see one junction node is within the “subDAG” that junction node and can be tracked as such.

Hence, a data packet must follow along a routing arc12, and can exit a routing arc12only via an edge junction at one of the ends of the routing arc12. Consequently, a data packet can reach the root node (i.e., the destination node)14based on traveling along one or more routing arcs12.

FIG. 3Ais a diagram illustrating an example method by the apparatus20ofFIG. 2that includes creating a loop-free routing topology10comprising routing arcs12for reaching a destination network node14, according to an example embodiment.FIGS. 3B, 3C and 3Dillustrate an alternate method by the apparatus20for creating the loop-free routing topology10, according to another example embodiment.

The operations described with respect to any of the Figures can be implemented as executable code stored on a computer or machine readable non-transitory tangible storage medium (i.e., one or more physical storage media such as a floppy disk, hard disk, ROM, EEPROM, nonvolatile RAM, CD-ROM, etc.) that are completed based on execution of the code by a processor circuit implemented using one or more integrated circuits; the operations described herein also can be implemented as executable logic that is encoded in one or more non-transitory tangible media for execution (e.g., programmable logic arrays or devices, field programmable gate arrays, programmable array logic, application specific integrated circuits, etc.). Hence, one or more non-transitory tangible media can be encoded with logic for execution by a machine, and when executed by the machine operable for the operations described herein.

In addition, the operations described with respect to any of the Figures can be performed in any suitable order, or at least some of the operations in parallel. Execution of the operations as described herein is by way of illustration only; as such, the operations do not necessarily need to be executed by the machine-based hardware components as described herein; to the contrary, other machine-based hardware components can be used to execute the disclosed operations in any appropriate order, or at least some of the operations in parallel.

Referring toFIG. 3A, the processor circuit22can create the loop-free routing topology10based on creating in operation30the first routing arc12as an infrastructure arc (i.e., a routing arc that is not a collapsed arc): the first routing arc12(e.g.,12aor12bofFIG. 1) created in operation30must have both ends terminating at the destination network node (i.e., the root node)14. The processor circuit22can create in operation32the next routing arc12(after the first routing arc12aor12bcreated in operation30) as an infrastructure arc (e.g.,12cafter12b) or a collapsed arc (e.g.,12dafter12a), subject to the following rules: (1) the next routing arc12under construction must terminate either in the junction node of an existing routing arc or at the destination network node14(e.g., routing arc12cterminates one end at the routing arc12band terminates the other end at the destination network node14); and (2) except for an end of a routing arc terminating in the junction node of an existing routing arc, the routing arc under creation must be made from network nodes that are not already in an existing routing arc; in other words, in rule (2) the next routing arc12includes network nodes that are distinct from any of the network nodes of the existing routing arcs. The next routing arc12can be constructed by the processor circuit22in operation34, until all the routing arcs have been completed for all network nodes having at least two data links. The processor circuit22identifies in operation36any leaf network nodes consisting of only one data link, and implements in operation38the loop-free routing topology10constructed in operations30,32,34, and36.

As illustrated operations30,32, and34, the first routing arc12(e.g.,12aor12b) preferably is created prior to any other routing arc12(e.g.,12cor12d); however, the routing arcs12inFIG. 1can be created in any arbitrary order, so long as the rules of operation32are followed to guarantee no loop formation, where the “existing routing arc” refers to a set of network nodes that already are allocated for another routing arc. Hence, alternative techniques for creating the loop-free routing topology10can be utilized, so long as: the routing arcs12do not intersect across each other during formation; or any routing arcs12that intersect across each other share the same cursor at the intersection point (e.g., a collapsed arc), causing all network traffic to be directed away from the cursor point.

The processor circuit22can deploy in operation38the loop-free routing topology10based on causing the device interface circuit24to output at least selected parameters associated with the routing arcs12to at least one other apparatus (e.g., a network router, a network management apparatus, one or more network nodes, etc.), causing the network traffic in the routing topology10to be forwarded along at least one of the routing arcs12to the destination network node14. If in operation40a link failure is detected (or a network node failure) in one of the routing arcs, for example by either the apparatus20or by one of the network nodes14or16, the possession of the arc cursor18can be gained (e.g., by transfer, reassignment, etc. by the processor circuit22) by the junction node adjacent to the link failure in operation42, enabling the junction node to control the network traffic based on reversing one of the reversible links for continued routing toward the destination network node14without creating a loop in the loop-free routing topology10.

FIGS. 3B, 3C and 3Dillustrate an example method by the processor circuit22for creating the loop-free routing topology10comprising the routing arcs12ofFIG. 6I, according to an example embodiment.

According to an example embodiment, a loop-free routing topology10can be created in which an attempt is made to establish every network node, except the root network node and the heir network nodes, as junction nodes, in order to guarantee that every network node has a shortest path and an alternate path to a destination network node (i.e., the root network node)14. This guarantee is established by creating routing arcs12that terminate at safe network nodes. Since conventional techniques for generating a directed acyclic graph (DAG) does not guarantee that every node within a directed acyclic graph can be a junction, the example embodiments enable a link to be reversed in response to a detected failure in a network node or network link, enabling immediate rerouting of data traffic without route recalculation and without the formation of any loop in the topology. Hence, the example embodiment can establish a loop-free routing topology of routing arcs for reaching a root network node, the loop-free routing topology consisting of a root network node, two or more heir network nodes coupled to the root network node, junction nodes, and zero or more leaf network nodes.

As described in further detail with respect toFIGS. 3B, 3C, 4-5 and 6A-6I, the loop-free routing topology10is created based on: generating a first directed acyclic graph for reaching the destination network node14; identifying (within the first directed acyclic graph) junction nodes that have non-congruent paths for reaching the destination network node14; identifying reversible links between the junction nodes, along the non-congruent paths, and that do not introduce or create a loop in the loop-free routing topology10; and identifying at least one second directed acyclic graph within the first directed acyclic graph (also referred to as a “subDAG”) for reaching one of the junction nodes, the second directed acyclic graph including an identified new junction node having a new non-congruent path for reaching the destination network node.

In this disclosure, links can be identified by the connecting network nodes, such that the link “A-R” refers to a wired or wireless link that connects the network node “A” to the next hop network node “R”: an arrow in a link designation can refer to an assigned direction (e.g., “A→R” and “R←A” equivalently identify a link directing traffic from node A to node R), whereas the absence of an arrow in a link designation (e.g., “A-R”) indicates that a direction has not yet been assigned to the link.

Referring toFIGS. 2 and 3B, the processor circuit22identifies the data link layer topology44(FIG. 2) composed of wired or wireless data links (e.g., wired or wireless IEEE 802.11, Bluetooth, etc.)46, and creates in operation50a directed acyclic graph (DAG)52for reaching the destination network node14, illustrated inFIG. 6A. In particular, the link layer topology44ofFIG. 2includes network nodes14having one or more link layer connections (e.g., wired or wireless IEEE 802 links, Bluetooth links, etc.) interconnecting the network nodes, for example in the form of a link layer (i.e., OSI Layer 2) mesh of interconnected network nodes. The directed acyclic graph52is generated in operation50by the processor circuit22, for example according to the techniques described in U.S. Pat. No. 7,656,857, where the links labeled “SPF” identify the Shortest Path First (SPF) links in the SPF topology, and the links labeled “TOP” identify the “then other path” (TOP) links overlying the SPF topology that result in the formation of the directed acyclic graph (DAG) toward the root node “R”. In summary, the directed acyclic graph is formed by the processor circuit22in operation50based on identifying next hop nodes adjacent to the root node14, and orienting the link of each next hop node toward the root. Secondary adjacent nodes (adjacent to each of the next hop nodes) are then identified, and the paths from the next hop nodes to the associated secondary adjacent nodes are extended while orienting each of the links between the secondary adjacent nodes and the next hop nodes toward the next hop nodes. These operations are repeated recursively until the paths extend to the furthest nodes in the network, and orienting the links back toward the root, for formation of the directed acyclic graph.

The SPF status of the SPF links are retained in the memory circuit26during calculation of the routing arcs12with respect toFIGS. 6A-6I.FIG. 4(consisting ofFIGS. 4A, 4B, 4C and 4D) illustrate an example state table54that can be stored in the memory circuit26and configured for storing state changes in the network nodes and the data links during execution of the method inFIGS. 3B, 3C and 3D.

FIG. 5illustrates an example topology table56that can be stored in the memory circuit26and configured for storing arc topology attributes as the routing arcs are constructed for reaching the destination network node (i.e., root network node “R”)14. The processor circuit22can update the topology table56ofFIG. 5as the state table54is updated (e.g., upon identification of SPF links, identification of reversible links, identification of junction nodes68, upon creating a routing arc, etc.), where the ownership of an arc cursor18is identified by the junction node68having the two outwardly oriented reversible links. Hence, the processor circuit20stores in operation50the SPF links58in the topology table56, and the non-SPF links (not shown inFIG. 5).

As illustrated inFIG. 6A, none of the network nodes in the DAG topology52(except the network node “J”) has at least two non-congruent paths for reaching the root node “R”. Hence, the method ofFIGS. 3B, 3C and 3Dprovides the creation of the routing arcs12in a loop-free routing topology10, the routing arcs enabling network traffic to be routed along the routing arcs toward the destination root network node via any one of the ends of the routing arcs.

After formation of the directed acyclic graph in operation50, the generation of the routing arcs begins in operation60ofFIG. 3B, where the SPF links are retained, while selectively modifying non-SPF links in the directed acyclic graph as either unidirectional links or reversible links. The status of each network node and each data link can be stored in a memory circuit.

The generation of the routing arcs in operation60begins with identification of the root network node R and orienting unoriented links toward the root (A→R, B→R) as illustrated by the state change in the state table ofFIG. 4Aat event200, and initiating identification of the heir network nodes (e.g., node A) in operation62. As described in further detail below, the SPF nodes are successively analyzed by the processor circuit22in operation62for identification of subordinate directed acyclic graphs (subDAGs)64(e.g.,64aand64bofFIG. 6B) within the DAG52toward the destination network node14. Each heir network node link (e.g., A-R) that is coupled to the root network node14is oriented outward toward the root network node and marked in the state table54as resolved (A→R=Resolved) (event202ofFIG. 4A). Each neighbor network node is successively resolved in operation66to identify any junction node within a subDAG64that has an alternate non-congruent path for reaching the destination network node14via a path that is distinct from the subDAG64; in other words, each neighbor network node16is successively resolved to identify, within a subDAG64, any junction nodes having at least two non-congruent paths for reaching the destination network node.

FIGS. 3C and 3Dillustrate in further detail the operations executed by the processor circuit22in operation66. The operations ofFIGS. 3C and 3Dare illustrated in the example form of “C code” for a function call entitled “resolve_neighbor(N)”, annotated with outline annotations to identify nested operations. The apparatus20is omitted inFIGS. 6B through 6IandFIG. 7to simplify the illustrations, although it will be apparent that the apparatus20will be consistently present during calculation of the routing arcs12and creation of the loop-free routing topology10(and load balancing of the loop-free routing topology10as described below with respect toFIGS. 7-9).

The first operation in operation70is executed by the processor circuit22if the neighbor node “N” under analysis is a leaf network node consisting of one and only one data link. In this example, the current state of execution is state202ofFIG. 4A, where the heir network node “A” is under analysis; hence, operation70is skipped because the heir network node A is not a leaf node. Operation72is executed by the processor circuit22if the neighbor node “N” under analysis is not a safe node. In this current state of analyzing the heir network node “A”, operation72is skipped because the heir network node A is a safe network node (because it is an heir network node).

As described previously, the method executed by the processor circuit22attempts to identify adjacent network nodes that are safe network nodes. Hence, any of the links (N-i) in the safe network node under analysis (e.g., Node N=Node A) that have not yet been labeled (i.e., are unlabeled) (e.g., D→A, C→A), are set initially to an unresolved status toward the nearest safe node (D→A=“?-S”; C→A=“?-S”) to indicate that it has not yet been determined whether the links (e.g., D→A, C→A) couple the network node (e.g., node A) to another safe network node that enables the link to be reversible, or whether the links couple the network node to an unsafe network node (i.e., a network node that is not a safe network node as previously defined).

Each of the links (N-i) of the safe network node under analysis (e.g., node N=node A) are resolved in operation74in order according to SPF identification, namely links providing shortest path first, followed by outgoing links, followed by incoming links. If in operation76a data link is already resolved, the execution by the processor circuit22proceeds to the next link in operation74: note that the link A→R is resolved and ends in the root network node14, identifying the link A→R as terminating a routing arc12. Operations78through86are currently skipped by the processor circuit22because the safe network node under analysis (e.g., node N=node A) has no other unresolved outgoing links. The processor circuit22returns to the next link in operation74, namely the incoming links.

If in operation88the processor circuit22determines the unresolved link under analysis (which is not an SPF link or an outgoing link) has no assigned direction, the link is assigned an incoming direction to direct traffic toward the safe network node under analysis (e.g., Node N=Node A). If the incoming link (e.g., D→A based on the initial directed acyclic graph) is marked to an unresolved status (e.g., D→A=“?-S”), the incoming link is marked to an unresolved status with respect to the safe network node under analysis (i.e., the link D→A is reset from “?-S” to “?-N”). Hence, the link “D→A” is reset to the status “?-A” (Node N=Node A: D→A=“?-A”); the process is repeated in operations74and88by the processor circuit22for the next link of node A, hence the link “C→A” is reset in operation88to the status “?-A” (C→A=“?-A”), indicating that it has not yet been determined whether the links “D→A” and “C→A” are reversible to reach another safe network node (the links are oriented toward the nearest safe network node). Hence, the unresolved status indicates that a routing arc cannot be formed yet because the unresolved link has not been found to be reversible toward an alternate non-congruent path to the root network node. All the unresolved incoming links in the subDAG toward the safe network node “N” (Node N=Node A) are recursively relabeled in operation88, resulting in the identification of subDAG(A)64aofFIG. 6Bvia the links labeled “?-A”.

After all the links for the safe network node under analysis (e.g., Node N=Node A) have been analyzed, the process of operations62and66ofFIG. 3Bare repeated by the processor circuit22for the next node having the shortest path (in the SPF computation of operation50) to the root network node “R” that has not yet been analyzed (e.g., heir network node “B”) (event204ofFIG. 4A). The network node “B” is identified by the processor circuit22as an heir network node in operation62, and the root link “B→R” is identified by the processor circuit22as an SPF link and oriented toward the root network node, and marked in the state table54and the topology table56as a resolved SPF link in operation62. As illustrated by the execution by the processor circuit22of operation66inFIGS. 3C and 3D, since network node “B” is identified as an heir network node (and therefore a safe network node) having an additional incoming link “K-B”, operations70and72are skipped by the processor circuit22, and the processor circuit22changes the status of the link “K→B” in operation88in the state table54from “?-S” to “?-B” (K→B=“?-B”). The remaining incoming links are recursively resolved toward the nearest safe node “B”, resulting in the subDAG(B)64bofFIG. 6B.

Processing continues by the processor circuit22in operation62ofFIG. 3Bto the next node identified by the SPF computation as closest to the root network node “R” that has not yet been analyzed, namely the network node “K” (event206ofFIG. 4A). Operation70ofFIG. 3Cis skipped because the network node “K” is not a leaf node. Hence, the network node “K” is not a safe network node because it does not yet have two non-congruent paths to the root network node “R”, rather the network node “K” currently has only the SPF link “K→B” to the safe network node “B”. Hence, all the non-SPF links (e.g., M-K and J-K) are assigned by the processor circuit22to be oriented incoming to the current network node “K” under analysis, and the links are labeled by the processor circuit22in operation72as unresolved to the nearest safe network node (e.g., M→K=“?-B”; J→K=“?-B”).

Hence, the current set of analyzed network nodes include the network nodes “A”, “R”, “B”, and “K”.

The method continues by the processor circuit22in operation62ofFIG. 3B and 104with the next SPF network node, identified as a network node “M” which is not a safe network node (event208ofFIG. 4A). Operation70skipped by the processor circuit22, the node “M→K” is identified as the SPF link, and in operation72the link “J-M” is assigned in the state table54in operation72as an incoming link having an unresolved status to the nearest safe network node “B” (J→M=“?-B”).

The next network node chosen by the processor circuit22in operation62ofFIG. 3Bfrom the SPF nodes is the network node “D” (event210), the link “D→A” is identified as the SPF link, operation70is skipped by the processor circuit22, and since the network node “D” is not a safe network node, the remaining non-SPF links are assigned by the processor circuit22as incoming to the network node “D” in operation72, and labeled in the state table54as unresolved to the nearest safe network node “A” (C→D=“?-A”; E→D=“?-A”; L→D=“?-A”). As described in further detail below, the cost of each of the non-SPF links for each of the network nodes can be tracked for later analysis. The method is repeated by the processor circuit22for the network node “C” (event212), resulting in the link “C→A” identified as the SPF link and the labeling of the links E→C=“?-A” and F→C=“?-A” in the state table54in operation72.

The next network node chosen in operation62ofFIG. 3Bfrom the SPF nodes is the network node “L” (event214). Operation70is skipped by the processor circuit22, and since the network node “L” is not a safe network node, link L→D is identified by the processor circuit22as the SPF link, the link “E-L” is assigned as incoming to the network node “L”, and labeled in the state table54as unresolved to the nearest safe network node “A” (“E→L”=“?-A”) in operation72.

The next network node chosen by the processor circuit22in operation62ofFIG. 3Bfrom the SPF nodes is the network node “E” (event216). Operation70is skipped, and since the network node “E” is not a safe network node, in operation72the link E→C is identified by the processor circuit22as an SPF link, and all the non-SPF links are oriented as incoming to the network node “E” and labeled as unresolved to the nearest safe network node “A”, resulting in the labeling of the links F→E=“?-A”, G→E=“?-A”, and H→E=“?-A” in the state table54.

The next network node by the processor circuit22in operation62ofFIG. 3B and 104from the SPF nodes is the network node “F” (event218). Operation70is skipped by the processor circuit22, and since the network node “F” is not a safe network node, in operation72the link F→C is identified as an SPF link, and all the non-SPF links are oriented as incoming to the network node “F” and labeled by the processor circuit22as unresolved to the nearest safe network node “A”, resulting in the labeling of the links H→F=“?-A”, I→F=“?-A”, and J→F=“?-A” in the state table54.

The next network node chosen by the processor circuit22in operation62ofFIG. 3Bfrom the SPF nodes is the network node “N” (event220). The network node “N” is identified by the processor circuit22as leaf network node based on its one and only one link N→L; hence, the link “N-L” is marked in the state table54as resolved (N→L=Resolved) in operation70.

The next network node chosen by the processor circuit22in operation62ofFIG. 3Bfrom the SPF nodes is the network node “G” (event222). Operation70is skipped, and since the network node “G” is not a safe network node, in operation72the link G→E is identified by the processor circuit22as an SPF link, and the non-SPF link H-G is oriented as incoming to the network node “G” and labeled as unresolved to the nearest safe network node “A”, resulting in the labeling of the link H→G=“?-A” in the state table54.

The next network node chosen in operation62by the processor circuit22from the SPF nodes is the network node “H” (event224). Since the network node “H” is not a safe network node, in operation72the link H→F is identified by the processor circuit22as an SPF link, and the non-SPF link I-H is oriented as incoming to the network node “H” and labeled as unresolved to the nearest safe network node “A”, resulting in the labeling of the link I→H=“?-A” by the processor circuit22in the state table54.

The next network node chosen by the processor circuit22is the network node “I” (event226. Since the network node “I” is not a safe network node, in operation72the link I→F is identified by the processor circuit22as an SPF link in the state table54. As described previously, each of the SPF links58also can be labeled by the processor circuit22in the topology table56ofFIG. 5.

As apparent from the foregoing description with respect toFIG. 6B, the identification of SPF links and unresolved links enables identification of the shortest path tree plus alternative unresolved links that can be used for identification of an alternate non-congruent path that is distinct from the shortest path to the root network node. The following description with respect to node “J” demonstrates how the identification of the alternative unresolved links enables identification of one or more junction nodes within the subDAGs64aand64bfor formation of the arc routing topology.

In particular, the following description illustrates the identification within the DAG52(two or more) junction nodes, and reversible links (labeled “Rev”) between the unction nodes and that can be reversed along one of the non-congruent paths of the junction nodes, without introducing a loop into the loop-free topology. In addition, the identification of a junction node in one subDAG (64aor64b) that has a non-congruent path for reaching the destination network node14(distinct from the junction node serving as the root of the subDAG) enables formation of another infrastructure arc overlying a first infrastructure arc.

As illustrated with respect toFIGS. 6B and 6C, the next network node chosen by the processor circuit22in operation62ofFIG. 3Bfrom the SPF nodes is the network node “J” (event228). The node “J” is identified by the processor circuit22as a safe network node because it can be classified as a junction node68, illustrated inFIGS. 3C and 3D. The node “J” can be identified by the processor circuit22as a junction node because it has two non-congruent paths for reaching a safe node (e.g., the root network node “R”) via the link J→F (labeled as unresolved to the nearest safe network node “A”, i.e., “?-A”), and/or the link J→K (labeled as the SPF link unresolved to the nearest safe network node “B”, i.e., “?-B”). Hence, the non-congruent paths provided by the links J→F and J→K are identified by the respective and distinct labels “?-A” and “?-B” identifying reachability to the root network node “R” via the respective safe network nodes “A” and “B”.

Operation72is skipped by the processor circuit22because the network node “J” is identified as a junction node. Each of the data links of the network node “J” are resolved in operation74in a prescribed order, namely SPF link first, then any outgoing link(s), then any incoming link(s). Hence, the link J→K is the SPF link and therefore the first link to be analyzed in operation74. Since the link J→K is unresolved in operation76, the outgoing link J→K in operation78does not end in another junction, hence operation80is skipped.

Referring toFIG. 3D, the processor circuit22determines whether to execute operation82if the network node is not yet an intermediate junction. Operation82is executed by the processor circuit22for the link J→K of the network node “J” because if the link J→K, if reversed, the link reversal would enable the endpoint network node “K” to become a junction node, i.e., the endpoint network node “K” could now have an alternate path to the root network node “R” via the safe network node “A” (e.g., if the label of link J→K was changed upon link reversal from “?-B” to “?-A”); hence, the link J→K enables the node “J” to become a junction and does not cause any pruning of the SPF link J→K. Consequently, the link J→K is resolved by marking the link in the state table54as reversible (“Rev”) by the processor circuit22in operation82. The labeling of the link J→K as reversible (“Rev”) is illustrated inFIG. 6D.

Since the node “J” is an edge junction toward the safe network node “B”, operation84is executed by the processor circuit22to prevent the formation of a loop via the outward link “J→M” in the event that the link J→K is ever reversed to K→J in order to reach the safe network node “A”; hence, since “J→M”=“?-B” is an outward link satisfying the condition “?-S” (where S=B), the outward link “J→M”=“?-B” is pruned in operation84by blocking the path toward node “M” (note the square inFIG. 6Cat the end of the link intersecting with network node “M”, indicating traffic from network node “J” to network node “M” is blocked); the direction of the pruned (i.e., blocked) link J-M is reversed and relabeled by the processor circuit22as unresolved inward toward the new safe network node (junction node), i.e., M→J=“?-J” in the state table54.

Also note that if in operation84another link existed (e.g., J→B) (not shown inFIG. 6B) as an unresolved link toward the safe node “B” (J→B=“?-B”), that link (J→B) could be pruned at both ends (i.e., removed: J-B) in order to avoid the possibility of any loops in the event of any link reversal.

Hence, in order to avoid loops a junction node in a routing arc can have one and only one link toward a first end of the arc, and one and only one other link toward a second end of the arc. The link J→F is unaffected in operation84because J is an edge junction toward safe node “B” (via J→K), whereas the node J→F is toward the other safe network node “A”.

Operation86is skipped by the processor circuit22for junction node “J” because it is not yet an intermediate junction because it does not yet have two reversible links. Operation88is skipped because the SPF link J→K is assigned as an outgoing link.

Execution of operation78by the processor circuit22with respect to the SPF link J→K (“Rev”) continues in operation90, which recursively calls execution of operation66(as illustrated inFIGS. 3C and 3D) for the endpoint of the link J→K, namely the network node “K”, in order to extend the arc along the shortest path; in other words, the operations ofFIGS. 3C and 3Dare executed based on the change in status of the link J→K to a reversible link (event230ofFIG. 4B). Hence, operation70is skipped for the J→K link endpoint node “K” (which is not a leaf node). The J→K link enables the endpoint node “K” to now become a junction node since the link J→K link is now reversible, hence the network node “K” as a junction node (specifically, an edge junction), and now a safe network node, hence operation72is skipped by the processor circuit22. Each of the safe network node “K” links are resolved in operation74, starting with the SPF link K→B: operation76is skipped by the processor circuit22because the SPF link K→B=“?-B” is not yet resolved. The SPF link K→B is an outgoing link, hence operation78is executed by the processor circuit22: operation80is not executed by the processor circuit22because the node K→B does not end in another junction node (i.e., the heir network node “B” is not a junction node). Operation82is executed by the processor circuit22because network node “K” is not an intermediate junction node yet, and the link K→B enables the end point network node B to become a junction node, hence the node K→B is labeled as reversible, K→B=“Rev” in operation82, to enable the heir network node “B” to become labeled by the processor circuit22as a junction node in the state table54.

In operation84the node N=K is now an edge junction toward node “B”, and there is no outward unresolved link to be pruned; however, the link M→K is relabeled by the processor circuit22from “?-B” to “?-K” in the state table54. In operation86the network node “K” is now identified by the processor circuit22as an intermediate junction having two reversible links J→K=“Rev” and K→B=“Rev”; however, there are no other outward links other than the two reversible links, hence no pruning of other outward links is needed.

Hence, the resolution of the link J→K at node J as a reversible link causes resolution of the link endpoint K to be recursively resolved by the processor circuit22at operation90, resulting in the resolution of reversible link K→B at node K. The resolution of the reversible link K→B at node K causes in operation90the recursive resolution by the processor circuit22of the link endpoint B (event232).

The heir network node B is identified as an edge junction based on the reversible link K→B, and since the SPF link B→R is to the root, the heir network node “B” is identified as the end of a routing arc. The resolution of node B causes the recursive execution by the processor circuit22in operation90to return to network node “K” (event234) to continue resolving the remaining links of the network node K.

Hence, the SPF link has been resolved in network node K, no outgoing links need to be resolved, causing the analysis of the link M→K=“?-K” at operation74. Each of the operations76,78, are skipped by the processor circuit22because the link M→K is not outgoing, and the incoming link is already marked unresolved to K “?-K”. Hence, the processor circuit recursively resolves the endpoint M of the link K→M in operation90(event236).

The network node M is determined by the processor circuit22in operation72to be a safe node because it has two non-congruent paths to the root, namely the path “?-K” via the link M→K, and the path “?-J” via the link M→J. Starting with the shortest path link M→K, in operation78the link is identified in operation80as ending in another junction “K”, enabling the link M→K to be marked by the processor circuit22as resolved in the state table54(and a first end of the collapsed arc “ARC1” ofFIG. 6DandFIG. 6I). A recursive call by the processor circuit22from network node M to network node K in operation90(event238) results in no changes, hence the processor circuit22returns to network node M (event240), and the processor circuit22resolves the next outgoing and unresolved link M→J=“?-J” into a resolved link in operation80(and the second end of the collapsed arc “ARC1” ofFIG. 6I).

Referring toFIG. 4B, the recursive resolution of network node “M” (as the endpoint of the link M-K) is complete, causing the processor circuit22return to the network node “K” at event242ofFIG. 4C; the recursive resolution of the network node “K” also is complete, causing the return to network node “J” at event244.

Note that the network nodes “K” and “M” are junction nodes without changing the link reversibility. Hence, the link M→J terminates a routing arc because it ends in a junction node “J”, and the link M→K terminates in a routing arc because it ends in another junction node “K”. Hence, the network nodes “J”, “K”, and “M” form a collapsed arc “ARC1”12, illustrated inFIG. 6D.

The processor circuit22in operation74repeats the link analysis for the next link of the junction node “J”, namely the outgoing link J→F=“?-A”. After skipping operation76, operation80is skipped by the processor circuit22because the network node “F” is not a junction inFIG. 6D, hence link J→F does not end in another junction. The network node “J” is not an intermediate junction yet because it does not have two reversible paths, hence operation82is executed to make the link J→F reversible (J→F=“Rev”) because the reversal of link J→F enables the endpoint network node “F” to become a junction having an alternate path to the root network node “R” via “?-A” and the path via the network node “J”. The network node “J” was already an edge junction, hence operation84is skipped.

Marking the link J→F reversible in operation78, however, now makes the safe node “J” an intermediate junction, hence operation86is executed by the processor circuit22: the description in operation86of “prune outwards all links of safe node N but the2reversible links . . . ” ensures that there are no outward links except along the arc (formed via network nodes F, J, K, and B)12, such that any other links are pruned and directed inwards (as executed previously with respect to the link M→J). Operation88is skipped by the processor circuit22because the link J→F is not incoming, and operation90is executed to recursively resolve the neighbor for the endpoint node of the link J→F, namely the network node “F” (event246).

The processor circuit22skips operation70during resolution of the network node “F” it has multiple links. The network node “F” is identified as an edge junction (and therefore a safe node) because it has two non-congruent paths to the root node “R”, and the network node “F” includes one reversible link J→F, hence, execution of operation72is skipped. As will be described in further detail below, the junction node “F” belongs to the subDAG(A)64aofFIG. 6B, and the junction nodes “J”, “K”, and “B” belong to the subDAG(B)64b; hence, a first infrastructure arc (“ARC2” illustrated inFIG. 6E)12can be created that comprises (at least two or more) junction nodes and (one or more) reversible links, where one end of the first infrastructure arc terminates at the destination network node “R”.

Each of the links of the safe node “F” are analyzed in operation74, starting with the SPF link F→C: operations76and80are skipped, and operation82is executed by the processor circuit22to mark the link F→C as reversible (F→C=“Rev”). Operation84is executed by the processor circuit22because the network node “F” is now an edge junction towards “S” (S=A). Hence, in operation84any outgoing unresolved links labeled “?-A” (e.g., F→E=“?-A”) are pruned and reversed inwards toward the edge junction and marked by the processor circuit22as unresolved toward the edge junction (e.g., change from F→E=“?-A” to E→F=“?-F”) in the state table54; further, in operation84all incoming links (i.e., inward links) of the safe node “F” are changed by the processor circuit22from “?-A” to “?-F” (e.g., change H→F=“?-A” and I→F=“?-A” to H→F=“?-F” and I→F=“?-F”). The relabeling of the links E→F, H→F, and I→F in operation84in the state table54exposes the network nodes “E”, “H”, and “I” to the alternate path to the root node “R” via the edge junction “F”, enabling the network nodes “E”, “H”, and “I” to be later identified as new junction nodes (and therefore safe network nodes) having new non-congruent paths for reaching the root node “R”, distinct from the path provided by the subDAG (A)64a. hence, the network nodes “E”, “H”, and “I” can later be used to create secondary infrastructure arcs based on the non-congruent paths distinct from the subDAG (A)64a.

The edge junction “F” is not an intermediate junction yet, hence operation86is skipped, and operation88is skipped because the incoming link E→F is already marked “?-F” as unresolved toward the edge junction “F”.

A recursive call is executed by the processor circuit22in operation90for the endpoint network node “C” of the SPF link F→C=“Rev” (event248).

The recursive resolution by the processor circuit22of the network node “C” skips operation70because it has multiple links. The network node “C” is identified as an edge junction (and therefore a safe node) because it has two paths to the root node “R”, and the network node “C” includes one reversible link F→C, hence, execution of operation72is skipped by the processor circuit22. Operations76and80are skipped, and operation82is executed by the processor circuit22to mark the link C→A as reversible (C→A=“Rev”) in the state table54. Operation84is executed by the processor circuit22because the network node “C” is now an edge junction towards “S” (S=A). Hence, in operation84any outgoing unresolved links labeled “?-A” (e.g., C→D=“?-A”) are pruned and reversed inwards by the processor circuit22toward the edge junction “C” and marked in the state table54as unresolved toward the edge junction (e.g., change from C→D=“?-A” to D→C=“?-C”); further, in operation84any incoming links of the safe node “C” are changed by the processor circuit22from “?-A” to “?-C” (e.g., change E→C=“?-A” to E→C=“?-C”) in the state table54. The relabeling of the links D→C and E→C in operation84exposes the network node “D” to an alternate path to the root node “R” via the edge junction “C”, enabling the network node “D” to be later identified as a junction node having two non-congruent paths for reaching the root node “R”.

The edge junction “C” is not an intermediate junction yet, hence operation86is skipped by the processor circuit22, and the link C→A is not incoming, hence operation88is skipped. A recursive call is executed in operation90for the endpoint network node “A” of the SPF link C→A=“Rev” (event250).

The recursive resolution by the processor circuit22of the network node “A” skips operation70because it has multiple links. The heir network node “A” is a safe node, and is identified as an edge junction because it has two non-congruent paths to the root node “R”, and the network node “A” includes one reversible link C→A, hence, execution of operation72is skipped.

The SPF link A→R is first selected in operation74and identified in operation76as resolved. The resolved SPF link A→R also ends in the root “R”, and therefore terminates the arc identified by the sequence of recursively called neighbors A(C,F, J) extending back to the intermediate junction “J”, and extending to the edge junction “B”.

Hence, the identification of the SPF link A→R as resolved during the successive recursion by the processor circuit22from the intermediate junction “J” (i.e., a junction node having two reversible links), establishes the junction node “A” as the second edge junction, resulting in the first infrastructure arc “ARC2” for reaching the root node “R”, illustrated inFIG. 6EandFIG. 6I. As illustrated inFIGS. 6E, 6H, and 6I, the infrastructure arc “ARC2” for reaching the root node “R” includes the junction nodes “A”, “C”, “F”, “J”, “K”, and “B” connected by the reversible links A-C, C-F, F-J, J-K, and K-B. Hence, the infrastructure arc “ARC2” for reaching the root node “R” can be identified based on traversing the sequence of an heir network node (e.g., “A”) and the sequence of reversible links until reaching another heir network node (e.g., “B”).

The next link of junction node “A” is analyzed in operation74, namely the link D→A=?-A, resulting in the recursive resolution of the network node “D” in operation90(event252). The network node “D” is now a junction node (and therefore a safe node), because it has two non-congruent paths (via nodes A and C) for reaching the root node “R”. Hence, operations70and72are skipped, and operation74is executed first for the SPF link D→A. The link D→A is marked as resolved in operation80based on terminating in the junction node A. The recursive calling from node “D” to node “A” causes the recursive analysis for node “A” to return back to node “D”, as all other links have already been analyzed with respect to node “A”: such a return is referred to as a “no-op recursion”, and will be omitted in future discussion for brevity.

The analysis for node “D” continues for link D→C in operation74. The link D→C ends in the junction node “C” and therefore is marked as resolved in operation80, resulting in the formation of the collapsed arc “ARC3”12illustrated inFIG. 6I. The incoming link L→D is next analyzed with respect to the junction node D in operation74, and relabeled in operation88from the unresolved status of ?-A to the unresolved status ?-D (L→D=“?-D”), indicating that the nearest safe node is the node “D”.

As illustrated inFIG. 6F, the safe node “D” can form its own subordinate directed acyclic graph SubDAG(D)64dwithin the SubDAG(A)64toward the root node “R”, such that the safe node “D” becomes the closest safe node for the network nodes “L”, “N”, “E”, “G”, “H”, and “I”. Hence, similar to operation72, all the unresolved incoming links in the SubDAG of safe node “D” (e.g., links L→D, E→D, E→L, G→E, H→G, I→H, and H→E) are recursively relabeled (i.e., marked) in operation88to “?-D” to propagate the identification of the newest safe node “D” (state252).

The recursive analysis in operation90of the node “L” by the processor circuit22results in a no-op recursion because the node “L” is not yet a safe node, hence the analysis returns to the node “D”.

The link E→D is next analyzed with respect to the junction node D in operation74, and relabeled in operation88by the processor circuit22from the unresolved status of ?-A to the unresolved status ?-D (E→D=“?-D”) in the state table54. The analysis for node E is recursively called by the processor circuit22in operation90(event254).

The network node E is a junction node (and therefore a safe node) because it has two non-congruent paths to the root via junction nodes “D” and “E”, without changing any link reversibility. The following links of junction node “E” need to be analyzed in operation74, in the following example order: E→C, E→D, E→L, E→F, G→E, and H→E.

Hence, the SPF link E→C is marked as resolved in operation80because it ends in the junction node “C”. The outgoing link E→D is analyzed with respect to the network node “E” in operation74, and is marked as resolved in operation80(becoming the first end of the collapsed arc “ARC8” ofFIG. 6I) because it ends in the junction node “D”. The outgoing link E→L is next analyzed in operation74, and since the link E→L enables in operation82the endpoint node “L” to become a junction, the link E→L is marked as reversible in operation82. The endpoint “L” is recursively analyzed in operation90(event256).

Referring toFIG. 4Dand event256, the network node “L” is identified as an edge junction (and therefore a safe node) because it has the reversible link E→L. The link L→D is marked as resolved in operation80because it ends in the junction node “D”, resulting in the formation of the second infrastructure arc “ARC4” ofFIG. 6GandFIG. 6I. Since the arc “ARC4” ends in a safe node “D”, then even though all traffic from the arc “ARC4” could exit via network node C (i.e., network node “D” sends its traffic to network node C via the link D→C), the network node “D” still has an alternate path via network node A. The link N→L has already been resolved for the leaf node N, hence the analysis returns to network node “E”.

The next link under analysis by the processor circuit22with respect to the network node “E” (event258) is the link E→F=?-F in operation74. The link E→F is resolved in operation80as ending in the junction node “F” (resulting in the formation of the collapsed arc “ARC8”). Although the link E→F was pruned as unidirectional, it could be safely reversed for LFA analysis, if desired (operation90is a no-op for the endpoint node F of link E→F, hence, analysis returns to the network node “E”).

The incoming link G→E of network node “E” is next analyzed in operation74. Since the network node “G” is not a junction, it is not a safe node and therefore the link G→E cannot be resolved, but is relabeled ?-E in operation88: all incoming links to the safe node “E” also are recursively marked by the processor circuit22as unresolved toward “E” (namely, links G→E, H→E, H→G, and I→H all are reset to “?-E”) resulting in the formation of a subDAG(E) toward E. Analysis of the network node “G” is recursively called as the endpoint of the link G→E in operation88.

The network node “G” (event260) is determined to not be a junction node, and all links are already labeled to the nearest safe node “E”, hence operation72can be skipped and the processor circuit22can return back to node “E” in event262.

The next incoming link H→E of the safe node “E” is analyzed in operation74, causing the processor circuit to recursively analyze in operation90the endpoint node “H” at event264.

The network node “H” in operations72and74is identified as a junction node having non-congruent paths via unresolved paths “?-F” (via the SPF link H→F) and “?-E” (via the links H→E and H→G). Hence, each of the links of the safe node “H” are successively resolved in operation74, namely the links H→F, H→E, H→G, and I→H.

The SPF link H→F of the safe network node “H” is resolved by the processor circuit in operation80as ending in the junction node “F”: as will be shown later, the link H→F will terminate the infrastructure arc “ARC5” and the collapsed arc “ARC6” ofFIG. 6I. Operation90results in a no-op recursive analysis of node “F” (as the endpoint of the link H→F), hence, the analysis of the next (outgoing) link H→E for the safe node “H” in operation74causes the link H→E (ending in the junction node “E”) to be resolved in operation80as the second end of the collapsed arc “ARC6”.

Operation90results in the no-op recursive analysis of node “E” (as the endpoint of the link H→E), hence the analysis of the next (outgoing link) H→G for the safe node “H” is executed in operation74. In operation82the link H→G enables the endpoint node “G” to become a junction; further, the link H→G if reversed does not cause pruning of the SPF link H→F; hence, the link H→G is relabeled in operation82by the processor circuit22to a reversible link (H→G=“Rev”) in the state table54. Operation90is executed for recursive analysis of the endpoint node “G” of the link H→G (event266).

The network node “G” is determined in operation72to be an edge junction (and therefore a safe node) based on the reversible link H→G. Hence, analysis of the SPF link G→E in operation74results in operation80with the link G→E being labeled as resolved as the second end of the infrastructure arc “ARC5”. Operation90results in the no-op recursive analysis of node “E” (as the endpoint of the link G→E), and since the safe network node “G” has no other links to resolve, execution returns to node “H” for evaluation of the next incoming link I→H (event268).

The next link in operation74, namely the incoming link I→H of the safe network node “H”: The link I→H is relabeled in operation88from I→H=“?-A” to I→H=“?-H”, and the operation90is executed by the processor circuit22for recursive analysis of the endpoint node “I” of the link I→H (event270).

The network node “I” is determined by the processor circuit22in operation72to be a junction node having non-congruent paths via unresolved paths “?-F” (via the SPF link I→F) and “?-H” (via the outgoing link I→H). Hence, in operation74the SPF link I→F is analyzed by the processor circuit22, and marked in operation80as resolved (and terminating the collapsed arc “ARC7”) based on ending in the junction node “F”. Operation90results in the no-op recursive analysis of node “F” (as the endpoint of the link I→F), resulting in analysis in operation74of the next (outgoing link) I→H. Since the link I→H ends in the junction node “H”, the link I→H is labeled in operation114as resolved, forming the second end of the collapsed arc “ARC7” ofFIG. 6I. Operation90results in the no-op recursive analysis of node “H” (as the endpoint of the link I→H), returning execution analysis to junction node “I”.

Analysis of node “I” is completed by the processor circuit22, returning execution analysis by the processor circuit22to node “H”; analysis of node “H” is complete, returning execution analysis to node “E”; analysis of node “E” is complete, returning execution analysis to node “D”; analysis of node “D” is complete, returning execution analysis to node “A”; analysis of node “A” is complete, returning execution analysis to node “C”; analysis of node “C” is complete, returning execution analysis to node “F”; and analysis of node “F” is complete, returning execution analysis to node “J”. As described previously, the processor circuit22can update the topology table56ofFIG. 5as each routing arc is constructed, where the ownership of an arc cursor is identified by the junction node having the two outwardly oriented reversible links.

The resulting link topology is illustrated inFIG. 6H, with the resulting arcs “ARC1” through “ARC8” illustrated inFIG. 6I. The routing topology ofFIG. 6Iillustrates the routing arcs “ARC1” through “ARC8”, with all the network nodes being junction nodes except for the root network node “R” and the leaf node “N”. As illustrated inFIGS. 6H and 6I, the collapsed arc “ARC1” includes the junction nodes “J”, “M”, and “K”; the infrastructure arc “ARC2” for reaching the root node “R” includes the junction nodes “A”, “C”, “F”, “J”, “K”, and “B” connected by the reversible links C→A, F→C, J→F, J→K, and K→B; the collapsed arc “ARC3” includes the junction nodes “A”, “D”, and “C”; the infrastructure arc “ARC4” includes the junction nodes “D”, “L”, “E”, and “C”; the infrastructure arc “ARC5” includes the junction nodes “E”, “G”, “H”, and “F”; the collapsed arc “ARC6” includes the junction nodes “E”, “H”, and “F”; the collapsed arc “ARC7” includes the junction nodes “H”, “I”, and “F”; and the collapsed arc “ARC8” has the junction nodes “D”, “E”, and “F”.

Consequently, assuming the link F→C encountered a failure, the network node “F” could redirect traffic to the node “J” via the reversible link J→F (e.g., based on the network nodes “F” and “J” negotiating that the link J→F needs to be reversed to F→J, enabling network traffic to be redirected without recalculation of routes.

As apparent from this disclosure, the loop-free routing topology10for the destination network node (“R”)14can be repeated for each network node16, enabling each network node16to have its own loop-free routing topology10that guarantees reachability to the corresponding network node16via non-congruent paths.

Distributed Establishment of Loop-Free Label Switched Paths in the Loop-Free Routing Topology

As described previously, the loop-free routing topology10illustrated inFIG. 6Ienables network traffic to be redirected instantaneously in response to a detected failure in the routing topology based on reversing a reversible link, without introducing any loops into the topology. The loop-free routing topology10also can utilize a new label distribution protocol that enables the network nodes16to establish loop-free label switched paths for reaching the destination network node14via the loop-free routing topology10. The apparatus20can be configured for not only computing the arc topology10, but also generating a set of serialized representations describing the loop-free routing topology, where each serialized representation describes a corresponding path in the topology: as described herein, the “path” as used herein is not necessarily limited to the disclosed routing arcs. The set of serialized representations can be propagated from the destination network node14to the network nodes16in the computing network, enabling each of the network notes to establish their own loop-free label switched paths for reaching the destination network node14.

The apparatus can be implemented, for example, as a centralized path computing engine associated with a network management system, the destination network node14, or any node computing the topology10for a number of destinations within a prescribed autonomous system.

FIG. 7illustrates an example hierarchy10′ of successively cascaded routing arcs, constructed by the apparatus20ofFIG. 2according to an example embodiment. In particular, the loop-free routing topology10can be represented by the apparatus20as a hierarchy10′ that contains the same routing arcs12for reaching the destination14, except that the routing arcs12are redrawn as a hierarchy of successively cascaded (collapsed) routing arcs12or12′ that supply network traffic in the “downward” direction100to a destination14.

As illustrated inFIG. 7, all network traffic toward the destination14follows the direction of the network traffic flow100, ending at the root14or the network nodes “A”, “C”, or “F” along the root arc “ARC2”12. Hence, all network traffic flows along the path100down the hierarchy10′ of successively cascaded routing arcs12or12′ supplying network traffic to the destination14.

Conversely, topology control messages102can be propagated from the destination network node14to each of the network nodes16in the computing network. The topology control messages102can include a “set of serialized representations” (described below) describing relevant paths (e.g., routing arcs12) of the loop-free routing topology10. The topology control message102can be used to flood the serialized representations of the relevant paths over the loop-free routing topology10, across each of the network nodes16along each of the routing arcs12: in other words, a network node (e.g., “C”)16passes the topology control message (containing the set of serialized representations) to any of its neighbors that can send network traffic back to that network node (e.g., “C”), except that the network node (e.g., “C”) will not send the topology control message back to the transmitting network node (e.g., “A”) that had just sent the topology control message to the network node (“C”). Hence, each network node16can learn the relevant paths of the loop-free routing topology10in response to parsing the set of serialized representations contained in a topology control message102.

Each topology control message102also includes one or more locally significant labels (“λ”) generated by the network node16transmitting the topology control message102. Each locally significant label generated by the transmitting network node16can have an arbitrary numeric value. As described below, each locally significant label is associated with prescribed attributes set by the transmitting network node16for forwarding a data packet to the destination network node14: as described below with respect toFIG. 15the transmitting network node16stores the locally significant table (and associated attributes) in a label forwarding table (also referred to as a label switched forwarding table); the network node receiving the topology control message102also stores the received locally significant label in a new label forwarding table entry in its own label forwarding table, creates a new locally significant label as an index to the new label forwarding table entry, and retransmits the set of serialized representations with the new locally significant label in a retransmitted topology control message.

Hence, the topology control messages102enable the network nodes16to each independently establish loop-free label switched paths for reaching the destination network node14via the loop-free routing topology10. Moreover, multiple locally significant labels can be specified within a single topology control message102, for example a primary label for a default path to reach the destination, and a “backup” (or “fast reroute”) path to reach the destination. Topology control messages102also can be propagated along both ends of a bidirectional routing arc12, resulting in a total of four locally significant labels identifying four respective paths available for reaching the destination node14by a network node16. The loop-free label switched paths can be implemented, for example, using multiprotocol label switched (MPLS) labels according to RFC 3031 or RFC 6178, label distribution protocol (LDP) according to RFC 3036 or 5036; alternately the labels can use other tagging techniques, for example IEEE 802.1q (or Q in Q) as labels in carrier Ethernet, IPv6 flow labels, or direct encapsulation over ATM or frame relay. Other topology information can be transmitted over the routing arcs12once established, for example as illustrated in U.S. Pat. No. 7,693,064.

Hence, the label switched paths enable any network node16along the bidirectional paths to instantaneously reverse the transmission of a data packet to an alternate (backup) label switched path in response to the network node detecting a failed link; moreover, loops are avoided by using different label switched paths to identify a default path in one direction of the bidirectional path (e.g., routing arc), a default path in a second direction of the bidirectional path, a backup (fast reroute) path that is used in response to detecting a failed link in the default path in the one direction, and a second backup (fast reroute) path than that is used in response to detecting a failed link in the default path in the second direction.

FIG. 8illustrates an example method for label distribution and route installation in the loop-free routing topology, according to an example embodiment. Referring toFIGS. 2, 6I, and8, the processor circuit22in the apparatus20is configured for creating in a computing network a loop-free routing topology10for reaching the destination network node “R” in operation110as illustrated inFIG. 6Iand as described previously with respect toFIGS. 1 through 6I. The computing network may be an autonomous system, or any part thereof, for example a local area network, an ad hoc network such as a mobile ad hoc network, a sensor network, etc. As described previously, the loop-free routing topology10comprises distinct paths12for reaching the destination network node14.

The processor circuit22also is configured for generating in operation12a set of serialized representations describing the loop-free routing topology10. As described in further detail below with respectFIGS. 10 and 14, each serialized representation114describes a corresponding one of the paths12. The processor circuit22also assembles all of the serialized representations114of the respective paths (e.g., routing arcs12) into a set116of serialized representations, illustrated inFIG. 12. Hence, the set of serialized representations116can provide a representation of the entire loop-free routing topology10.

The processor circuit22can generate in operation118a topology control message102containing the set of serialized representations116, enabling the network interface circuit24of the destination node “R” to output in operation118the topology control message102on each of its incoming links (i.e., toward nodes “A” and “B”) causing the topology control message102to be propagated throughout the network. Since the destination node “R”14is the final destination for the loop-free topology10, the destination node14also is referred to generically as the “omega node” (Ω). Hence, the omega node (Ω=“R”)14defines the forwarding equivalence class (FEC) for the topology control message102: the topology control message102also specifies a locally significant label (e.g., an MPLS label) (e.g., “O=R_AR” for the link “R-A” or “R_BR” for the link “R-B”) that is associated with the network interface that outputs the message to the next hop network node16for the forwarding equivalence class “Ω=R”.

As used herein, the nomenclature “O=X_YZ” refers to a locally significant label “O” identifying the link in the direction from node “Z” to node “Y” for the forwarding equivalence class “Ω=X” to be used as a default (i.e., primary) path in reaching the destination node “Ω=X”: in other words, the node “Z” generates the locally significant label “O=X_YZ” to notify the node “Y” (i.e., topology control message “to Y from Z”) that the label “O=X_YZ” is to be used for forwarding a data packet via node “Z” along a default path to the destination node “Ω=X” (i.e., data traffic destined for “Ω=X” via default path is sent “from Y to Z”). An additional extension (e.g., “FRR”) can be used to identify an additional label attribute, namely that the link is to be used as a fast reroute (“FRR”) path (i.e., backup path) in the event of a link failure on the default path. The locally significant label can be implemented as a numeric value that provides an index into a label forwarding table within a network node. Hence, a topology control message102output by a network node16and containing the set of serialized representations can further include a default label “O=X_YZ” and a backup (fast reroute) label “O=X_ZY_FRR” for the forwarding equivalence class “Ω=X”. Since the routing arcs12are bidirectional, the node “Y” also can receive another topology control message12from the “other end” of its arc, and in response send to the node “Z” a topology control message102specifying the default label “O=X_ZY”, the backup label “O=X_YZ_FRR”, and the set of serialized representations. Hence, the omega node (Ω=“R”)14outputs in operation118(118aofFIG. 12) the topology control message102with the set of serialized arcs (116ofFIG. 12): the omega node (Ω=“R”)14also adds a locally significant label “O=R_AR” to the topology control message102output onto the link “R-A” to the network node “A”, and a locally significant label “O=R_BR” to the topology control message102output onto the link “R-B” to the network node “B”.

In response to the network node “A”16receiving the topology control message102with the locally significant label “O=R_AR” on an identified network interface (e.g., “A1”), the network node “A” can create in operation120an entry in its internal label forwarding table for the forwarding equivalence class Ω=“R” that any data packet destined for the destination node “Ω=R”14via the link “R-A” should be output onto the network interface “A1” with the locally significant label “O=R_AR” (as described previously, a locally significant label can be an arbitrary numeric value chosen by the source of the label).

The processor circuit22in the network node “A”16also can determine the routing topology10from the set of serialized arcs116in the topology control message102. Hence, the processor circuit22in the network node “A”16can create additional label forwarding table entries for the network nodes “C” and “D” that are configured to send network traffic to the destination node “Ω=R”14via the network node “A”: the label forwarding table entry for the network node “C” can specify a new locally significant label “O=R_CA” (used as an index into the label forwarding table), the destination label “O=R_AR”, and the outbound network interface A1. Hence, if the network node “A” receives a data packet from the network node “C” that specifies the locally significant label “O=R_CA”, the network node “A” can use the specified locally significant label as an index into the label forwarding table to recover from the forwarding table entry the destination label “O=R_AR” (to be swapped with the existing label in the received data packet) and output the data packet onto the network interface “A1” for transfer to the destination node14via the link “A-R”.

Hence, in operation118the network node “A” sends the topology control message102to the network node “C” with the locally significant label “O=R_CA”, and to the network node “D” with the locally significant label “O=R_DA”. The network node “C” can identify the network topology10from the set of serialized arcs116, and in response can update its label forwarding table in operation120with a forwarding table entry specifying the network interface (e.g., “C1”) having received the topology control message102from the network node “A”, the locally significant label “O=R_CA”, and new locally significant labels (e.g., “O=R_FC”, “O=R_EC”) used as indices into the label forwarding table for data packets received from other network nodes (e.g., “F” via C-F; “E” via C-E). The network node “C” can output the topology control message102to the network nodes “E” and “F” using the locally significant labels “O=R_EC” and “O=R_FC”, respectively.

Hence, the propagation in operation118of the topology control message enables the network nodes162establish the arc topology for reaching the omega node14; further, insertion and swapping of locally significant labels at each network node enables each of the network nodes16to independently establish loop-free label switched paths for reaching the destination network node14via the loop-free routing topology10.

FIG. 9illustrates an example method by the processor circuit22of the apparatus20of executing operation112ofFIG. 8, namely the serializing of the arc topology10, according to an example embodiment. The method begins in operation112abased on the processor circuit22of the apparatus20identifying in operation112beach path (e.g., routing arc)12by its arc cursor18, namely the identity of the network node16having position of the arc cursor18for a given routing arc12. As illustrated inFIG. 10, each routing arc12as identified by its arc reference (ARC1to ARC8) inFIG. 6Iis given a serialized arc identifier122based on the corresponding network node16having possession of the arc cursor18. For example, the network node “J” has possession of the cursor18for the routing arc “ARC2”12; the network node “E” has possession of the arc cursor18for the routing arcs “ARC4”12and “ARC8”, hence the serialized arc identifiers “E1” and “E2” are used to distinguish routing arcs12in instances where the same network node (“E”) has possession of multiple arc cursors18for respective routing arcs12(see also the serialized arc identifiers “H1” and “H2”122to distinguish the routing arcs “ARC5” and “ARC6” having their respective arc cursors18controlled by the network node “H”).

Hence, the serialized arc identifier122serves as metadata that identifies the network node16in the corresponding path (e.g., routing arc)12as possessing the corresponding our cursor18for control of traffic along the routing arc12.

The processor circuit20of the apparatus20generates in operation112ca list124(illustrated inFIGS. 10 and 14) identifying a contiguous sequence of arc nodes16along the corresponding arc12. For example, the serialized arc114aprovides the source route “{B, K, J, F, C, A}” along the arc having the serialized arc identifier “J”122for the routing arc “ARC2” inFIG. 6I. the processor circuit20also identifies in operation112dat least a first edge junction and a second edge junction of the routing arc12(i.e., exit nodes) that empties traffic from the routing arc to either the destination node14or another routing arc that is closer to the destination network node14than the corresponding routing arc12. As used in this description, any node (or nodes) within brackets “[ ]” identify an end of a routing arc (i.e., an exit node), such that the nodes “C” and “D” are the exit nodes for the routing arc “ARC4” in the serialized arc format114b; the contiguous sequence of arc nodes within brackets “{ }” refers to intermediate junction nodes that are not exit nodes.

As illustrated inFIG. 14, a serialized arc format114also can be generated in operation112efor a buttressing arc having zero (i.e., null) exit nodes on one end of the routing arc12a contiguous sequence of arc nodes along the buttressing arc (A, B, C, and D), with a list of exit nodes (e, f) coupled to the last network node “D”.

Hence, the serialized arc format114for each routing arc12includes a first list of exit nodes126, followed by a source route124of nodes along the arc, ending with another list126of exit nodes of the arc, enabling the formation of a complete source route along the corresponding arc12; in the case of a buttressing arc as inFIG. 14, one of the lists126can have null entries, however the other list126must specify at least one exit node for the arc. Hence, the serialized arc format114includes metadata for identifying the art cursor (via the serialized arc identifier122), exit nodes (126), and the intermediate nodes124between the exit nodes and along the routing arc12.

Hence, in operation112ofFIGS. 8 and 9the processor circuit22of the apparatus20assembles the serialized arc formats114for each of the individual arcs12into a single set116of serialized arcs. As described previously, the single set116of serialized arcs are output by the destination (omega) node14to the network nodes for propagation in operation118of the topology control messages102to enable building of the label switched paths by the network nodes16.

FIG. 11illustrates example propagation118of the topology control messages102throughout the network nodes16, according to an example embodiment. The omega node14outputs in operation118athe topology control message102, for example as a label distribution protocol (LDP) protocol data unit (PDU). As described previously, the topology control message102includes a set116of all the serialized arcs (114athrough114h); further, each topology control message102output by each network node16specifies a corresponding unique locally significant label “O” for associating the LDP PDU to the forwarding equivalence class “Ω=R”.

In response to a network node16receiving in operation118ba topology control message102, the corresponding processor circuit22of the network node16can parse from the topology control message102the locally significant label “O”, and the set116of serialized representations containing the serialized arc identifiers122and the serialized arc formats114describing the respective paths12. The corresponding processor circuit22of the network node16can decode in operation118cthe serialized arcs, as identified by their respective serialized arc identifiers122and their respective serialized arc formats114, and create the necessary entries into label forwarding table of the network node16. The network node16can optionally remove (i.e. proven) in operation118dat least one of the serialized representations from the received topology control message102based on the corresponding path being positioned between the network node and the destination14. The pruning of operation118dis described in further detail below with respect toFIG. 12. The network node16outputs in operation118ea modified (i.e., pruned) topology control message102on each of its inward arcs of the arcs topology10, for propagation to the next network nodes in the topology10.

FIG. 12illustrates a selective pruning of selected paths12from the set116of serialized representations propagated in the topology control message102by network nodes within the loop-free routing topology10, according to an example embodiment. The specific serialized arc formats114are omitted fromFIG. 12for simplicity, hence each arc is represented inFIG. 12merely by its serialized arc identifier122.

Operations128athrough128millustrate operation118dofFIG. 11executed by the different outputting network nodes. As illustrated with respect to operation128a, there is no pruning performed in the output set of serialized arcs116when transmitting the topology control message102from the destination node (Ω=R)14to the nodes along the root arc “ARC2”, namely from the destination node (Ω=R)14to either node “A” or “B”, from node “A” to “C”, from node “C” to node “F”, from node “F” to node “J”, etc. to node “B”; from node “B” to node “K”, from node “K” to node “J”, etc.

Hence, the topology control message102output from the destination node (Ω=R)14to node “A” is propagated around the arc “ARC2”12, enabling each network node16node along the path ARC2″12in the first direction to update its label forwarding table with the source node's locally significant label O, and swap with a new locally significant label O′ for use by the next hop node; similarly, the topology control message102output from the destination node (Ω=R)14to node “B” is propagated around the arc “ARC2”12, enabling each network node16along the path “ARC2”12in the second direction to update its label forwarding table with the source node's locally significant label O″, and swap with a new locally significant label O′″ for use by the next hop node.

In contrast, the network nodes16in the routing arcs above the root arc “ARC2”12(identified by its serialized art identifier “J”122) do not need the topology information for the root arc; hence, the network nodes “A”, “C”, and “F” can selectively prune the full set of serialized arcs116aas illustrated in operations128b,128c,128d,128e. for example, in operation128bthe network nodes “A” and “C” can prune the serialized arcs “J” and “M” (as represented inFIG. 10) from the set of serialized arcs116a, in order to send the pruned set116bto the network node “D”; similarly, the network nodes “C” and “E” can prune in operation128cthe serialized arcs “J”, “M”, and “D” from the set of serialized arcs116a, in order to send the pruned set116cto the network node “E”; the network node “F” can prune in operation128dthe serialized arcs “J”, “M”, “D”, “E1”, and “E2” from the set of serialized arcs116a, in order to send the pruned set116dto the network node “H”; the network node “F” also can prune in operation128ethe serialized arcs “J”, “M”, “D”, “E1”, “E2”, “H1”, and “H2” from the set of serialized arcs116a, in order to send the pruned set116eto the network node “I”.

Operations128fthrough1281illustrated further pruning that can be executed by other nodes in arcs that are above the root arc ARC2. Hence, each network node can selectively prune at least one of the serialized representations114from the received topology control message102based on the corresponding path12being positioned between the at least one network node and the destination network node14, and output the modified (i.e., pruned) topology control message to another one of the network nodes away from the destination and the selectively pruned path.

FIG. 13illustrates an example method of establishing the loop-free label switched paths by the network nodes receiving the set when 16 of serialized representations from the destination network node14, according to an example embodiment.

As described previously, the sourcing network node (e.g., the destination node (Ω=R)14or an exit node of a lower routing arc12) outputs a topology control message102specifying the forwarding equivalence class (FEC) for the destination node (Ω=R)14; the topology control message102also specifies a locally significant label O that is unique for the sourcing node based on path direction, whether the path is the primary (default) path or a fast reroute (backup) path, arc identifier, and the forwarding equivalency class.

Assume the receiving network node that receives in operation130the topology control message102is node “F” that receives the topology control message from the node C: the topology control message specifies the label “O=R_FC” generated by the node “C” (i.e., for the FEC=R, output on link C-F in the “LEFT” direction from node F to node C). In response, the node “F” decodes in operation132the set of serialized arcs for the forwarding equivalence class and installs an entry in the label forwarding table associated with the locally significant label “O=R_FC” specified in the topology control message102.

FIG. 15illustrates an example label forwarding table148stored in the memory circuit26of the network node “F”16, according to an example embodiment. In particular, the processor circuit22of the node “F” creates an entry in operation134ofFIGS. 13 and 15, using the new label “O=R_JF” created by node “F” as an index: hence, any data packet received by node “F” (e.g., from node J) containing the label “O=R_JF” is swapped with the left primary swap label (LP) “O=R_FC” and output on the network interface identified as “InterfaceLP_ID” to the link F-C for switching to the node “C”; if the node “F” detects a failure on the link C-F, then fast reroute can be instantly implemented by swapping the label “O=R_JF” with the right-direction fast reroute (RFF) label “O=R_FJ_FRR” and outputting the packet on the interface “InterfaceRFF_ID” for transmission of the data packet via the link F-J back to the node “J”.

The network node (e.g., “F”) can choose in operation136a new locally significant label for each of the other next hop nodes that did not send the topology control message102, and forward the topology control message on the inward links (e.g., F-J, F-I, F-H, or F-E). The relevant table entries also are created in operation150ofFIG. 15. For example, the network node “F” would send to the network node “J” the topology control message102specifying the set of serialized representations, and the labels “O=R_JF” for the default path and “O=R_FJ_FRR” for the fast reroute (FRR) path.

Assuming in operation138that another topology control message102is received from the other side of the arc (e.g., “F” receives the message102from node “J” with the label “O=R_FJ”), the node “F” can add the corresponding entry in the label forwarding table in operation140, including a right primary swap label (RP) and a left fast reroute (LFF), enabling association of the locally significant label (e.g., “O=R_CF”) as described previously, but in the opposite direction.

The processor circuit22in each network node16also implements switching rules in operation142, illustrated inFIG. 15based on the incoming label. In particular, for Inter-arc switching152, either the left primary or right primary labels may be used depending on the position of the network node relative to the arc cursor. For intra-arc (i.e. within the arc) switching154, loop-free fast reroute is utilized in response to a detected local link failure: (1) a left primary (LP) label is swapped with a Right Fast Reroute (RFF) label; (2) a right primary (RP) label is swapped with a Left Fast Reroute (LFF) label; and (3) any received packet having a RFF label or LFF label is dropped to prevent the formation of a loop (156ofFIG. 15).

Hence, fast reroute is implemented instantly in response to a detected link failure: four label switched paths are maintained by each network node, namely: left-primary (in the left direction), right-fast reroute (in the right direction in response to a detected link failure for left-primary), right-primary (in the right direction), and left-fast reroute (in the left direction in response to a detected link failure for right-primary). Further, a fast reroute label state is propagated in the rerouted direction; hence, a second link failure in the same arc will cause the data packet to be dropped, avoiding the formation of a loop.

The topology control message received in operation144also is forwarded after a new locally significant label is chosen.

Hence, labels can be established within a routing topology that enables full redundancy in two connected graphs: a new label distribution protocol format is introduced that contains a new non-linear source route information to describe the routing arc topology. Each routing arc allows one link failure, hence the arc topology can support multiple concurrent link failures that might occur in different routing arcs. Further, the label distribution protocol can be deployed automatically and independently by the network nodes in the computing network.

Creating Non-Congruent Paths in the Loop-Free Routing Topology Having Routing Arcs

FIGS. 16A-16Cillustrate creation of non-congruent paths300aand300b(illustrated inFIGS. 16B and 16C) in the loop-free routing topology10that enables bicasting of network traffic between a source network node and a destination network node14, according to an example embodiment. The term “bicasting” refers to a network node within the loop-free routing topology10(e.g., a host network node such as a controller device, a sensor device, a user device, etc.) that outputs two data packets containing the same payload for delivery to a destination: one data packet is routed to a destination via a first multi-hop network path to the destination, and a bicasted copy of the data packet is routed to the destination via a second multi-hop network path that is distinct from the first multi-hop network path. Bicasting is effective in deployments where reliability and timeliness must be guaranteed. Bicasting also can be used in video distribution.

As an example of bicasting, a single packet could be routed via the routing arcs12along the shortest path to the destination network node (i.e., “root”)14, based on the above-described routing of traffic away from the arc cursor18; however any such routing of a data packet may require utilizing fast reroute to reverse the flow for the data packet in response to a failure in the network topology.

According to an example embodiment, the non-congruent paths300aand300bguarantee that no single point of failure within the loop-free routing topology10will cause a disruption in any network traffic that is concurrently transmitted (e.g., bicasting) via the two or more non-congruent paths. In particular, bicasted data packets are routed via the non-congruent paths300aand300band independent of the arc cursors18, to guarantee that even with a breakage in the network topology two non-congruent paths can be maintained.

FIG. 16Aillustrates the loop-free routing topology10comprising the routing arcs “A1”, “A2”, “A3”, “A4”, “A5”, “A6”, “A7”, and “A8”12, and the buttressing arcs “BA1”, “BA2”, and “BA3”13, prior to assignment of any routing arc to any non-congruent path: any unassigned routing arc12or buttressing arc13is illustrated inFIGS. 16A-16Cas a solid line.FIG. 16Billustrates initial formation of the non-congruent path300awithin the routing arcs “A1” and “A2” and the buttressing arc “BA2”, where each non-congruent path300ais illustrated as a dashed line;FIG. 16Balso illustrates initial formation of the non-congruent path300bwithin the routing arcs “A1”, “A2” and “A3”, where each non-congruent path300bis illustrated as a long-dashed and short-dashed line (with alternating long-dash and short-dash).FIG. 16Cillustrates the completed formation of the non-congruent paths300aand300bwithin the routing topology10.

FIGS. 14 and 16A-16Ceach illustrate a routing arc12joined with a single buttressing arc13. However, any number of buttressing arcs13may be joined with a routing arc12at the same junction node or a different junction node, enabling the formation of a comb structure comprising a single routing arc and multiple buttressing arcs joined to the routing arc.

As described in further detail below, each bicasted data packet includes a tag that specifies or identifies the direction that the data packet is to be transmitted, namely along either the non-congruent path300aor300b: if a data packet includes a tag specifying the “West/Left” path300a, the data packet is forwarded along the non-congruent path300a, whereas the bicasted copy of the data packet having the tag specifying the “East/Right” path300bwill be forwarded along the non-congruent path300b. As described below, a data packet also can be forwarded away from the non-congruent path (e.g.300a) toward the arc cursor18if the corresponding tag specifies the opposite direction (e.g.,300b). Consequently, the bicasting data packets are routed to the non-congruent paths300aand300bbased on the directions as specified by the tags, respectively.

Hence, a data packet does not need to be reversed (using fast rerouting) in response to a detected failure within a first path (e.g.,300a) of the loop-free routing topology, as the second non-congruent path (e.g.,300b) can provide the concurrently-transmitted packet between the source and destination. As described below, fast rerouting can be used in response to detected collisions either during formation of the non-congruent paths.

FIG. 17illustrates an example method of creating non-congruent paths300aand300bin the loop-free routing topology10, according to an example embodiment. Each of the disclosed operations with respect to any of the Figures can be executed by the processor circuit22of the apparatus20, or any logic encoded on a tangible computer readable storage medium, as described previously.

The processor circuit22can create non-congruent paths300aand300bwithin the loop-free routing topology10based on execution of operations302,304,306,308, and310ofFIG. 17. The processor circuit22can begin creation of the non-congruent paths based on associating each heir network node (i.e., each first hop node from the destination root node14) in operation302to one and only one non-congruent path300aor300b. For example,FIG. 16Billustrates the processor circuit22associating the heir network nodes “H1”, “H2”, and “H3” with the “West/Left” non-congruent path300a, and the heir network nodes “H4”, “H5”, and “H6” with the “East/Right” non-congruent path300b.

The processor circuit22in operation304propagates the association of each heir network node along the corresponding routing arc12toward the corresponding network node having possession of the arc cursor18in a routing arc12, or alternately toward the junction node of a buttressing arc. For example, the association of the heir network node “H2” to the non-congruent path300ais propagated up along the routing arc “A2” toward the corresponding arc cursor18, causing all network nodes that are along the routing arc “A2” in between the heir network node “H2” and the arc cursor18(e.g., network nodes “N11” and “N16”) to be associated with the non-congruent path300a. Similarly, the association of the heir network node “H5” to the non-congruent path300bis propagated up along the routing arc “A2” toward the corresponding arc cursor18, causing all network nodes that are along the routing arc “AT” in between the heir network node “H5” and the arc cursor18(e.g., network nodes “N14” and “N13”) to be associated with the non-congruent path300b. Similar associations are propagated in the routing arc “A1”. Both the routing arcs “A1” and “A2” are root arcs having their ends of the routing arcs as the first hop heir network nodes, such that all of the network nodes in the root arcs “A1” and “A2” have a direct association with one of the heir network nodes. The association of the heir network node “H6” to the non-congruent path300bis propagated in operation304up the routing arc “A3” up to the corresponding arc cursor18. The association of the heir network node “H1” to the non-congruent path300ais propagated up the entire buttressing arc “BA2”13up to and including the edge junction node “J1”16.

The processor circuit22in operation306performs implied association between the routing arcs based on selectively propagating the association along a routing arc to another higher routing arc via the network nodes that serve as edge junctions between the lower (parent) routing arc and the higher routing arc. In particular, edge junction nodes (e.g., “N11” and “N12”) of a higher routing arc (e.g., “A6”) propagate the heir node association from the parent arcs if the edge junction nodes (e.g., “N11” and “N12”) are exposed to different non-congruent paths. As illustrated inFIG. 16B, the edge junction node “N11” of the routing arc “A6” is exposed to the “West/Left” non-congruent path300aof the parent routing arc “A2”, whereas the complementary edge junction node “N12” of the routing arc “A6” is exposed to the “East/Right” non-congruent path300bof the parent routing arc “A3”. Hence, the heir node associations from the parent arcs can be propagated along the routing arc “A6” up to the corresponding arc cursor18, where the processor circuit22causes the network node “Ni F” to propagate the association to the non-congruent path300aup the routing arc “A6” to the corresponding arc cursor18, and causes the network node “N12” to propagate the association to the non-congruent path300bup the routing arc “A6” to the corresponding arc cursor18.

The selective propagation of the associations along a routing arc also includes the processor circuit22in operation308resolving any “collisions” if edge junction nodes (e.g., “N13”, “N14”) in a higher routing arc (e.g., “A5”) are joined to the same non-congruent path300bvia the at least one lower routing arc (e.g., “A2”) providing reachability to the destination network node14. The processor circuit22associates the edge junction node (e.g., “N14”) having the shorter path to an heir network node “H5” with the exposed non-congruent path300b, and associates the second edge junction (e.g., “N13”) (that is further than “N14” to any heir network node) with the other (non-exposed) non-congruent path300a, enabling the routing arc “A5” to have edge junctions “N13” and “N14” providing reachability to the non-congruent paths300aand300b, respectively.

The processor circuit22can continue in operation310the propagation of associations of the non-congruent paths300aor300bupward along the routing arcs12, resulting in the complete association of all the routing arcs inFIG. 16Cto either the non-congruent path300aor the non-congruent path300b.

Hence, the processor circuit22enables any network node in the loop-free routing topology10to utilize the non-congruent paths300aand300bin operation312for forwarding bicasting data via the non-congruent paths300aand300b. As illustrated inFIGS. 16C and 19, a network node “N20” in the buttressing arc “BA3”13can output a data packet having a tag specifying the “West/Left” path300a, causing the network nodes in the loop-free routing topology10to forward the data packet via the non-congruent path300athat includes the network nodes “J2” (via buttressing arc “BA3”), “N15” (via routing arc “A8”), “N11” (via routing arc “A6”), “H2” (via routing arc “AT”), to the root network node14. Similarly, the network node “N20” can output a bicasted copy of the data packet having a complementary tag specifying the “East/Right” path300b, causing the network nodes in the loop-free routing topology10to forward the bicasted copy via the non-congruent path300bthat includes the network nodes “N17” (via buttressing arc “BA3”), “N12” and “H6” (via routing arc “A3”), to the root network node14.FIGS. 16C and 19also illustrate bicasting by the network node “N21” along the non-congruent paths300aand300b.

Hence, the bicasting by the network nodes “N20” and “N21” via the non-congruent paths300aand300bguarantee that at least one of the bicasted data packets will reach the destination root14. If the processor circuit22determines that a particular path along one of the routing arcs encounters a failure, the processor circuit22can execute a fast reroute onto a fast reroute bicasting path in operation314, to establish an alternate non-congruent path, if needed.

Generating Non-Congruent Paths Having Minimal Latency Difference in a Loop-Free Routing Topology Having Routing Arcs

FIGS. 19-20describe operations executed by the path generator20(illustrated inFIG. 2) for determining a non-congruent path pair providing no more than a prescribed difference of latency (DoL_MAX) from a source network node (“S” ofFIGS. 20A-22E)16to the destination (omega) network device14, according to an example embodiment.

As described previously with respect toFIG. 16C, the path generator20can create non-congruent paths300aand300bin the loop-free routing topology10that enables bicasting of network traffic between a source network node and a destination network node14. The processor circuit22of the path generator20also can determine, from among multiple non-congruent paths from the source network node (“S” ofFIGS. 20A-22E) to the destination network node14at least a non-congruent path pair (e.g., L4-R2ofFIG. 20E)330providing no more than a prescribed difference of latency “DoL_MAX”, where the latency of the non-congruent “West/Left” path “L4”300a(“L_L4”) and the latency of the non-congruent “East/Right” path “R2”300b(“L_R2”) have a difference of no more than the prescribed difference of latency “DoL_MAX” (i.e., |L_L4−L_R2|≤DoL_MAX). The use of non-congruent paths having a latency difference of no more than the prescribed difference of latency “DoL_MAX” ensures reliable delivery of a jitter-sensitive stream bicasted to the destination network node14(e.g., a network device such as a router device) with minimal buffer requirements if the destination network node14needs to switch from one non-congruent path300ato another non-congruent path300b(e.g., due to a failure in the non-congruent path300a).

In particular, “Jitter” in a single data flow is the difference between the source-to-destination delays (i.e., latencies L) between consecutive data packets, measured for example as the variation in arrival time (T) along a data path A (i.e., TA) between consecutive packets (e.g., packet P(i−1) and then P(i) transmitted at the source after time Tnext) (e.g., where J(A)=TA_P(i)−TA_P(i−1)−Tnext). Jitter along a data path (e.g., J(A)) can vary typically on the order of milliseconds. Hence, a destination node receiving jitter-sensitive traffic (e.g., video) via a single data path can eliminate the effects of jitter by utilizing a large enough buffer to receive and store sequential packets (e.g., packet P(i−1) and then P(i)) over a few milliseconds, such that the sequential packets are available for rendering according to the synchronization requirements of the data stream (ideally process a data packet every Tnext interval).

Although bicasting via non-congruent paths can provide guaranteed reliability in data delivery without the necessity of a deterministic network, arbitrary selection of the non-congruent paths300aand300b(e.g., as illustrated inFIG. 16C) can result in the non-congruent paths300aand300bhaving substantially different source-to-destination transmission times (i.e., latencies LA, LB), resulting in a substantially large difference in latency between the two non-congruent paths (i.e., a “Delta of Latency” or “Difference of Latency” (DoL=|LA−LB|)). Hence, the Delta of Latency between non-congruent paths arbitrarily selected can have a value on the order of seconds (e.g., where DoL=|TA_P(i)−TB_P(i−1)−Tnext|), causing a disruption in data flow unless the destination network node14has a substantially large memory capable of storing seconds' worth of jitter-sensitive data packets. Such a substantially large memory is not practical for a network device such as a destination router in a network that provides data to one or more destination customers.

Hence, according to the example embodiments the path generator20can determine, within the loop-free routing topology10, a non-congruent path pair330(FIG. 20E) that has no more than the prescribed difference of latency “DoL_MAX” from the source network node “S”16(FIGS. 20A-22E) to the destination network node14, enabling the destination network node14to instantaneously switch between one non-congruent path (e.g., “L4”300a) and the peer non-congruent path (e.g., “R2”300b) without any interruption or jitter, without the necessity of a large buffer. Hence, the prescribed DoL_MAX can be chosen based on the memory capacity of the memory circuit26in the destination network node14relative to the memory requirements of one or more bicasted data flows, enabling the memory circuit26to simultaneously process multiple bicasted data flows with no jitter, based on the prescribed DoL_MAX set to a value on the order of milliseconds. Hence, the prescribed DoL_MAX can be set based on the memory capacity of the destination network device14, for example based on whether the destination network node14is a user computer having substantially large memory capacity in its memory circuit26, or whether the destination network node14is a network switch or a network router device having a substantially smaller memory capacity in its memory circuit26for a given bicasted data flow.

Referring toFIG. 19A, the processor circuit22of the path generator20(illustrated as a “path generator” or “path computation element” (PCE)) in operation400can create the loop-free routing topology10for reaching the destination network node14: as illustrated inFIG. 20A, the loop-free routing topology10comprises a root arc12e, and routing arcs12f,12g,12h,12i,12j,12k,12l,12m,12n, and12o; the same loop-free routing topology10comprising the routing arcs12ethrough12ois illustrated inFIGS. 20B-22E, although the reference characters for only the relevant routing arcs are illustrated to reduce cluttering in the Figures.

As illustrated inFIG. 19AandFIG. 20A, the processor circuit22of the path generator20in operation402can identify, within the loop-free routing topology10, non-congruent paths (e.g.,300a,300b) for a source node “S”16to reach the destination network node14. As illustrated inFIGS. 20A-22E, the non-congruent paths can include the “West/Left” direction paths “L1”, “L2”, “L3”, and “L4”300a, and the “East/Right” direction paths “R1” and “R2”300b; other “West/Left” direction paths300aand/or other “East/Right” direction paths300balso could be identified by the path generator20.

The processor circuit22of the path generator20in operation404is configured for determining a non-congruent path pair (e.g., “L4, R2” ofFIG. 20E)330from the available non-congruent paths, where the non-congruent path pair330provides less than the prescribed difference of latency “DoL_MAX”, described in further details with respect toFIGS. 19B and 21C. In response to determining the non-congruent path pair330, the processor circuit22of the path generator20in operation406is configured for creating instructions for the arc nodes in the loop-free routing topology10, illustrated for example inFIGS. 6I and 7(not shown inFIGS. 20A-22E): the instructions generated by the processor circuit22can be output by the network interface circuit24as instructions within the topology control messages102ofFIG. 7; hence, the instructions can cause the arc nodes in the loop-free routing topology10to deploy the non-congruent path pair330for the source network node “S”16to forward the data packet (and the bicasted copy) to the destination network node14via the non-congruent paths “L4”300aand “R2”300bof the non-congruent path pair330within the prescribed difference of latency “DoL_MAX”.

FIG. 19Billustrates one example method of determining a non-congruent path pair (e.g.,330ofFIG. 20E) executed in operation404, according to an example embodiment.FIG. 20Billustrates an example method where the processor circuit22of the path generator20can determine the non-congruent path pair330based on comparing latencies of non-congruent shortest paths in the loop-free routing topology10, and successively comparing slower paths from the faster “side” (i.e., direction) to identify a non-congruent path pair330within the prescribed difference of latency “DoL_MAX”. For example, the processor circuit22of the path generator20inFIG. 19Bcan identify in operation410a first non-congruent path (“L1”300aofFIG. 20A) having a corresponding shortest path (SPF_L) in the first direction (e.g., A=“West/Left”); the processor circuit22of the path generator20inFIG. 19Balso can identify in operation410a second non-congruent path (“R1”300bofFIG. 20A) having the corresponding shortest path (SPF_R) in the second direction (e.g., B=“East/Right”).

As illustrated inFIG. 20A, the non-congruent path “L1”300aprovides a data path (illustrated as even-spaced dashed lines) from the source network device “S”16to the destination network node14via the West/Left direction of the routing arc12mending in arc node “N30”16, the East/Right direction of the routing arc12jending in arc node “N31”16, the West/Left direction of the routing arc12kending in arc node “N32”16, the West/Left direction of the routing arc12hending in arc node “N33”16, the East/Right direction of the routing arc12fending in arc node “N34”16, and the West/Left direction of the root routing arc12eending at the destination network node14. The non-congruent path “R1”300bprovides a distinct non-congruent data path (with alternating long-dash and short-dash lines) from the source network device “S”16to the destination network node14via the East/Right direction of the routing arc12mending in arc node “N35”16, the East/Right direction of the routing arc12kending in arc node “N36”16, the West/Left direction of the routing arc12gending in arc node “N37”16, and the East/Right direction of the root routing arc12eending at the destination network device14.

Additional arc nodes16in the routing arcs12e-12mare omitted to avoid cluttering inFIGS. 20A-20E, even though each arc node12includes at least three arc nodes as described previously, namely a first network node as a first end of the routing arc, a second node as a second end of the routing arc, and a third network node in between the first and second ends and configured for routing any network traffic along the routing arc and exiting, toward the destination node14, via any one of the first or second ends of the routing arc (or both ends as appropriate, for example exiting both ends “N30” and “N35” for the routing arc12m).

In response to the processor circuit22of the path generator20identifying the shortest path in the first direction (A) (e.g., “A=L1=SPF_L”) and the shortest path in the second direction (B) (e.g., “B=R1=SPF_R”), the processor circuit22of the path generator20in operation412can determine the respective latencies (LA=L_L1; LB=L_R1) of the candidate paths (A, B) from the source node “S”16to the destination network node14. The processor circuit22of the path generator20in operation414can determine whether a determined difference of latency between the first and second latencies is no more than the prescribed difference of latency “DoL_MAX”, i.e., “|LA−LB|≤DoL_MAX”, where the expression “|LA−LB|” refers to the absolute value between the latency “LA” of the candidate path “A” and the latency “LB” of the candidate path “B”.

If in operation414the processor circuit22of the path generator20determines the determined difference of latency “|LA−LB|” is less than the prescribed difference of latency “DoL_MAX”, the processor circuit22of the path generator20in operation416can choose in operation416the candidate paths “A=L1=SPF_L” and “B=R1=SPF_R” as the non-congruent path pair providing no more than the prescribed difference of latency “DoL_MAX”, and can generate in operation406the instructions as described above for deployment of the chosen non-congruent path pair for bicasting by the source network device16to the14within the prescribed difference of latency “DoL_MAX”.

If in operation414the processor circuit22of the path generator20determines that determined difference of latency between the first and second latencies “|LA−LB|” is more than the prescribed difference of latency “DoL_MAX” (e.g., “|L_L1−L-R1|>DoL_MAX”), the processor circuit22of the path generator20in operation418can successively search for matching candidate paths based on choosing a “next-slower candidate” path from the “faster” non-congruent path side. In particular, the processor circuit22of the path generator20in operation418can determine the “faster” non-congruent path side based on determining the first latency (LA=L_L1) of the first non-congruent path in the first direction (A=L1) is less than the second latency (LB=L_R1) of the second non-congruent path in the second direction (B=R1). In response to identifying the “faster” non-congruent path side (e.g.,300a), the processor circuit22can choose a “next-slower candidate” from the “faster” non-congruent path side based on identifying a “third” non-congruent path in the first direction (A=L2) and having a “third latency” (L_L2) that is greater than the first latency (L_L1) (i.e., “L_L2>L_L1”).

As illustrated inFIG. 20B, the “next-slower” candidate “L2” from the “faster” non-congruent path side300aprovides a data path (illustrated as even-spaced dashed lines) from the source network device “S”16to the destination network node14via the West/Left direction of the routing arc12mending in arc node “N30”16, the West/Left direction of the routing arc12jending in arc node “N38, and the West/Left direction of the routing arc12fending at the destination network node14. Assume that the latencies have the relationship “L_L1<L_L2<L_R1”.

The processor circuit22of the path generator20in operation412can determine whether the corresponding determined difference of latency between the “second” latency (LB=L_R1) for the path R1(L_R1) and the “third” latency (LA=L_L2) for the path L2, illustrated inFIG. 20B, is no more than the prescribed difference of latency, e.g., “|L_L2−L_R1|≤DoL_MAX”. In response to the processor circuit22determining in operation414the corresponding determined of latency between the “second” latency “L_R1” and the “third” latency “L_R1” is more than the prescribed difference of latency “DoL_MAX”, the processor circuit22of the path generator20in operation418can successively compare the corresponding latency (e.g., L_L3) of a successively slower non-congruent path (e.g., “L3” ofFIG. 20C) in the “faster” first direction300awith the second latency “L_R1” until one of: the corresponding latency of the slower non-congruent path in the “faster” first direction (L_L3) is within the prescribed difference of latency of the second latency (L_R1), “|L_L3−L_R1|≤DoL_MAX”; or the corresponding latency of the slower non-congruent path (e.g., “L_L3”) in the “faster” first direction300ais greater than the second latency (L_R1) by at least the prescribed difference of latency, i.e., “L_L3−L_R1>DoL_MAX”, such that the “East/Right” path300bis now faster than the “West/Left” path300a.

As illustrated inFIG. 20C, the “next-slower” candidate “L3” from the non-congruent path side300aprovides a data path (illustrated as even-spaced dashed lines) from the source network device “S”16to the destination network node14via the West/Left direction of the routing arc12mending in arc node “N30”16, the West/Left direction of the routing arc12jending in arc node “N38”16, the East/Right direction of the routing arc12fending in arc node “N34”16, and the West/Left direction of the root arc12eending in the destination device14.

In response to the processor circuit22selecting the “next-slower” candidate “L3”, the processor circuit22of the path generator20in operation412can determine the respective latencies “L_L3”, “R_R1”; assume in operation operations414and418the corresponding latency of the slower non-congruent path (e.g., “L_L3”) in the “faster” first direction300ais greater than the second latency (L_R1) by at least the prescribed difference of latency, i.e., “L_L3−L_R1>DoL_MAX”; hence, the processor circuit22in response to identifying the West/Left path “L3”300ais now slower than the East/Right path “R1”300b(i.e., L_L1<L_L2<L_R1<L_L3), the processor circuit22in operation418can successively compare a corresponding latency (e.g., “L_R2”) of a successively slower non-congruent path in the second direction (e.g., “R2” ofFIG. 20D) with the corresponding latency of the slower non-congruent path in the first direction (L_L3), until one of: the corresponding latency of the slower non-congruent path in the second direction (L_R2) is within the prescribed difference of latency of the corresponding latency of the slower non-congruent path in the first direction (L_L3), “|L_L3−L_R2|≤DoL_MAX”; or the corresponding latency of the slower non-congruent path in the second direction (L_R2) is greater than the corresponding latency of the slower non-congruent path in the first direction (L_L3) by at least the prescribed difference of latency, “L_R2−L_L3>DoL_MAX”.

As illustrated inFIGS. 20D and 22E, the non-congruent path “R2”300bprovides a distinct non-congruent data path (with alternating long-dash and short-dash lines) from the source network device “S”16to the destination network node14via the East/Right direction of the routing arc12mending in arc node “N35”16, the East/Right direction of the routing arc12kending in arc node “N36”16, and the East/Right direction of the routing arc12gending in the destination network node14.

Assume with respect toFIG. 20Dthat the processor circuit22of the path generator20in operations412and414determines that the corresponding latency of the slower non-congruent path in the second direction (L_R2) is greater than the corresponding latency of the slower non-congruent path in the first direction (L_L3) by at least the prescribed difference of latency, in other words where “L_R2−L_L3>DoL_MAX” and “L_L1<L_L2<L_R1<L_L3<L_R2”, such that the path “R2”300bofFIG. 20Dis now the “slower” side relative to the non-congruent path “L3”300a. In response to the processor circuit22in operation418determining the path “R2”300bis now the slower side, and the path “L3”300ais now the faster side, the processor circuit22selects a successively slower path “L4” from the “faster” side300a, illustrated inFIG. 20E.

As illustrated inFIG. 20E, the next-slower non-congruent path “L4” from the non-congruent path side300aprovides a data path (illustrated as even-spaced dashed lines) from the source network device “S”16to the destination network node14via the West/Left direction of the routing arc12mending in arc node “N30”16, the West/Left direction of the routing arc12jending in arc node “N38”16, the East/Right direction of the routing arc12fending in arc node “N34”16, and the East/Right direction of the root arc12eending in the destination network device14.

The processor circuit22of the path generator20can determine in operation412the latency of the non-congruent path “L4”300a(L_L4), and compare with the latency of the non-congruent path “R2”300b. In response to the processor circuit22of the path generator20determining in operation414that the determined difference of latency between non-congruent path “L4”300aand the non-congruent path “R2”300bis no more than the prescribed difference of latency, i.e., “|L_L4−L_R2|≤DoL_MAX”, the processor circuit22in operation416can choose the candidate paths “L4”300aand “R2”300bas the non-congruent path pair330providing less than the prescribed difference of latency “DoL_MAX”.

Hence, the processor circuit22can generate in operation406instructions for the deployment of the non-congruent paths “L4”300aand “R2”300bin the loop-free routing topology10that enables the source network device “S”16to send bicasted traffic to the destination network node14, within the prescribed difference of latency “DoL_MAX”, via the non-congruent paths “L4”300aand “R2”300b. The network interface circuit24of the path generator20is configured for outputting the instructions into the loop-free routing topology10, for example using the topology control messages102ofFIG. 7, enabling the arc nodes16implementing the routing arcs12e,12f,12g,12j,12k, and12mto install route entries (e.g., label switched paths) that enable the source network node to forward the data packet, and the bicasted copy, to the destination node via the one first available path and the one second available path, respectively.

As described previously, each routing arc (e.g., “ARC4” ofFIGS. 6I and 7)12comprises a first network node (e.g., “C”)16as a first end of the routing arc, a second network node (e.g., “D”)16as a second end of the routing arc, and at least a third network node (e.g., “E” or “L”)16configured for routing any network traffic along the routing arc (e.g., “ARC4”) and exiting toward the destination node14via any one of the first or second ends of the routing arc. Hence, the first, second, and third network nodes of each of the routing arcs12e,12f,12g,12j,12k, and12minstall route entries for bicasting of the network traffic via the non-congruent paths “L4”300aand “R2”300b. For example, the arc nodes “N34”, “N38”, “N30” (and any arc nodes not shown along the path300ainFIG. 20E) can implement the instructions generated by the path generator20to enable the source network device “S”16to forward data packets along the path “L4”300a; the arc nodes “N36”, “N35” (and any arc nodes not shown along the path300binFIG. 20E) can implement the instructions generated by the path generator20to enable the source network device “S” to forward bicasted copies of the data packets along the path “R2”300b, resulting in the destination network device the bicasted streams via the respective paths “L4”300aand “R2”300bwithin the prescribed difference of latency “DoL_MAX”.

As illustrated above with respect toFIG. 19B, the example embodiments enable the path generator20to determine the non-congruent path pair330providing no more than the prescribed difference of latency “DoL_MAX” based on starting with the shortest non-congruent paths “L1”, “R1”, and successively testing successively slower paths on a “faster” side until the non-congruent path pair330is identified.

FIG. 19Cillustrates that the processor circuit22of the path generator20also can determine the non-congruent path pair330providing no more than the prescribed difference of latency “DoL_MAX”, based on determining in operation420, within the loop-free routing topology10, first available paths (e.g., L1, L2, L3, L4) in the first direction300afor the source network node “S”16to reach the destination node14, and second available paths (e.g., R1, R2, etc.) in the second direction for the source network node to reach the destination node; the processor circuit22can sort the available paths in the first direction300aby increasing latency (starting with the shortest-path lowest latency L1), and can further sort the available paths in the second direction300bby increasing latency (starting with the shortest-path lowest latency R1), and store the sorted available first/second direction paths as one or more data structures in the memory circuit26, for example within the state table54.

The processor circuit22of the path generator20in operation422can determine, from among the first available path300aand the second available path300b, one of the first available paths (e.g., A=L4) and one of the second available paths (e.g., B=R2) that provide no more than the prescribed difference of latency, for example staring with the lowest (or next-lowest) DoL. The processor circuit22in operation424can confirm non-congruency of the paths chosen in operation422, in other words, confirm that the two chosen paths do not have any shared or overlapping data links, and deploy in operation406the chosen paths (e.g., L4, R2) in response to confirming the chosen paths are non-congruent paths. If in operation424an overlap is detected between the two paths indicating the two paths are not non-congruent, the processor circuit22of the path generator20can select another candidate path in operation422to find a non-congruent path pair330.

According to example embodiments, non-congruent paths are established for bicasting data within a computing network having a loop-free routing topology, within a prescribed difference of latency. The non-congruent paths provide no more than the prescribed difference of latency enables a destination network device to instantaneously switch between the non-congruent paths for reliable reception and jitter-free processing of jitter-sensitive traffic, without the necessity of large buffer sizes that normally would be required if a bicasted copy of a data packet required a substantially longer arrival time (i.e., longer than the prescribed difference of latency).

While the example embodiments in the present disclosure have been described in connection with what is presently considered to be the best mode for carrying out the subject matter specified in the appended claims, it is to be understood that the example embodiments are only illustrative, and are not to restrict the subject matter specified in the appended claims.