Systems and methods for automatically building and repairing a spanning tree flooding backbone in link state routed networks
AssigneeCiena Corporation
InventorsAlexander A. Smith, John K. Oltman
Life of this patent
Estimating the term…
Abstract
The present disclosure provides systems and methods for a spanning tree topology used as a spanning tree flooding topology for messages on a link state routed network. Specifically, messages are only broadcast on the links in the spanning tree flooding topology thereby significantly reducing message flooding. The present disclosure also provides systems and methods for automatically, correctly, and efficiently creating, reconfiguring, and fixing the spanning tree topology in the event of any spanning tree link failures.
Claims16
A network operating method, comprising:
- upon achieving full adjacency of nodes in a network, determining a single spanning tree connecting each node via an algorithm;
- setting each link in the spanning tree at each of the nodes as a flooding link;
- checking at each of the nodes with neighboring nodes a link flooding status of links associated with the spanning tree;
- and
- operating the network using only the links in the spanning tree to exchange link state messages while using all links to exchange data thereon, wherein the network comprises at least one link not part of the spanning tree on which the link state messages are not flooded, and wherein the link state messages comprise topology information.
A link state routed network, comprising:
- a plurality of nodes;
- a plurality of links interconnecting the plurality of nodes and each exchanging data between the plurality of node;
- and
- an algorithm operating at each of the plurality of nodes and configured to automatically define and monitor a single spanning tree comprising some of the plurality of links, to repair the spanning tree responsive to a fault without re-defining the entire spanning tree, and to constrain link state message broadcast only to links in the spanning tree, wherein at least one of the plurality of links not part of the spanning tree does not have flooding of the link state message.
A network operating method with a spanning tree flooding topology, comprising:
- exchanging topology messages between a plurality of nodes in a network;
- upon achieving full adjacency of the plurality of nodes, executing Prim's algorithm at each of the plurality of nodes in the network thereby defining a single spanning tree in the network;
- checking between the plurality of nodes to ensure each of the plurality of nodes has the same topology of the spanning tree;
- operating the network comprising sending link state messages only on links in the spanning tree while using all links to exchange data thereon, wherein the network comprises at least one link not part of the spanning tree on which the link state messages are not flooded, and wherein the link state messages comprise topology information;
- detecting a failed link in the spanning tree;
- and
- automatically repairing the spanning tree by determining a new path between opposing nodes on the failed link without re-defining the entire spanning tree using Prim's algorithm.
Dependencies are inferred from the claim text.