Efficient propagation of link state advertisements in densely interconnected OSPF networks
View Patent ↗A method for efficient propagation of link state advertisements in densely interconnected OSPF networks is disclosed for reducing the number of duplicate LSAs propagated during a flooding event. The efficient propagation method includes calculating an LSA propagation subgraph which is used by a node which receives an LSA to determine which links to propagate the LSA upon. This allows a significant reduction in the LSAs which traverse the network during a flooding event. The reduction in LSAs is particularly useful for reducing network convergence times associated with flooding events. In addition, a system is disclosed for performing the method in both a centralized and dispersed manner.
1. A method of reducing, in a network having a plurality of core nodes and a plurality of edge nodes connected by links, the number of duplicate link-state advertisements (LSAs) propagated during a flooding event, said method comprising the steps of:
forming an LSA forwarding subgraph wherein the edges of said LSA forwarding subgraph correspond to said links, and said LSA forwarding subgraph comprises the union of a quantity K spanning-trees containing said core nodes and the links connecting said core nodes to said edge nodes, and wherein said K spanning-trees are edge-disjoint, and where within each of the K spanning-trees no core node can have a degree greater than quantity N, and where a core node appears as a node in more than one tree of said quantity of K spanning-trees only insofar that an overall degree of said core node in the K spanning trees is at most a quantity M, wherein K, M, and N are integers greater than 1; and
upon a core node in said network receiving an LSA along a first link during said flooding event, said core node forwarding said LSA along only a first subset of links corresponding to edges in said LSA forwarding subgraph; and
upon an edge node in said network receiving an LSA along a first link during said flooding event, said edge node forwarding said LSA along only a second subset of links corresponding to edges in said LSA forwarding subgraph.
2. A method as claimed in claim 1 wherein said first subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said core node.
3. A method as claimed in claim 2 wherein said second subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said edge node.
4. A method as claimed in claim 2 wherein said second subset comprises no links.
5. A method as claimed in claim 1 wherein said first subset comprises those links incident on said core node that correspond to edges of the spanning-tree of said quantity K spanning-trees of which said first link is a member in said LSA forwarding subgraph.
6. A method as claimed in claim 5 wherein said second subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said edge node.
7. A method as claimed in claim 5 wherein said second subset comprises no links.
8. A system that reduces the number of duplicate link-state advertisements (LSAs) propagated during a flooding event, said system comprising:
a plurality of core nodes;
a plurality of edge nodes, and wherein said plurality of core nodes and said plurality of edge nodes are connected by links;
an LSA forwarding subgraph calculator which automatically calculates an LSA forwarding subgraph wherein the edges of said LSA forwarding subgraph correspond to said links, and said LSA forwarding subgraph comprises the union of a quantity K spanning-trees containing said core nodes and the links connecting said core nodes to said edge nodes, and wherein said K spanning-trees are edge-disjoint, and where within each of the K spanning-trees no core node can have a degree greater than quantity N, and where a core node appears as a node in more than one tree of said quantity of K spanning-trees only insofar that an overall degree of said core node in the K spanning trees is at most a quantity M, wherein K, M, and N are integers greater than 1; and
a core node forwarding module in each core node of said plurality of core nodes which upon its respective core node receiving an LSA along a first link during said flooding event, said core node forwarding module forwarding said LSA along only a first subset of links corresponding to edges in said LSA forwarding subgraph; and
an edge node forwarding module in each edge node of said plurality of edge nodes which upon its respective edge node receiving an LSA along a first link during said flooding event, said edge node forwarding module forwarding said LSA along only a second subset of links corresponding to edges in said LSA forwarding subgraph.
9. A system as claimed in claim 8 wherein said first subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said core node.
10. A system as claimed in claim 9 wherein said second subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said edge node.
11. A system as claimed in claim 9 wherein said second subset comprises no links.
12. A system as claimed in claim 8 wherein said first subset comprises those links incident on said core node that corresponds to edges of the spanning-tree of said quantity K spanning-trees of which said first link is a member in said LSA forwarding subgraph.
13. A system as claimed in claim 12 wherein said second subset comprises any link that corresponds to edges in said LSA forwarding subgraph that are incident on said edge node.
14. A system as claimed in claim 12 wherein said second subset comprises no links.
15. A system as claimed in claim 8 wherein said LSA forwarding subgraph calculator is located at a single location and which propagates said LSA forwarding subgraph to said plurality of core nodes and said plurality of edge nodes.
16. A system as claimed in claim 8 wherein said LSA forwarding subgraph calculator is located at each of said plurality of core nodes and said plurality of edge nodes.