Patent Description:
Certain networks employ link state information to route packets. In such networks, each node broadcasts the node's link state information across the network in link state messages as part of a synchronization process. A node's link state information includes data identifying the node, indicating the node's neighbors, and indicating distance and/or routing costs to contact such neighbors. Each node receives the link state messages from the other nodes, and uses the link state information to populate a link state database. Each node can then use a corresponding link state database to determine shortest paths for communicating data packets with other nodes. Such networks suffer from certain scalability problems. Specifically, each node periodically broadcasts a link state message to all other nodes in the network. As more nodes are added to the network, more link state messages are broadcast, which results in ever increasing signaling overhead that competes with data traffic for bandwidth.

<CIT> discloses that Connectivity information is received at a local node of the nodes in the network, and a processor of the local node computes a flooding topology based on the received connectivity information, where the flooding topology is represented by links between nodes in the network. The links are encoded between the local node and remote nodes and between remote nodes on the flooding topology, and a link state message is flooded to the remote nodes from the local node in the network, where the link state message includes each of the encoded links in the flooding topology.

In an embodiment, the disclosure includes a method implemented in a first node in a network. The method comprises receiving, at a receiver of the first node, data indicating connectivity of a plurality of nodes in the network including the first node. The method further comprises building, by a processor of the first node, a flooding topology based on the connectivity. The flooding topology is built by selecting one of the nodes as a root node, and building a tree of links connecting the root node to the nodes in the network. The flooding topology is stored in a memory without transmitting the flooding topology to the plurality of nodes in the network. The method further comprises flooding, by a transmitter of the first node, link state messages over the flooding topology. Employing a flooding topology allows list state messages to reach all nodes in the network without requiring the link state messages be flooded over all links. This reduces redundant link state message traffic, and hence reduces network traffic congestion. Such reduction also provides for increased network scalability as the flooding topology reduces network traffic congestion in a manner that is proportional to the number of network nodes. Also, allowing each node to separately calculate the flooding topology without transmitting the flooding topology over the network further reduces network traffic congestion.

The method further comprising receiving, at the receiver, a request specifying a number of leaf links to add to the tree, and adding to the flooding topology, by the processor, the number of leaf links between the nodes in the network. Adding leaf links to the flooding topology adds redundancy, but also stability. Additional leaf links reduce the number of potential sources of equipment failure that could sever the flooding topology.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein, prior to adding leaf links, the tree of links in the flooding topology contains a minimum number of links to connect all of the nodes in the network to the root node.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, further comprising establishing, by the processor, an adjacency with a newly connected node. The newly connected node is directly connected to the first node via a link. The method further comprises adding, by the processor, the newly connected node to the tree of links in the flooding topology until the flooding topology is recomputed. This allows new nodes to be added to the flooding topology without requiring that the flooding topology be immediately recomputed by the entire network.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, further comprising receiving, at the receiver, a first link state message across a link that is excluded from the flooding topology; and
flooding, by the transmitter, the first link state message across links on the flooding topology. This allows link state messages received from outside the flooding topology to be forwarded across the network without flooding across all interfaces. This may be used to allow for backwards compatibility with devices that are not capable of employing a flooding topology.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, further comprising:
receiving, at the receiver, a second link state message indicating a second node in the network is down; and flooding, by the transmitter, the second link state message to links that connect between the first node and neighbors of the second node. This allows for communication around a malfunctioning node while maintaining the flooding topology for portions of the network that are not directly connected to the malfunction.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, further comprising receiving, at the receiver, a third link state message indicating a first link in the network is down. The method further comprises determining that the first link is a critical element. The method further comprises based on the determination, sending the third link state message to links that connect to neighbors which also connect nodes adjacent to a node attached to the first link. This allows for communication around a malfunctioning link while maintaining the flooding topology for portions of the network that are not directly connected to the malfunction.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, further comprising: determining, by the processor, critical elements, wherein a critical element is a link or node whose failure splits the flooding topology; and discontinuing use of the flooding topology when a critical interface fails. Failure of a critical element breaks the flooding topology into multiple topologies. Hence, failure of a critical element may prevent link state messages over the flooding topology from reaching all nodes in the network. Maintaining awareness of this potential problem allows the network to revert to general flooding until another flooding topology can be generated that omits the critical interface.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages are Open Shortest Path First (OSPF) Link State Advertisements (LSAs).

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages are Intermediate System to Intermediate System (IS-IS) Link State Protocol data units (LSPs).

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain Flooding reduction (F) flags set to indicate the nodes in the network that support link state flooding reduction via the flooding topology. The F flags allows for backwards compatibility.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain a mode field set to indicate centralized link state flooding reduction, distributed link state flooding reduction, or statically configured link state flooding reduction.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain an algorithm field set to indicate an algorithm to build the tree of links in the flooding topology.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain an operation (OP) field set to switch to link state flooding reduction from full network flooding.

In an embodiment, the disclosure includes a first node in a network. The first node comprises a receiver configured to receive data indicating connectivity of a plurality of nodes in the network including the first node. The first node also comprises a processor coupled to the receiver. The processor is configured to build a flooding topology based on the connectivity. This occurs by selecting one of the nodes as a root node, and building a tree of links connecting the root node to the nodes in the network. The first node also comprises a memory coupled to the processor, the memory configured to store the flooding topology. The first node also comprises a transmitter coupled to the processor, the transmitter configured to flood link state messages over the flooding topology without transmitting the flooding topology to the remaining nodes in the network. Employing a flooding topology allows list state messages to reach all nodes in the network without requiring the link state messages be flooded over all links. This reduces redundant link state message traffic, and hence reduces network traffic congestion. Such reduction also provides for increased network scalability as the flooding topology reduces network traffic congestion in a manner that is proportional to the number of network nodes. Also, allowing each node to separately calculate the flooding topology without transmitting the flooding topology over the network further reduces network traffic congestion.

The receiver is further configured to receive a request specifying a number of leaf links to add to the tree, and wherein the processor is further configured to add to the flooding topology the number of leaf links between the nodes in the network. Adding leaf links to the flooding topology adds redundancy, but also stability. Additional leaf links reduce the number of potential sources of equipment failure that could sever the flooding topology.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the processor is further configured to establish an adjacency with a newly connected node, wherein the newly connected node is directly connected to the first node via a link, and wherein the processor is further configured to add the newly connected node to the tree of links in the flooding topology until the flooding topology is recomputed. This allows new nodes to be added to the flooding topology without requiring that the flooding topology be immediately recomputed by the entire network. Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the receiver is further configured to receive a first link state message across a link that is excluded from the flooding topology, and wherein the transmitter is further configured to flood the first link state message across links on the flooding topology. This allows link state messages received from outside the flooding topology to be forwarded across the network without flooding across all interfaces. This may be used to allow for backwards compatibility with devices that are not capable of employing a flooding topology.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the receiver is further configured to receive a second link state message indicating a second node in the network is down, and wherein the transmitter is further configured to flood the second link state message to links that connect between the first node and neighbors of the second node. This allows for communication around a malfunctioning node while maintaining the flooding topology for portions of the network that are not directly connected to the malfunction.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the receiver is further configured to receive a third link state message indicating a first link in the network is down, wherein the processor is further configured to determine that the first link is a critical element, and wherein the transmitter is further configured to, based on the determination, send the third link state message to links that connect to neighbors which also connect to nodes adjacent to a node attached to the first link. This allows for communication around a malfunctioning link while maintaining the flooding topology for portions of the network that are not directly connected to the malfunction.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the processor is further configured to determine critical elements, wherein a critical element is a link or node whose failure splits the flooding topology; and discontinue use of the flooding topology when a critical element fails. Failure of a critical element breaks the flooding topology into multiple topologies. Hence, failure of a critical element may prevent link state messages over the flooding topology from reaching all nodes in the network. Maintaining awareness of this potential problem allows the network to revert to general flooding until another flooding topology can be generated that omits the critical interface.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain an algorithm field set to indicate an algorithm to build the tree of links in the flooding topology. Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the link state messages contain an operation (OP) field set to switch to link state flooding reduction from full network flooding.

In an embodiment, the disclosure includes a non-transitory computer readable medium comprising a computer program product for use by a first node in a network, the computer program product comprising computer executable instructions stored on the non-transitory computer readable medium such that when executed by a processor cause the first node to perform any of the preceding aspects.

In an embodiment, the disclosure includes a first node in a network. The first node comprises a receiving means for receiving data indicating connectivity of a plurality of nodes in the network including the first node. The first node also comprises a processing means for build a flooding topology based on the connectivity. This occurs by selecting one of the nodes as a root node, and building a tree of links connecting the root node to the nodes in the network. The first node also comprises a memory storage means for storing the flooding topology. The first node also comprises a transmitting means for flooding link state messages over the flooding topology without transmitting the flooding topology to the remaining nodes in the network.

Optionally, in any of the preceding aspects, another implementation of the aspect includes, wherein the receiving means, processing means, memory storage means, and transmitting means are configured to perform any of the preceding aspects.

The disclosure should in no way be limited to the illustrative implementations, drawings, and techniques illustrated below, including the exemplary designs and implementations illustrated and described herein, but may be modified within the scope of the appended claims.

Disclosed herein are various mechanisms to reduce signaling overhead related to link state messages in IGP networks, such as OSPF and/or IS-IS networks. Communicating link state messages from a node to all other nodes in a network domain is referred to as flooding. The disclosed mechanisms, referred to collectively as LSFR, reduce the impact of link state message flooding by generating a flooding topology that is a subset of the real network topology. In general, each node floods the network by transmitting link state messages over the flooding topology without transmitting such messages across network links that are excluded from the flooding topology. This allows the message to reach all other nodes in the network, while minimizing the number of redundant copies of the message received at each node. For example, the flooding topology may be generated as a tree of links (e.g., a spanning tree) that connects the nodes. Such a tree of links allows a link state message to be flooded to all nodes while ensuring each node receives a single copy of the flooded message. For increased reliability, leaves may be added to the tree of links as directed by a network administrator. This adds back some message redundancy, but increases network reliability by providing alternate message path(s) across the flooding topology in the event a link or node malfunctions. In distributed mode, each node determines the flooding tree by employing a common algorithm, which may be selected by the administrator. This allows each node to maintain a copy of the flooding topology without flooding a copy of the flooding topology over the network, which would increase network congestion. A Flooding reduction (F) flag is also disclosed. The F flag allows each node to communicate LSFR support, and hence allows nodes to employ the flooding topology while maintaining backwards compatibility with nodes that do not support LSFR. The F flag also allows non-LSFR nodes to be connected farther away from the root of the flooding topology tree. Also disclosed are mechanisms to manage link state message flooding in the event of network changes. For example, when a new node enters the network and communicates with a neighbor node already on the flooding topology, the neighbor node may add the new node to the flooding topology until a recalculation of the flooding topology occurs, and a new flooding topology is built. Further, when a link or node malfunctions, a node adjacent to the malfunction can communicate link state messages to other nodes that are adjacent to the malfunction via links that are excluded from the flooding topology to ensure such nodes continue to receive link state messages until the malfunction is addressed. In addition, the nodes may each retain knowledge of critical elements. A critical element is a flooding topology link/interface or node that, upon failure, splits the flooding topology into two or more disjoint parts. Upon notification of the failure of a critical element, the nodes may revert to flooding link state messages over all links in order to maintain network functionality until the link/node is repaired or until a new flooding topology can be computed that does not include the failed element. When a critical element is a flooding topology link (or interface), the critical element is called a critical interface or a critical link. When a critical element is a flooding topology node, the critical element is called a critical node.

<FIG> is a schematic diagram of an example IGP network <NUM>. An IGP network <NUM> is a network configured to exchange routing and/or switching information based on an IGP protocol, such as OSPF and/or IS-IS. The IGP network <NUM> includes a plurality of nodes <NUM> interconnected by links <NUM>. A node <NUM> is a network device capable of receiving a data packet from a source on a first interface, determining a destination of the data packet can be reached via a second interface, and forwarding the data packet toward the destination via the second interface. For clarity of discussion, the term data packet as used herein includes both data packets and data frames. A link <NUM> is a medium capable of propagating a signal from an interface of a first node <NUM> to an interface of a second node <NUM>.

The nodes <NUM> are interconnected to form a network domain <NUM>. As used herein, a network domain <NUM> is a group of interconnected nodes <NUM> that share network addressing schemes, policies, and/or protocols. Specifically, the nodes <NUM> of network domain <NUM> employ a link state routing protocol. When employing a link state routing protocol, each node <NUM> in the network domain <NUM> maintains a complete network topology (e.g., a routing table) and independently determines next hops for data packets by employing locally stored information related to the network topology. The network topology includes data indicating the structure of the IGP network <NUM>, such as node <NUM> and link <NUM> connections, node <NUM> adjacencies, node <NUM> interface information, and/or other link <NUM>/node <NUM> relationship information.

The nodes <NUM> share link state information across the network domain <NUM>. Link state information for a node <NUM> includes data identifying the node <NUM> (e.g., the node's <NUM> address), a list of the node's <NUM> neighbors, and costs/delays between the node <NUM> and the node's <NUM> neighbors. Nodes <NUM> are neighbors when separated by a single link <NUM>. In order to share link state information, the node's <NUM> flood link state messages across the network domain <NUM>. In OSPF, the link state messages are known as link state advertisements (LSAs). In IS-IS, the link state messages are known as link state protocol data units (LSPs). In some examples, each node <NUM> floods link state messages on all interfaces. As used herein, flooding indicates simultaneous transmission of a packet/frame on a predefined set of network interfaces. Such an approach may create problems as the size of the IGP network <NUM> increases. For example, when each node <NUM> periodically sends a link state message to all other nodes <NUM> via all interfaces, network traffic related to link state data may increase drastically as more nodes <NUM> are added to the IGP network <NUM>. Further, each node <NUM> may receive a link state message for each other node <NUM> on all interfaces. This may result in each node <NUM> receiving multiple redundant link state messages.

The present disclosure modifies the protocols employed by the nodes <NUM> in the network domain <NUM> in order to reduce redundant link state messages. The process of reducing redundant link state message communication is referred to herein as list state flood reduction (LSFR). Specifically, the nodes <NUM> are modified to generate and maintain a flooding topology that is a subset of the IGP network <NUM> topology. Link state messages are flooded over the flooding topology instead of over the entire IGP network <NUM> topology. This approach reduces the communication of redundant link state messages, which increases the scalability of the IGP network <NUM>. Further, reducing link state message traffic reduces overall network maintenance signaling, and hence increases the communication capacity of the nodes <NUM> for data traffic. <FIG> is a schematic diagram of an example IGP network <NUM> with a flooding topology <NUM> to support distributed LSFR. For example, IGP network <NUM> may be employed to implement LSFR on an IGP network <NUM>. The IGP network <NUM> includes nodes <NUM>, a root node <NUM>, and a first node <NUM>, which may be substantially similar to nodes <NUM> in IGP network <NUM>. A root node <NUM> is a node <NUM> selected as a root for a spanning tree employed as a flooding topology <NUM>. A first node <NUM> is a node <NUM>, and is differentiated in order to support clarity of discussion when describing the LSFR scheme discussed herein. The IGP network <NUM> includes flooding topology links <NUM> and links <NUM>, which are substantially similar to links <NUM>. The flooding topology links <NUM>, depicted in bold, are links included in the flooding topology <NUM>, and are hence employed to transmit link state messages. The links <NUM>, depicted without bold, are not included in the flooding topology <NUM>, and only conduct link state messages in certain particular cases as discussed with respect to the FIGS below.

IGP network <NUM> may operate in a distributed mode. In distributed mode, each node <NUM>, <NUM>, and <NUM> generates a flooding topology <NUM> after a change in the network is detected. The flooding topology <NUM> is a tree of flooding topology links <NUM> employed to transmit link state messages. The nodes <NUM>, <NUM>, and <NUM> employ the same algorithm for generating the flooding topology <NUM>. Accordingly, each node <NUM>, <NUM>, and <NUM> stores the flooding topology <NUM> in local memory without transmitting the flooding data indicating the flooding topology <NUM> to the remaining nodes in the IGP network <NUM>. In this fashion, data indicating the flooding topology <NUM> is not sent to all nodes <NUM>. The flooding topology <NUM> can be generated according to several algorithms as discussed with respect to the FIGS.

Each node <NUM>, <NUM>, and <NUM> can generate a flooding topology <NUM> after receiving data indicating the connectivity of the nodes <NUM>, <NUM>, and/or <NUM> in the IGP network <NUM> at each node <NUM>, <NUM>, and <NUM>. Receiving/sending data may occur over a pre-existing flooding topology <NUM> and/or via general flooding if no pre-existing flooding topology <NUM> exists. Each node <NUM>, <NUM>, and <NUM> can build a copy of the flooding topology <NUM> by employing a selected algorithm. For example, one of the nodes of the IGP network <NUM> is selected as a root node <NUM>. A root node <NUM> can be selected from the nodes <NUM>/<NUM> by many mechanisms. For example, the root node <NUM> may be selected from the nodes <NUM>/<NUM> as the node with the largest or smallest identifier (ID), internet protocol (IP) address, media access control (MAC) address, etc. Once the root node <NUM> is selected, a tree of flooding topology links <NUM> is built so that the tree of flooding topology links <NUM> connect the root node <NUM> to the nodes in the network. For example, the flooding topology <NUM> may be built as a spanning tree and/or a minimum weight spanning tree. A spanning tree is a subset of a graph, where all vertices (nodes <NUM>, <NUM>, and <NUM>) are connected via a minimum number of edges (links <NUM>). A minimum weight spanning tree is a subset of a graph, where all vertices (nodes <NUM>, <NUM>, and <NUM>) are connected via minimum edge weight (e.g., link cost in term of latency). A flooding topology <NUM> tree with a root node <NUM> may be computed in O(N), where O(N) is big O notation indicating a linear computation time based on input (e.g., number of nodes).

A flooding topology <NUM> is a sub-network topology of the IGP network <NUM> topology that meets several criteria. First, the flooding topology <NUM> provides equivalent reachability to all the nodes in the sub-network as in the real network (e.g., IGP network <NUM>). Second, when n (n><NUM>) links <NUM> fail, reachability to all the nodes (e.g., nodes <NUM>, <NUM>, and <NUM>) in the sub-network should be the same as in the real network. Third, when m (m><NUM>) nodes fail, reachability to all the live nodes in the sub-network should be the same as in the real network. Fourth, the number of flooding topology links <NUM> in the flooding topology <NUM> should be minimized in order to reduce list state flooding.

Once the flooding topology <NUM> is generated, the nodes <NUM>, <NUM>, and <NUM> can flood link state messages, such as OSPF LSAs and/or IS-IS LSPs, over the flooding topology <NUM>. The flooding topology <NUM> is designed to interact with the IGP network <NUM> by employing several criteria when flooding link state messages. For example, the link state messages use both the flooding topology <NUM> and the real IGP network <NUM> topology. Further, the flooding topology <NUM> and associated flooding mechanisms should support flooding link state messages (e.g., link state message <NUM>) to every node <NUM>, <NUM>, and/or <NUM> in the IGP network <NUM> in many cases, which are discussed in greater detail with respect to the FIGS below. For example, the flooding mechanisms should allow link state messages to reach all nodes node <NUM>, <NUM>, and/or <NUM> when n (n > <NUM>) nodes are down (e.g., node failure). As another example, the flooding mechanisms should allow link state messages to reach all nodes <NUM>, <NUM>, and/or <NUM> when m (m > <NUM>) links are down (e.g., link/interface failure). The flooding mechanisms should meet such criteria while reducing (e.g., almost minimizing) link state message flooding. Also, the flooding mechanisms should be backward compatible to operate with a flooding topology <NUM> comprising nodes <NUM>, <NUM>, and/or <NUM> that support LSFR and nodes that are not capable of LSFR. Compatibility is discussed in more detail with respect to the FIGS below. Generally, incapable nodes are positioned on the flooding topology <NUM>, but far away from the root node <NUM>. The incapable nodes can then receive link state messages from the flooding topology <NUM> and flood them over all interfaces.

For purposes of illustration, a link state message flooding mechanism over the flooding topology <NUM> is discussed from the perspective of the first node <NUM>. As used herein, the term first node <NUM> denotes an arbitrarily selected node <NUM> from the IGP network <NUM> for clarity of discussion. A first node <NUM> can receive a link state message <NUM>, for example from the root node <NUM> over one or more links <NUM>. The link state message <NUM> may be an LSA, an LSP, or other packet/frame carrying link state information. The link state message <NUM> may contain connectivity data, such as source node <NUM>/<NUM> ID, node <NUM>/<NUM> adjacency, link <NUM>/<NUM> IDs, interface information (e.g., port data), and/or link/node status information, such as link <NUM>/<NUM> cost (e.g., latency).

The first node <NUM> receives the link state message <NUM> over a flooding topology link <NUM>. The first node <NUM> parses and stores data from the link state message <NUM> when such information is newer than locally stored data. The first node <NUM> then forwards the link state message <NUM> over the flooding topology links <NUM> of the flooding topology <NUM> toward neighbor nodes <NUM>. The link state message <NUM> is not flooded back across the interface from which the link state message <NUM> was received (e.g., back toward the root node <NUM>). As shown, the link state message <NUM> is generally not flooded across links <NUM> that are outside of the flooding topology <NUM> absent particular cases as discussed in more detail with respect to the FIGS below. Hence, the link state flooding is accomplished according to the flooding topology <NUM>. As the flooding topology <NUM> connects all nodes <NUM>, <NUM>, and <NUM>, each node in the IGP network <NUM> receives a copy of the link state message <NUM> and updates local link state information (e.g., in a routing table). However, because the link state message <NUM> is generally not flooded across links <NUM>, the nodes <NUM>, <NUM>, and <NUM> generally do not receive redundant copies of the link state message <NUM>. As such, link state message <NUM> flooding is reduced such that each node <NUM>, <NUM>, and <NUM> receives a single copy of the link state message <NUM> instead of a copy on each interface.

Generally limiting link state message <NUM> flooding to the flooding topology <NUM> results in several advantages. For example, the flooding mechanisms discussed herein reduce overall network traffic, and hence enhance network performance. Further, the flooding mechanisms discussed herein improve network convergence, as the flooding topology <NUM> is calculated at each node in distributed mode. Also, the flooding mechanisms discussed herein may reduce configuration requirements when compared to other link state flooding mechanisms.

It should be noted that some redundancy may be designed into the IGP network <NUM> to protect against equipment failure. Specifically, extra links <NUM> may be added to the flooding topology <NUM> in order to mitigate potential IGP network <NUM> communication problems. In such a case, some nodes <NUM>, <NUM>, <NUM> may receive more than one link state message <NUM>. Accordingly, LSFR may be balanced with more reliability based on redundant link state messages. A mechanism for increasing flooding topology <NUM> reliability is discussed below.

<FIG> is a schematic diagram of an example IGP network <NUM> with a flooding topology <NUM> employing a leaf link <NUM>, which may be employed to increase network reliability. The IGP network <NUM> is substantially similar to IGP network <NUM>, but contains an extra leaf link <NUM> in the flooding topology <NUM>. As such, the IGP network <NUM> contains a root node <NUM>, nodes <NUM>, links <NUM>, and a flooding topology <NUM> containing flooding topology links <NUM>, which are substantially similar to root node <NUM>, nodes <NUM>/<NUM>, links <NUM>, flooding topology <NUM>, and flooding topology links <NUM>, respectively. A leaf link <NUM> is a link added to the flooding topology <NUM> to support IGP network <NUM> reliability. The leaf link <NUM> is shown as a dashed bold line. With leaf link <NUM> added to the flooding topology <NUM> (e.g., creating a circle), some of the links <NUM>/<NUM> to nodes <NUM>/<NUM> could malfunction without causing other nodes <NUM>/<NUM> to be separated from the tree of flooding topology links <NUM>. However, adding leaf link <NUM> may cause one of the leaf link's <NUM> end point node's <NUM>/<NUM> to receive a redundant link state message. As such, the reliability of the IGP network <NUM> is increased at the cost of slightly increased signal overhead.

Adding a leaf link <NUM> may occur during the process of building the flooding topology <NUM>. For example, a system administrator can select a number of leaf links <NUM> to add to the flooding topology <NUM>. Such a selection can be transmitted to all the nodes <NUM>/<NUM> in the IGP network <NUM>. Accordingly, each node <NUM>/<NUM> receives the request, which specifies the number of leaf links <NUM> to add to the tree of flooding topology links <NUM> in the flooding topology <NUM>. Each node <NUM>/<NUM> can build the flooding topology <NUM> based on the connectivity information as discussed above. Prior to adding the leaf links <NUM>, the tree of links <NUM> in the flooding topology <NUM> may contain a minimum number of links to connect all of the nodes <NUM> in the IGP network <NUM> to the root node <NUM>. After generating the flooding topology <NUM>, the nodes <NUM>/<NUM> add to the flooding topology <NUM> a number of leaf links <NUM> (k>=<NUM>) as specified in the request from the system administrator. The leaf link(s) <NUM> are added between the nodes <NUM>/<NUM> in the IGP network <NUM> to increase reliability. Leaf links <NUM> can be placed based on several mechanisms. For example, any flooding topology link <NUM> or node <NUM>/<NUM> that would split the flooding topology <NUM> into multiple trees/parts upon failure can be designated as a critical element. The leaf links <NUM> may be placed in positions selected in order to minimize the number of critical elements in the IGP network <NUM>. Additional leaf link <NUM> placement mechanisms are discussed below.

For example, flooding topology <NUM>, designated Ft, may be built by one of the mechanisms described with respect to <FIG>. In such a case, the flooding topology <NUM> may take the shape of a tree. An integer number of leaf links <NUM> (k>=<NUM>) can then be added to the tree to create an enhanced flooding topology <NUM> with increased connectivity. For example, there may be m (m > <NUM>) links <NUM> directly connected to a node X on the flooding topology <NUM>. A number k of leaf links <NUM> can be selected, where k <= m, for example by using a deterministic algorithm or rule. One algorithm or rule may include selecting k leaf links <NUM> that have the smallest or largest IDs of the links <NUM> not currently connected to the flooding topology <NUM>. (e.g., the IDs of these k link's non-leaf ends are smaller/bigger than the IDs of the other links directly connected to the node X). Every node may have a unique ID. Hence, selecting k leaf links with smaller or larger IDs of these links' non-leaf ends is deterministic. As a specific example, if k = <NUM> under this algorithm, the leaf link <NUM> selected has the smallest/largest ID among the IDs of all the links' non-leaf ends directly connected to node X.

In another example mechanism, a first node L may be directly connected to a second node N in the flooding topology <NUM> Ft. A connection/adjacency to a third node can be selected from the first node L as a leaf link <NUM> in Ft by using a deterministic algorithm or rule. For example, a first node L may be directly connected to third nodes Ni (i = <NUM>,<NUM>,. ,s) in the flooding topology <NUM> Ft via adjacencies. Further, the third nodes Ni are not the second node N, IDi is the ID of third nodes Ni, and Hi (i = <NUM>,<NUM>,. ,s) is the number of hops from the first node L to the third nodes Ni in the flooding topology <NUM> Ft. One algorithm or rule is to select the connection to third node Nj (<NUM> <= j <= s) as a leaf link <NUM> such that Hj is the largest among H1, H2,. If there is another third node Na ( <NUM> <= a <= s) and Hj = Ha, then select the third node with the smaller (or larger) node ID. Specifically, if Hj is equal to Ha and IDj < IDa, then select the connection to the third node Nj by selecting the link with smaller ID (or if Hj == Ha and IDj < IDa then select the connection to Na for selecting the one with larger node ID).

For purposes of illustration, the number of connections in total between nodes L selected and the nodes in the flooding topology <NUM> Ft to be added as leaf links <NUM> can be denoted as NLc. The number of leaf links <NUM> NLc can be limited programmatically. In one example, NLc is configured to a specified number such as ten, which indicates that at most ten connections between a leaf node L and nodes in the flooding topology <NUM> Ft can be selected and added to the flooding topology <NUM> Ft to generate an enhanced flooding topology <NUM> Ft. In another example, NLc is configured to a specified percentage of the number of nodes <NUM>/<NUM> in the network (e.g., five percent), which indicates that the number of connections between the leaf nodes and nodes in Ft to be selected and added into Ft is at most five percent of the number of nodes <NUM>/<NUM> in the IGP network <NUM>. For example, for a network with one thousand nodes <NUM>/<NUM>, five percent of one thousand is fifty. Thus at most fifty leaf links <NUM> between leaf nodes L and nodes in the flooding topology <NUM> Ft are selected and added into the flooding topology <NUM> Ft.

<FIG> is a schematic diagram of an example network node <NUM> for operation in an IGP network, such as a node in IGP network <NUM>, <NUM>, and/or <NUM>. For example, network node <NUM> can be employed to implement nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Further, network node <NUM> may be employed to compute a network topology <NUM> and/or <NUM>. Network node <NUM> may also receive, process, and forward link state messages, such as LSAs or LSPs (e.g., link state messages <NUM>), over such flooding topologies to implement LSFR. Hence, the network node <NUM> is suitable for implementing the disclosed examples/embodiments as described herein. The network node <NUM> comprises downstream ports <NUM>, upstream ports <NUM>, and/or transceiver units (Tx/Rx) <NUM>, including transmitters and/or receivers for communicating data upstream and/or downstream over a network. The network node <NUM> also includes a processor <NUM> including a logic unit and/or central processing unit (CPU) to process the data and a memory <NUM> for storing the data. The network node <NUM> may also comprise optical-to-electrical (OE) components, electrical-to-optical (EO) components, and/or wireless communication components coupled to the upstream ports <NUM> and/or downstream ports <NUM> for communication of data via optical or wireless communication networks. The network node <NUM> may also include input and/or output (I/O) devices for communicating data to and from a user in some cases.

The processor <NUM> is implemented by hardware and software. The processor <NUM> may be implemented as one or more CPU chips, cores (e.g., as a multi-core processor), field-programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and digital signal processors (DSPs). The processor <NUM> is in communication with the downstream ports <NUM>, Tx/Rx <NUM>, upstream ports <NUM>, and memory <NUM>. The processor <NUM> comprises a LSFR module <NUM>. The LSFR module <NUM> implements the disclosed embodiments described herein. Specifically, the LSFR module <NUM> may build a flooding topology based on connectivity information. The LSFR module <NUM> may build the flooding topology by employing several mechanisms, such as by methods <NUM>, <NUM>, and/or <NUM> as discussed below. The LSFR module <NUM> may also add a number of leaf links to the flooding topology as directed by a user/system administrator. The LSFR module <NUM> may store the flooding topology in memory <NUM>. The LSFR module <NUM> may then receive and/or flood link state messages, such as OSPF LSAs and/or IS-IS LSPs, over an IGP network via the flooding topology by employing the downstream ports <NUM>, Tx/Rx <NUM>, and/or upstream ports <NUM>. The LSFR module <NUM> may also employ case specific handling of link state messages as discussed with respect to the FIGS. For example, the LSFR module <NUM> may add new nodes to the flooding topology upon startup as well as forward link state messages outside of the flooding topology in case of link/node failures. The LSFR module <NUM> may also maintain awareness of critical elements, and revert to general flooding of link state messages in the event of a critical element failure. These and other mechanisms implemented by LSFR module <NUM> are discussed in more detail with respect to the FIGS. Further, LSFR module <NUM> effects a transformation of the network node <NUM> to a different state. Alternatively, the LSFR module <NUM> can be implemented as instructions stored in the memory <NUM> and executed by the processor <NUM> (e.g., as a computer program product stored on a non-transitory medium).

The memory <NUM> comprises one or more memory types such as disks, tape drives, solid-state drives, read only memory (ROM), random access memory (RAM), flash memory, ternary content-addressable memory (TCAM), static random-access memory (SRAM), etc. The memory <NUM> may be used as an over-flow data storage device, to store programs when such programs are selected for execution, and to store instructions and data that are read during program execution. <FIG>, <FIG>, and <FIG> depict example methods of building a flooding topology. Generally, building a flooding topology includes <NUM>) selecting a node R according to a rule, such as the node with the biggest/smallest node ID; <NUM>) building a tree using R as the root of the tree; and <NUM>) connecting k (k>=<NUM>) leaves to the tree as desired to add equipment failure mitigation to the flooding topology. In distributed mode, each of the nodes in the network uses the algorithm to generate a flooding topology, and thus the flooding topology is not distributed/flooded in the IGP network. Two example types of mechanisms are discussed below. One type of mechanism builds a tree for the flooding topology without checking whether the nodes support LSFR. Such a mechanism assumes that all the routers in the domain support LSFR. A second type of mechanism considers whether each node supports LSFR while building a tree for the flooding topology. Such mechanisms place nodes that support LSFR closer to the root node in order to allow the nodes that support LSFR to be continuously connected to the flooding topology. Support for LSFR can be signaled in a F flag, which can be included in an IS-IS router capability type length value (TLV) and/or an OSPF LSA. For example, the F flag can be set to one to indicate the node/router supports LSFR and set to zero to indicate that the node/router does not support LSFR. The root node can then be selected according to a corresponding rule, for example as the node with the biggest/smallest node ID that also supports LSFR (e.g., among the nodes with an F flag set to one).

<FIG> is a flowchart of an example method <NUM> of building a flooding topology, such as flooding topology <NUM> and/or <NUM>. Accordingly, method <NUM> may be employed by a node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Method <NUM> is a mechanism for building a tree from a root node R with a candidate queue (Cq) initially containing node R and initially an empty flooding topology Ft.

At block <NUM>, flooding topology generation is initiated. For example, flooding topology can be recalculated when there are changes in the network. As another example, a flooding topology can be recalculated upon the occurrence of an event. Specifically, a flooding topology can be recalculated upon failure of a critical element. As another example, a flooding topology can be recalculated upon receiving a message from a user/system administrator requesting a recalculation. As noted above, in distributed mode, method <NUM> is substantially simultaneously initiated on each node in the network that is LSFR capable.

At block <NUM>, a root node for the flooding topology is selected, for example based on ID number. The selected root node is added to an empty candidate queue. Further, a flooding topology may be initialized as empty at block <NUM>. The method <NUM> then proceeds to block <NUM>, which forms an iterative loop with blocks <NUM>, <NUM>, and <NUM>.

Block <NUM> varies depending on whether the method <NUM> considers which nodes support LSFR. If the method <NUM> does not consider which nodes support LSFR, block <NUM> removes the first node from the candidate queue and adds the removed node to the flooding topology. If the removed node is not the root node, (e.g., the flooding topology is not empty prior to addition of the removed node), a link between the removed node and the last node added to the flooding topology is also included in the flooding topology. As such, block <NUM> iterates through the candidate queue in order from the root node and positions nodes on the flooding topology.

If method <NUM> does consider which nodes support LSFR, block <NUM> removes the first node from the candidate queue that also supports LSFR. When no nodes in the candidate queue support LSFR, the first node in the candidate queue (that doesn't support LSFR) is removed from the candidate queue. The removed node, and a corresponding link to the previous node in the flooding topology if applicable, is then added to the flooding topology. In this manner, block <NUM> can position nodes that support LSFR in positions on the flooding topology that are closer to the root node. This results in positioning nodes that do not support LSFR farther away from the root node, and hence reduces reliance on such nodes for communicating link state data across the flooding topology.

At block <NUM>, the list of nodes in the network is compared to the list of nodes on the flooding topology. When all nodes have been added to the flooding topology, the method <NUM> proceeds to block <NUM> and returns a completed flooding topology FT. When at least one node is not included in the flooding topology FT, the method <NUM> proceeds to block <NUM>. Block <NUM> varies depending on whether the method <NUM> considers which nodes support LSFR. If the method <NUM> does not consider which nodes support LSFR, block <NUM> determines a list of nodes Xi (i= <NUM>,<NUM>,<NUM>,. n) connected to the last node added to the flooding topology, where such nodes are not already in the flooding topology. Such nodes Xi may then be sorted by link cost and/or link/node/interface ID. Link cost may indicate latency, link length, or link maximum bandwidth, and/or other link capabilities. Further, link cost may indicate a cost between the last node added to the flooding topology and a corresponding node Xi. Such an approach may be employed to position nodes Xi with lower cost links higher in the candidate queue. Hence, such lower cost links are more likely to be added closer to the root node and be more heavily utilized in the flooding topology. When cost is identical, link/node/interface ID can be employed to determine order. If the method <NUM> does consider which nodes support LSFR, block <NUM> may consider LSFR support when determining cost. For example, real metrics can be employed to determine costs for nodes that support LSFR. Further, the real metrics for node(s) that do not support LSFR can be scaled by a factor such that the lowest cost non-LSFR metrics are higher than the highest cost LSFR metrics. By employing costs in this fashion, nodes that do not support LSFR are positioned at the end of the candidate queue. This further supports placing nodes that do not support LSFR as far away from the root node as possible.

At block <NUM>, the nodes Xi from block <NUM> are added to the end of the candidate queue in order as sorted in block <NUM>. The method <NUM> may then return to block <NUM> to add the next node from the candidate queue onto the flooding topology. By employing the abovementioned approach, the flooding topology grows as a balanced tree starting at the root node. The root node is added to the flooding topology first. Then each of the nodes connected to the root node (e.g., first degree nodes) are added to the flooding tree. Then each node connected to the nodes connected to the root node (e.g., second degree nodes connected to a first degree node) is added to the flooding tree. This process continues until all nodes are added to the flooding topology along with corresponding links.

<FIG> is a flowchart of another example method <NUM> of building a flooding topology, such as flooding topology <NUM> and/or <NUM>. Accordingly, method <NUM> may be employed by a node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Method <NUM> is a mechanism for building a tree from a root node R with a candidate queue initially containing node R and initially an empty flooding topology Ft. Method <NUM> employs blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, which are substantially similar to blocks <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively. Method <NUM> also employs block <NUM>, which is similar to block <NUM>. However, block <NUM> adds nodes Xi from block <NUM> to the end of the candidate queue instead of to the beginning of the candidate queue. Method <NUM> may consider whether such nodes are capable of LSFR when sorting nodes Xi, or method <NUM> may operate without consideration of LSFR capability (e.g., in a manner substantially similar to method <NUM>).

Accordingly, method <NUM> is substantially similar to method <NUM>, but the flooding tree grows differently. Specifically, the tree grows along the first branch from the root node until all nodes connected to the first branch are added to the flooding topology. Then nodes attached to the second branch from the root node (that have not already been added) are added to the flooding topology, etc. If LSFR capability is considered, nodes that are not LSFR capable can still be placed later in the sequence due to sorting at block <NUM>.

<FIG> is a flowchart of another example method <NUM> of building a flooding topology such as flooding topology <NUM> and/or <NUM>. Accordingly, method <NUM> may be employed by a node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Method <NUM> is a mechanism for building a tree from a root node R with a candidate queue initially containing node R and initially an empty flooding topology Ft. Method <NUM> employs blocks <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, which are substantially similar to blocks <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively. Method <NUM> also includes blocks <NUM> and <NUM>, which are similar to blocks <NUM> and <NUM>, respectively. However, blocks <NUM> and <NUM> orders nodes Xi in the candidate queue based on the cost back to the root node instead of based on ID or the cost back to the previous node in the flooding topology.

Specifically, block <NUM> determines the lowest cost to the root node for each node Xi coupled to the last node added to the flooding topology at block <NUM>. In examples that consider LSFR capability, routes that traverse nodes that do not support LSFR can be assigned increased costs to ensure such routes are excluded and/or only employed on the flooding topology when no complete LSFR supporting path is available. Nodes Xi coupled to the last node added to the flooding topology are added to the candidate queue along with associated shortest costs back to the root node. In the event a node Xi was previously included in the candidate queue during a previous iteration due to connection to another node already in the flooding topology, the new cost to the root node is compared to the previous cost to the root node. The cost is then updated if the new cost is less than the previous cost. This approach causes each node to be considered in the candidate queue based on the lowest cost back to the root node during each iteration. The candidate queue is then sorted by costs back to the root node and/or based on interface/node/link ID.

Accordingly, method <NUM> is substantially similar to method <NUM>, but the flooding tree grows differently. For example, the flooding topology of method <NUM> grows by adding nodes in order of lowest cost back to the root node. This approach causes the flooding topology to be populated primarily with lowest cost paths. Further, lowest cost paths are positioned in the flooding topology so that such paths are employed with the greatest amount of link state traffic. Accordingly, higher cost paths are either excluded or only included in the flooding topology as a last resort to ensure full connectivity. Hence, use of such higher cost paths and/or use of paths that traverse a non-LSFR capable device are employed for the least amount of link state traffic.

Employing a flooding topology, for example as generated according to methods <NUM>, <NUM>, and <NUM>, may result in certain issues. For example, certain mechanisms may be employed to ensure that each node in the network obtains a complete flooding topology in a short time when changes occur in the network, particularly when multiple link or node failures occur. One approach to mitigate such issues is to cause nodes to maintain/compute a redundant flooding topology. Such redundant flooding topology may include a basic flooding topology for flooding changes excluding down links or nodes. In addition, the redundant flooding topology may comprise the information (such as flooding paths) for a link or node failure as well as for multiple link or node failures. Another mechanism that may be employed is a mechanism to account for changes at the root node. For example, when a node X finds out that the root node R used to compute a flooding tree is down or not reachable, node X selects a new root node R according to some rule such as the node with smallest/largest node ID. The node X then computes a flooding tree as discussed above and builds the flooding topology based on the flooding tree (e.g., immediately). Further, when a new node is added into the existing topology and is reachable, the node X may check to determine whether the new node is a new root for a flooding tree according to a root node selection rule, such as the new nodes ID is the new smallest/largest node ID. If the new node is the new root node, node X computes a flooding tree using new node R as the root and builds the flooding topology based on the flooding tree after a predefined interval of time, such as five seconds.

<FIG> is a schematic diagram of an example flooding mechanism <NUM>, which may be employed in an IGP network, such as IGP network <NUM>, <NUM>, and/or <NUM>. The flooding mechanism <NUM> is employed with respect to a first node <NUM>, which can be any node in an IGP network (e.g., node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>) that employs a flooding topology, such as flooding topology <NUM> and/or <NUM>. Such flooding topology can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>.

As shown for purposes of illustration, the node <NUM> is coupled to links <NUM> that are excluded from the flooding topology and links <NUM> that are included in the flooding topology. As noted above, a node <NUM> generally receives link state information from a flooding topology and floods such link state information over other interfaces coupled to the flooding topology. However, certain cases can occur where a node <NUM> receives link state information from a link <NUM> that is not included in the flooding topology. For example, a node <NUM> may receive a link state message <NUM> from a node that is not LSFR capable, and hence has flooded the link state message <NUM> on all interfaces. As another example, the node <NUM> may receive a link state message <NUM> from outside the flooding topology when a node/link has malfunctioned. Accordingly, the node <NUM> can take various actions, depending on the example. In one example, if the link state message <NUM> is received from a link <NUM> that is not on the flooding topology, the node <NUM> sends a link state message <NUM> and <NUM> to the node's <NUM> neighbors over all the other links <NUM> and <NUM> that are attached to the node <NUM> excluding the link <NUM> from which the link state message <NUM> is received (e.g., the link state flooding follows the real network topology). Note that messages <NUM> and <NUM> are copies of message <NUM>. In another example, if the link state message <NUM> is received from a link <NUM> that is not on the flooding topology, the node <NUM> sends a link state message <NUM> to the node's <NUM> neighbors over all the links <NUM> that are attached to node <NUM> and are included on the flooding topology. Hence, the node <NUM> may be configured to receive a link state message <NUM> across a link <NUM> that is excluded from the flooding topology, and flood the link state message <NUM> outside of the flooding topology.

<FIG> is a schematic diagram of an example flooding mechanism <NUM> employed by a first node <NUM> upon discovering a second new node <NUM>. Flooding mechanism <NUM> may be employed in an IGP network, such as IGP network <NUM>, <NUM>, and/or <NUM>. The flooding mechanism <NUM> is employed with respect to a node <NUM>, which can be any node in an IGP network (e.g., node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>) that employs a flooding topology, such as flooding topology <NUM> and/or <NUM>. Such flooding topology can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>. Flooding mechanism <NUM> can be employed with a flooding mechanism <NUM> when the new node <NUM> is discovered.

Mechanism <NUM> illustrates an approach for adjusting link state flooding when a new node <NUM> is connected to a node <NUM>, denoted as a first node <NUM>, which is already operating on the network. Mechanism <NUM> may be triggered when the first node <NUM> establishes an adjacency with the newly connected new node <NUM>. As shown, the newly connected new node <NUM> is directly connected to the first node <NUM> via a link <NUM>. The first node <NUM> assumes that the new node <NUM> is coupled to the flooding topology via the corresponding link <NUM> until the flooding topology can be rebuilt (e.g., after there is a change in the network). As such, link <NUM> is temporally labeled as a flooding topology link in the memory of the first node <NUM>. Accordingly, the link <NUM> is employed to add the newly connected new node <NUM> to the tree of links in the flooding topology until the flooding topology is recomputed. After the new node <NUM> is added to the flooding topology, the first node <NUM> may receive a link state message <NUM> over a link <NUM> in the flooding topology. The first node <NUM> may then forward the link state message <NUM> (a copy of message <NUM>) across both the flooding topology links <NUM> and the link <NUM> to the new node <NUM>. The link state message <NUM> may not be forwarded to links <NUM> that are otherwise excluded from the flooding topology.

<FIG> is a schematic diagram of an example flooding mechanism <NUM> employed upon discovering a node has malfunctioned, (e.g., gone down). The flooding mechanism <NUM> operates on an IGP network, such as IGP network <NUM>, <NUM>, and/or <NUM>. The flooding mechanism <NUM> is illustrated with respect to a first node <NUM>, which can be any node in an IGP network (e.g., node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>) that employs a flooding topology, such as flooding topology <NUM> and/or <NUM>. Such flooding topology can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>. Flooding mechanism <NUM> can be employed with flooding mechanisms <NUM> and/or <NUM> when a down node <NUM> malfunctions.

As shown, mechanism <NUM> operates on an IGP network with nodes <NUM>, a root node <NUM>, and a first node <NUM> connected by links <NUM> and flooding topology links <NUM>, which are substantially similar to nodes <NUM>, root node <NUM>, first node <NUM>, links <NUM>, and flooding topology links <NUM>, respectively. Mechanism <NUM> may operate on any node, and is illustrated from the perspective of the first node <NUM> for clarity of discussion. Mechanism <NUM> may be initiated when the first node <NUM> receives a new link state message <NUM> from a neighbor node <NUM> over a flooding topology link <NUM>. The link state message <NUM> indicates that the down node <NUM> is not functioning. The down node <NUM> is a neighbor with nodes <NUM>, which are also neighbors of the first node <NUM>. The down node <NUM> is a neighbor with node <NUM>, which is not a neighbor of the first node <NUM>.

When the link state message <NUM> is received from a flooding topology link <NUM>, the first node <NUM> sends the link state message <NUM> (a copy of message <NUM>) to the first node's <NUM> neighbors over the flooding topology links <NUM>, excluding the flooding topology links <NUM> from which the link state message <NUM> was received. This ensures the new link state message <NUM> is properly forwarded over the flooding topology. The first node <NUM> also sends the link state message <NUM> (another copy of message <NUM>) to the nodes <NUM> that are neighbors to both the first node <NUM> and the down node <NUM>. Such link state messages <NUM> are sent over the links <NUM> that attach the first node <NUM> to the nodes <NUM>, even though such links <NUM> are not included in the flooding topology. This mechanism <NUM> considers that the nodes neighbors <NUM> may rely on the down node <NUM> for link state messages <NUM>. Hence, the first node <NUM> notifies neighbor nodes <NUM> of the down node <NUM> to ensure that the link state message <NUM> is propagated to such nodes <NUM>. The first node <NUM> may not forward the link state message <NUM> to the remaining neighbor node <NUM> of the down node <NUM>, because the node <NUM> is not a neighbor of the first node <NUM>. The mechanism relies on a neighbor of node <NUM> to inform node <NUM> that the down node <NUM> is not operational. This approach prevents every node in the network from contacting all other nodes when a down node <NUM> malfunctions.

As such, the first node <NUM> may receive a link state message <NUM> (e.g., a third link state message for distinction from other link state messages discussed herein) indicating a second down node <NUM> in the network is down. The first node <NUM> may then flood the link state message <NUM> to links <NUM> that are excluded from the flooding topology and connect between the first node <NUM> and neighbor nodes <NUM> of the down node <NUM>.

<FIG> is a schematic diagram of another example flooding mechanism <NUM> employed upon discovering a node has malfunctioned, (e.g., gone down). The flooding mechanism <NUM> operates on an IGP network, such as IGP network <NUM>, <NUM>, and/or <NUM>. The flooding mechanism <NUM> is illustrated with respect to a first node <NUM>, which can be any node in an IGP network (e.g., node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>) that employs a flooding topology, such as flooding topology <NUM> and/or <NUM>. Such flooding topology can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>. Flooding mechanism <NUM> can be employed with flooding mechanisms <NUM> and/or <NUM> when a down node <NUM> malfunctions.

As shown, mechanism <NUM> operates on an IGP network with nodes <NUM>, a root node <NUM>, and a first node <NUM> connected by links <NUM> and flooding topology links <NUM>, which are substantially similar to nodes <NUM>, root node <NUM>, first node <NUM>, links <NUM> and flooding topology links <NUM>, respectively. Further, a down node <NUM> malfunctions, which is similar to down node <NUM>. Also, the network contains nodes <NUM> that are neighbors to the first node <NUM> and the down node <NUM>, and a node <NUM> that is a neighbor of the down node <NUM> and not a neighbor of the first node <NUM>. Mechanism <NUM> is similar to mechanism <NUM>, but is employed when a first node <NUM> receives a new link state message <NUM> from a neighbor node over a link <NUM> that is not on the flooding topology. The link state message <NUM> contains information indicating the down node <NUM> is down/malfunctioning. In one example, the first node <NUM> sends the link state message <NUM> to all neighbor nodes over all the links <NUM> and <NUM> that are connected to the first node <NUM> excluding the link <NUM> from which the link state message <NUM> was received. Such a response is substantially similar to mechanism <NUM> and allows the link state message <NUM> to flood by following the real network topology. Such an example presumes the first node <NUM> is not properly receiving link state messages over the flooding topology and takes action to ensure the link state message <NUM> is transmitted as widely as possible.

In another example, the first node <NUM> floods the link state message <NUM> (a copy of message <NUM>) over the flooding topology links <NUM>. The first node <NUM> also floods the link state message <NUM> to nodes <NUM> that are neighbors to both the first <NUM> node and the down node <NUM> over links <NUM> that are not on the flooding topology. The link state message <NUM> need not be forwarded back on the link <NUM> from which the link state message <NUM> was received. Further, the first node <NUM> may not forward the link state message <NUM> to the remaining neighbor node <NUM> of the down node <NUM>, because the node <NUM> is not a neighbor of the first node <NUM>. Such an example focuses on forwarding link state information along the flooding topology and informing the down node's <NUM> neighbors of the malfunction. In either example, the first node <NUM> receives a link state message <NUM> (e.g., a third link state message for distinction from other link state messages discussed herein) indicating a second down node <NUM> in the network is down. The first node <NUM> then floods the link state message <NUM> to links <NUM> that are excluded from the flooding topology and connect between the first node <NUM> and neighbor nodes <NUM> of the down node <NUM>.

<FIG> is a schematic diagram of an example flooding mechanism <NUM> employed upon discovering a link <NUM> has malfunctioned, (e.g., gone down). The flooding mechanism <NUM> operates on an IGP network, such as IGP network <NUM>, <NUM>, and/or <NUM>. The flooding mechanism <NUM> is illustrated with respect to a first node <NUM>, which can be any node in an IGP network (e.g., node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>) that employs a flooding topology, such as flooding topology <NUM> and/or <NUM>. Such flooding topology can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>. Flooding mechanism <NUM> can be employed with flooding mechanisms <NUM>, <NUM>, <NUM>, and/or <NUM> when a link <NUM> goes down/malfunctions.

As shown, mechanism <NUM> operates on an IGP network with nodes <NUM>, a root node <NUM>, and a first node <NUM> connected by links <NUM> and flooding topology links <NUM>, which are substantially similar to nodes <NUM>, root node <NUM>, first node <NUM>, links <NUM> and flooding topology links <NUM>, respectively. Further, a down link <NUM> malfunctions. A node <NUM> is coupled to the first node <NUM> via the down link <NUM>. Nodes <NUM> are neighbors to both the first node <NUM> and the node <NUM> adjacent to the down link <NUM>. Node <NUM> is a neighbor to the node <NUM> (adjacent to the down link), but is not a neighbor of the first node <NUM>.

The first node <NUM> finds out that a link <NUM> is down upon receiving a newer link state message <NUM> from a neighbor node, in this case root node <NUM>, over a link, in this case a flooding topology link <NUM>. The first node <NUM> first checks to determine whether the down link <NUM> is on the flooding topology. If the down link <NUM> is not on the flooding topology, the down link <NUM> does not affect link state flooding and no action need be taken beyond forwarding the link state message <NUM> (a copy of message <NUM>) across the flooding topology. In the example shown, the down link <NUM> is on the flooding topology, so the first node <NUM> proceeds to check whether the down link <NUM> is on a neighboring interface to the first node <NUM>. If the down link <NUM> is not on a neighboring interface, the first node <NUM> can allow nodes that are adjacent to the down link <NUM> to handle any signaling, and hence can take no action beyond forwarding the link state message <NUM> across the flooding topology. This approach prevents every node in the network from signaling upon discovering a down link <NUM>. In the example shown, the down link <NUM> is adjacent to the first node <NUM>, so the first node <NUM> takes on signaling reasonability to ensure nodes that might depend on the down link <NUM> continue to receive link state information until the flooding topology can be recalculated. In this case, the first node <NUM> sends the link state message <NUM> across the flooding topology to each flooding topology link <NUM> except for the flooding topology link <NUM> from which the link state message <NUM> was received. Further, the first node <NUM> sends the link state message <NUM> (another copy of message <NUM>) over links <NUM> that are excluded from the flooding topology as necessary to contact nodes <NUM> that are neighbors to both the first node <NUM> and the node <NUM> adjacent to the down link <NUM>. Further, the first node <NUM> may not forward the link state message <NUM> to the remaining neighbor node <NUM> of the node <NUM>, because the node <NUM> is not a neighbor of the first node <NUM>. This approach allows nodes <NUM> that potentially rely on the down link <NUM> to receive link state information to continue to receive such link state information despite the broken flooding topology.

Hence the first node <NUM>, by employing mechanism <NUM>, can receive a link state message <NUM> (e.g., a fourth link state message for distinction from other link state messages discussed herein) indicating a link <NUM> (e.g., a first link) in the network is down. The first node <NUM> can determine that the first link <NUM> is in the flooding topology and that the first link <NUM> is connected to the first node <NUM>. Based on the determination, the first node <NUM> can then send the link state message <NUM> to links <NUM> and/or <NUM> that connect to neighbors which also connect to a node <NUM> adjacent to the first link.

It should be noted that when a link <NUM> on an existing/old flooding topology is down or a node is down (e.g., as discussed in mechanisms <NUM> and <NUM>), a new flooding topology is generated shortly thereafter. The mechanisms <NUM>, <NUM>, and/or <NUM> allow the existing flooding topology to continue to operate until the new flooding topology can be computed and employed by the nodes. The abovementioned mechanisms <NUM>, <NUM>, and <NUM> allow the network to continue to function when a link or node goes down as long as the network topology is not split into multiple isolated flooding topologies by the malfunction. Critical interfaces can be saved in memory to deal with such scenarios as discussed below. <FIG> is a schematic diagram of an example IGP network <NUM> with a critical interface <NUM> in the flooding topology <NUM>. The IGP network <NUM> is substantially similar to IGP network <NUM>, <NUM>, and/or <NUM>. The IGP network <NUM> includes nodes <NUM> and a root node <NUM>, which may be similar to nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. The IGP network <NUM> flooding topology <NUM> may be similar to flooding topology <NUM> and/or <NUM>. Such flooding topology <NUM> can be generated, for example, according to method <NUM>, <NUM>, and/or <NUM>. The nodes <NUM> and root node <NUM> may employ flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>.

Upon computing the flooding topology <NUM>, the nodes <NUM> and root node <NUM> maintain awareness of any critical interface <NUM> in the flooding topology <NUM>. A critical interface <NUM> is any interface (e.g., link or node) on the flooding topology <NUM> that, if removed, would split the flooding topology <NUM> into two or more unconnected topologies of links. In the example shown, the flooding topology <NUM> contains multiple loops of flooding topology links. When a flooding topology link in a loop is removed, the flooding topology <NUM> can still forward link state information to all the nodes on the loop through the undamaged portion of the loop. Hence, such links are not critical interfaces. However, if critical interface <NUM> is removed from the flooding topology <NUM>, the flooding topology <NUM> is split into a first tree <NUM> and a second tree <NUM>. In the absence of the critical interface <NUM>, the first tree <NUM> and the second tree <NUM> cannot communicate link state information as no flooding topology <NUM> link would connect the two trees.

The critical interface(s) <NUM> can be determined at each node <NUM>/<NUM> during/after computing flooding topology <NUM> and be saved in memory. The number of critical interfaces <NUM> can be reduced by adding more leaf links as discussed above. When a link or node associated with a critical interface <NUM> malfunctions, the nodes <NUM>/<NUM> (upon notification of the malfunction via link state messages) may revert to flooding link state messages on all interfaces until a new flooding topology <NUM> can be generated to address the failure of the critical interface and reconnect all the nodes <NUM>/<NUM>.

Hence nodes <NUM>/<NUM> may determine critical interfaces <NUM>, where a critical interface <NUM> is a link or node whose failure splits the flooding topology <NUM>. The nodes <NUM>/<NUM> can discontinue use of the flooding topology <NUM> when a critical interface <NUM> fails.

<FIG> is a schematic diagram of an example OSPF v2 encoding <NUM> for indicating node support for LSFR. For example, a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>, may employ the encoding <NUM> to indicate whether the node supports LSFR. Such information may be employed by other nodes when building a flooding topology, for example based on methods <NUM>, <NUM>, and/or <NUM>. OSPF v2 nodes employing LSFR, and hence employing encoding <NUM>, may also employ flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>.

Encoding <NUM> can be employed to incorporate LSFR into an IGP network that is compatible with OSPF v2. Specifically, encoding <NUM> can be included in an OSPF v2 LSA. Encoding <NUM> includes an LS age field <NUM> set to indicate a time (e.g., in seconds) since the LSA was originated. The LSA age field <NUM> may be sixteen bits long and may extend from bit zero to bit fifteen. The encoding <NUM> also includes an options field <NUM> that may contain data indicating optional capabilities supported in a portion of a routing domain in an IGP network as described by the LSA. The options field <NUM> may be eight bits long and may extend from bit sixteen to bit twenty three. The encoding <NUM> also includes an LS type field <NUM> that can be set to indicate the type of the LSA. For example, the LS type field <NUM> can be set to one to indicate the LSA is a router (e.g., node) LSA. The LS type field <NUM> may be eight bits long and may extend from bit twenty four to bit thirty one. The encoding <NUM> also includes a link state ID field <NUM> that includes data that identifies the portion of the internet environment that is being described by the LSA. For example, the link state ID field <NUM> can be set to indicate that the LSA describes the collected states of a router's interfaces. The link state ID field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one. The encoding <NUM> also includes an advertising router field <NUM> that contains the router ID of the router originating the LSA. The advertising router field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one. The encoding <NUM> also includes an LS sequence number field <NUM> that contains data for identifying the LSA. The LS sequence number field <NUM> data can be employed to detect old or duplicate LSAs. The LS sequence number field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one. The encoding <NUM> also includes an LS checksum field <NUM> containing checksum data to support error checking. The LS checksum field <NUM> may be sixteen bits long and may extend from bit zero to bit fifteen. The encoding <NUM> also includes an LS length field <NUM> containing data indicating the length of the LSA in bytes. The LS length field <NUM> may be sixteen bits long and may extend from bit sixteen to bit thirty one.

The encoding <NUM> also includes various flags employed to indicate various characteristics for the router initiating the LSA. The encoding can include a virtual (V) flag <NUM> at bit position five, which can be set to indicate when the router is an endpoint to one or more adjacent virtual links. The encoding can also include an external (E) flag <NUM> at bit position six, which can be set to indicate when the router is an autonomous system boundary router. The encoding can also include a border (B) flag <NUM> at bit position seven, which can be set to indicate when the router is a border area router.

The encoding <NUM> also includes an F flag <NUM>. The F flag <NUM> may be one bit and may be positioned at bit position eight. The F flag <NUM> can be set (e.g., set to one) to indicate that the router initiating the LSA supports flooding reduction (e.g., according to the LSFR mechanisms discussed herein). The bit position of the F flag <NUM> can also be unset (e.g., set to zero) by default so that routers that do not support LSFR can be identified by routers receiving the LSA. As such, the encoding <NUM> allows link state messages to contain F flags set to indicate the nodes in the network that support link state flooding reduction via a flooding topology.

The encoding <NUM> also includes a number of links field <NUM> that indicate the number of links described by the LSA. The number of links field <NUM> may be sixteen bits long and may extend from bit position sixteen to bit position thirty one. The encoding <NUM> also includes a link ID field <NUM> for each link described by the LSA. The link ID field <NUM> includes an ID that identifies the object (e.g., node) to which the corresponding link is connected. The link ID field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one. The encoding <NUM> also includes a link data field <NUM> for each link described by the LSA. The link data field <NUM> includes address information (e.g., IP address information) related to the corresponding link/interface. The link data field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one.

The encoding <NUM> also includes a type field <NUM> for each link described by the LSA. The type field <NUM> contains data describing the router link. The type field <NUM> may be eight bits long and may extend from bit zero to bit seven. The encoding <NUM> also includes a number of type of service (ToS) fields <NUM> for each link described by the LSA. The number of the ToS field <NUM> indicates a number of ToS metrics for the corresponding links that are included in the LSA. The number of the ToS field <NUM> may be eight bits long and may extend from bit eight to bit fifteen. The encoding <NUM> also includes a metric field <NUM> that includes the cost (e.g., routing cost/latency, etc.) of using the corresponding link. The metric field <NUM> may be sixteen bits long and may extend from bit sixteen to bit thirty one. The encoding <NUM> may also include ToS fields <NUM> and ToS metric fields <NUM> indicating ToS information associated with the corresponding link. The Tos field <NUM> indicates the type of service referred to by the ToS metric field <NUM>, may be eight bits long, and may extend from bit position zero to bit position seven. The Tos metric field <NUM> may indicate ToS specific information for the link, may be sixteen bits long, and may extend from bit sixteen to bit thirty one.

<FIG> is a schematic diagram of an example OSPF v3 encoding <NUM> for indicating node support for LSFR. For example, a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>, may employ the encoding <NUM> to indicate whether the node supports LSFR. Such information may be employed by other nodes when building a flooding topology, for example based on methods <NUM>, <NUM>, and/or <NUM>. OSPF v3 nodes employing LSFR, and hence employing encoding <NUM>, may also employ flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>.

Encoding <NUM> can be employed to incorporate LSFR into an IGP network that is compatible with OSPF v3. Specifically, encoding <NUM> can be included in an OSPF v3 LSA. The encoding <NUM> may include an LS age field <NUM>, a LS type field <NUM>, a link state ID field <NUM>, an advertising router field <NUM>, an LS sequence number field <NUM>, an LS checksum field <NUM>, and an LS length field <NUM>, which may be substantially similar to LS age field <NUM>, LS type field <NUM>, link state ID field <NUM>, advertising router field <NUM>, LS sequence number field <NUM>, LS checksum field <NUM>, and LS length field <NUM>, respectively. Unlike LS type field <NUM>, LS type field <NUM> is sixteen bits long and extends from bit position sixteen to bit position thirty one.

The encoding <NUM> also includes an options field <NUM> that can be set to indicate optional capabilities supported by the router that initiated the LSA. The options field <NUM> may be thirty two bits long and may extend from bit zero to bit thirty one. The options field <NUM> includes various flags employed to indicate various characteristics for the router initiating the LSA. The options field <NUM> may include a V flag <NUM>, an E flag <NUM>, and a B flag <NUM>, which may be substantially similar to V flag <NUM>, E flag <NUM>, and B flag <NUM>, respectively. The options field <NUM> may also include a wildcard (W) flag <NUM> that may be set to indicate the router initiating the LSA is a wildcard multicast receiver. The W flag <NUM> may be one bit long and may be positioned at bit position four.

The options field <NUM> also includes an F flag <NUM>. The F flag <NUM> may be one bit and may be positioned at bit position eight. The F flag <NUM> can be set (e.g., set to one) to indicate that the router initiating the LSA supports flooding reduction (e.g., according to the LSFR mechanisms discussed herein). The bit position of the F flag <NUM> can also be unset (e.g., set to zero) by default so that routers that do not support LSFR can be identified by routers receiving the LSA. As such, the encoding <NUM> allows link state messages to contain F flags set to indicate the nodes in the network that support link state flooding reduction via a flooding topology.

The encoding <NUM> may also include a type field <NUM> and a metric field <NUM> for each link described by the LSA. The type field <NUM> and metric field <NUM> maybe substantially similar to the type field <NUM> and metric field <NUM>, respectively. The encoding <NUM> may also include an interface ID field <NUM>, a neighbor interface ID field <NUM>, and a neighbor router ID field <NUM> for each link described in the LSA. The interface ID field <NUM>, neighbor interface ID field <NUM>, and neighbor router ID field <NUM> may each be thirty two bits long and extend from bit position zero to bit position thirty one. The interface ID field <NUM> indicates an ID assigned to the interface (e.g., link) being described. The neighbor interface ID field <NUM> indicates an interface ID of the neighboring router coupled to the link being described. The neighbor router ID field <NUM> indicates the router ID of the neighboring router coupled to the link being described. <FIG> is a schematic diagram of an example IS-IS encoding <NUM> for indicating node support for LSFR. For example, a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>, may employ the IS-IS encoding <NUM> to indicate whether the node supports LSFR. Such information may be employed by other nodes when building a flooding topology, for example based on methods <NUM>, <NUM>, and/or <NUM>. IS-IS nodes employing LSFR, and hence employing encoding <NUM>, may also employ flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>.

Encoding <NUM> can be employed to incorporate LSFR into an IGP network that is compatible with IS-IS. Specifically, encoding <NUM> can be included as a TLV in an IS-IS LSP. The encoding <NUM> includes a type field <NUM> set to indicate that the encoding is an IS-IS router capable TLV. For example, the type field <NUM> may be eight bits long, may extend from bit position zero to bit position seven, and may be set to two hundred forty two. The encoding <NUM> includes a length field <NUM>, which may be eight bits long, may extend from bit position eight to bit position fifteen, and may be set to indicate the length of the TLV. The length field <NUM> can be set to a value of between five and two hundred fifty five inclusive. The encoding <NUM> also includes a router ID field <NUM>, which is thirty two or forty eight bits long, may extend from bit position sixteen to bit position fifteen or thirty one, and contains an ID of the router initiating the link state message. The encoding <NUM> also includes a set of flags <NUM> that indicate capabilities of the router initiating the link state message. The flags <NUM> may be eight bits long and may extend from bit sixteen to bit twenty three. The flags <NUM> include a de-looping (D) flag <NUM> that may be positioned at bit position twenty two, and may be set to indicate whether the TLV can be leaked between levels in the IS-IS system. The flags <NUM> also include a set (S) flag <NUM> that may be positioned at bit position twenty three, and may be set to indicate whether the TLV is flooding across the entire IS-IS network domain or contained to a particular IS-IS network level.

The flags <NUM> also include an F flag <NUM>, which may be positioned at bit position twenty one. The F flag <NUM> can be set (e.g., set to one) to indicate that the router initiating the LSP supports flooding reduction (e.g., according to the LSFR mechanisms discussed herein). The bit position of the F flag <NUM> can also be unset (e.g., set to zero) by default so that routers that do not support LSFR can be identified by routers receiving the LSP. As such, the encoding <NUM> allows link state messages to contain F flags set to indicate the nodes in the network that support link state flooding reduction via a flooding topology.

The encoding <NUM> may also include one or more optional sub-TLVs <NUM> that contain additional information relevant to the LSP.

<FIG> is a schematic diagram of an example LSFR control TLV encoding <NUM> for managing LSFR in an IGP network. For example, a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>, may receive the LSFR control TLV encoding <NUM> to control the implementation of LSFR in the network. Specifically, the LSFR control TLV encoding <NUM> may allow a user/system administrator to select and/or switch operating modes for LSFR and associated flooding topologies. The LSFR control TLV encoding <NUM> may be employed as part of a link state message, such as encoding <NUM>, <NUM>, and/or <NUM>. Such information may be employed by nodes when building a flooding topology, for example based on methods <NUM>, <NUM>, and/or <NUM>. The LSFR control TLV encoding <NUM> may also indicate to the nodes when to employ LSFR flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>.

The LSFR control TLV encoding <NUM> employs an information TLV type field <NUM> that may include data identifying the TLV as an LSFR control TLV. The TLV type field <NUM> may be sixteen bits long and may extend from bit position zero to bit position fifteen. The LSFR control TLV encoding <NUM> also employs a TLV length field <NUM> that includes data indicating the length of the LSFR control TLV. The TLV length field <NUM> may be sixteen bits long and may extend from bit position sixteen to bit position thirty one.

The LSFR control TLV encoding <NUM> also employs an operation (OP) field <NUM>, which may be three bits long and may extend from bit position zero to bit position two. The OP field <NUM> can be employed to select and/or change the LSFR operating mode for nodes that are LSFR capable. The OP field <NUM> can contain data to indicate that nodes should perform flooding reduction or may contain data to indicate that nodes should roll back to normal flooding without using a flooding topology. Hence, the LSFR control TLV encoding <NUM> allows link state messages to contain an OP field set to switch to link state flooding reduction from full network flooding. For example, a user/system administrator may employ the OP field <NUM> to turn LSFR on and/or off as desired.

The LSFR control TLV encoding <NUM> also employs a mode (MOD) field <NUM>, which may be three bits long and may extend from bit position three to bit position five. LSFR may include three modes, including central mode, distributed mode, and static configuration mode, and the MOD field <NUM> may be employed to signal a switch between modes. For example, the MOD field <NUM> can be set to central mode, which directs the IGP network to select a leader and/or backup leader. The leader then computes the flooding topology, and floods the flooding topology to the other nodes. Every node receives and uses the flooding topology from the leader. The MOD field <NUM> can also be set to distributed mode, which directs all the nodes in the IGP network to compute a flooding topology by employing a common algorithm as discussed above. The MOD field <NUM> can also be set to static configuration mode, which directs the nodes in the IGP network to employ a configured flooding topology. Hence, the LSFR control TLV encoding <NUM> allows link state messages to contain a MOD field <NUM> set to indicate centralized link state flooding reduction, distributed link state flooding reduction, or statically configured link state flooding reduction.

The LSFR control TLV encoding <NUM> also employs an algorithm field <NUM>, which may be eight bits long and may extend from bit position six to bit position thirteen. The algorithm field <NUM> may contain data indicating an algorithm for computing a flooding topology (e.g., method <NUM>, <NUM>, and/or <NUM>) that should be used by nodes in central and/or distributed mode. Hence, the LSFR control TLV encoding <NUM> allows link state messages to contain an algorithm field <NUM> set to indicate an algorithm to build the tree of links in the flooding topology.

The encoding <NUM> may also include one or more optional sub-TLVs <NUM> that contain additional information relevant to LSFR implementation.

<FIG> is a schematic diagram of an example TLV encoding <NUM> for integrating centralized LSFR with distributed LSFR. Specifically, the TLV encoding <NUM> may be used in conjunction with the LSFR control TLV encoding <NUM>, for example when the MOD field <NUM> is set to central mode. The TLV encoding <NUM> includes an information TLV type field <NUM> and a TLV length field <NUM> that are substantially similar to the information TLV type field <NUM> and the TLV length field <NUM>, respectively. The TLV encoding <NUM> also includes a priority field <NUM>, which may be eight bits long and may extend from bit position zero to bit position seven. The priority field <NUM> may be employed to indicate a priority of a node originating a TLV to become a leader in central mode. The encoding <NUM> may also include one or more optional sub-TLVs <NUM> that contain additional information relevant to LSFR implementation. Such sub-TLVs <NUM> may include a leader sub-TLV and/or a backup leader sub-TLV, which include a method/algorithm to select the leader and/or backup leader, respectively.

<FIG> is a flowchart of an example method <NUM> of operating LSFR mechanisms in an IGP network. For example, method <NUM> may be employed by a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>. Method <NUM> may be employed in OSPF and/or IGP networks, and hence may be employed in conjunction with encoding <NUM>, <NUM>, and/or <NUM>. Method <NUM> may be employed to build a flooding topology, for example by employing methods <NUM>, <NUM>, and/or <NUM>. Method <NUM> may also employ flooding mechanisms, such as flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Method <NUM> may also be initiated by receipt of an LSFR control TLV encoding <NUM>.

The method <NUM> can be implemented on any node in an IGP network, which is denoted as a first node for purposes of clarity of discussion. At block <NUM>, data is received at the first node that indicates connectivity of a plurality of nodes in the network. Such data includes link state data, and can be received, for example, according to general flooding of link state messages, such as OSPF LSAs or IS-IS LSPs.

At block <NUM>, the first node (and all nodes in the network) build a flooding topology based on the connectivity. The flooding topology can be built by selecting one of the network nodes as a root node, and building a tree of flooding topology links connecting the root node to the other nodes in the network. For example, block <NUM> may build a flooding topology by employing methods <NUM>, <NUM>, and/or <NUM>. Building a flooding topology can occur periodically and/or upon the occurrence of a condition, such as a link/node malfunction, the malfunction of a critical interface, etc. As discussed above, the flooding topology can be built based on LSFR capability of the nodes, for example as advertised in link state messages employing an F flag. Further, the first node (and all nodes) can build the flooding topology according to an algorithm indicated in an LSFR control TLV encoding <NUM> (e.g., in a link state message).

At optional block <NUM>, the first node may receive a request specifying a number of leaf links to add to the tree. The request may be a TLV included in a link state message, for example as initiated by a user/network administrator. If a request is received, the first node (and all nodes in the network) adds the number of leaf links to the flooding topology as specified in the request. Such leaf links are added between the nodes in the network, for example as discussed with respect to <FIG> above. For example, leaf links can be added to reduce the number of critical interfaces, can be added based on link ID/interface ID/node ID, etc. Prior to adding such leaf links, the tree of links in the flooding topology may contain a minimum number of links to connect all of the nodes in the network to the root node. The leaf links may increase reliability of the flooding topology at the expense of slightly increasing redundant link state message communication.

At block <NUM>, the first node stores the flooding topology in a memory without transmitting the flooding topology to the other nodes in the network. This approach ensures that the flooding topology is created at each node according to a preselected algorithm, which in turn reduces link state message flooding related to the flooding topology.

At block <NUM>, the first node floods link state messages over the flooding topology. Further, the first node does not flood link state messages outside of the flooding topology.

At optional block <NUM>, the first node may alter flooding procedure based on changes in link/node status. For example, the first node may employ flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM> depending on the type of changes that occur in the network. As specific examples, the first node can receive a first link state message from a newly connected node, where the newly connected node is directly connected to the first node via a link. The first node can then add the newly connected node to the tree of links in the flooding topology until the flooding topology is recomputed. As another example, the first node can receive a second link state message across a link that is excluded from the flooding topology. The first node can then flood the second link state message outside of the flooding topology. As another example, the first node can receive a third link state message indicating a second node in the network is down. The first node can then flood the third link state message to links that are excluded from the flooding topology and connect between the first node and neighbors of the second node. As another example, the first node can receive a fourth link state message indicating a first link in the network is down. The first node can determine that the first link is in the flooding topology and the first link is connected to the first node. Based on the determination, the first node can send the fourth link state message to links that connect to neighbors which also connect nodes adjacent to the first link. As another example, the first node can determine critical interfaces in the network, where a critical interface is a link or node whose failure splits the flooding topology. The first node can discontinue use of the flooding topology when a critical interface fails.

<FIG> is an embodiment of a device <NUM> for operating LSFR mechanisms in an IGP network. For example, device <NUM> may be employed to implement method <NUM>. Further, device <NUM> may be employed as a node, such as nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>, in an IGP network, such as IGP network <NUM>, <NUM>, <NUM>, and/or <NUM>. Device <NUM> may be employed in OSPF and/or IGP networks, and hence may be employed in conjunction with encoding <NUM>, <NUM>, and/or <NUM>. Device <NUM> may be employed to build a flooding topology, for example by employing methods <NUM>, <NUM>, and/or <NUM>. Device <NUM> may also employ flooding mechanisms, such as flooding mechanisms <NUM>, <NUM>, <NUM>, <NUM>, and/or <NUM>. Device <NUM> may also be controlled by receipt of an LSFR control TLV encoding <NUM>.

The device <NUM> includes a receiving module <NUM>, which is a means for receiving data indicating connectivity of a plurality of nodes in the network including the first node. The device <NUM> includes a flood topology building module <NUM>, which is a means for building a flooding topology based on the connectivity by selecting one of the nodes as a root node, and building a tree of links connecting the root node to the nodes in the network. The device <NUM> includes a storing module <NUM>, which is a means for storing the flooding topology without transmitting the flooding topology to the plurality nodes in the network. The device <NUM> also includes a flooding module <NUM>, which is a means for flooding link state messages over the flooding topology.

In one embodiment, a first node in a network includes receiving means for receiving data indicating connectivity of a plurality of nodes in the network including the first node. The first node further includes building means for building, by a processor means of the first node, a flooding topology based on the connectivity by selecting one of the nodes as a root node, by building a tree of links connecting the root node to the nodes in the network, by storing the flooding topology in a memory without transmitting the flooding topology to the plurality of nodes in the network and by flooding link state messages over the flooding topology.

A first component is directly coupled to a second component when there are no intervening components, except for a line, a trace, or another medium between the first component and the second component. The first component is indirectly coupled to the second component when there are intervening components other than a line, a trace, or another medium between the first component and the second component. The term "coupled" and its variants include both directly coupled and indirectly coupled. The use of the term "about" means a range including ±<NUM>% of the subsequent number unless otherwise stated.

While several embodiments have been provided in the present disclosure, it may be understood that the disclosed systems and methods might be embodied in many other specific forms without departing from the spirit or scope of the present disclosure. The present examples are to be considered as illustrative and not restrictive, and the intention is not to be limited to the details given herein. For example, the various elements or components may be combined or integrated in another system or certain features may be omitted, or not implemented.

Claim 1:
A method implemented in a first node in a network, the method comprising:
receiving, by the first node, data indicating connectivity of a plurality of nodes in the network including the first node;
building, by the first node, a flooding topology based on the connectivity, wherein the first node is selected as a root node, and
storing the flooding topology in a memory; and
flooding, by the first node, the flooding topology to nodes in the flooding topology to enable the nodes to send link state messages over the flooding topology without transmitting such messages across network links that are excluded from the flooding topology;
flooding, by the first node, link state messages over the flooding topology, wherein the link state message contains a mode field set to indicate centralized link state flooding reduction;
the method further comprising:
receiving, a request specifying a number of leaf links to add to the tree; and
adding to the flooding topology, the number of leaf links between the nodes in the network.