Method and system for ring topology discovery and forwarding database flush nullification

Abstract

A method and system for rerouting data in a communication network ring. The ring includes a plurality of nodes and a plurality of links. Each node includes a first port and a second port. Each first port is connected to a neighboring second port through a link of the plurality of links. The topology of the communication network ring is discovered and a forwarding database table is populated with static entries according to the discovered topology. Upon receiving notice of a failed link, which includes a source address of a node adjacent to the failed link, the topology and the source address of the node adjacent to the failed link is used to reconfigure the forwarding database table. Data is forwarded using the reconfigured forwarding database table without flooding the ring.

1 . A method for rerouting data in a communication network ring, the ring including a plurality of nodes, each node including a first port and a second port, each first port connected to a second port of a neighboring node through a link of the plurality of links, the method comprising:
 discovering a topology of the communication network ring;   populating static entries in a forwarding database table according to the discovered topology;   receiving notice of a failed link, the notice including a source address of a node adjacent to the failed link;   using the topology and the source address of the node adjacent to the failed link to reconfigure the forwarding database table; and   forwarding data using the reconfigured forwarding database table.   
     
     
         2 . The method of  claim 1 , wherein discovering the topology of the communication network ring comprises:
 receiving at least one of a ring topology request and a response to the ring topology request from at least one node on the ring, the at least one of the ring topology request and the response to the ring topology request including an identification of the at least one node and a hop count needed to reach the at least one node;   forwarding the at least one of the ring topology request and the response to the ring topology request to at least one neighboring node on the ring through the first port; and   determining the topology based on the identification of the at least one node, the hop count, and an identification of the first port.   
     
     
         3 . The method of  claim 2 , wherein the ring topology request is a Ring Automated Protection Switching message, the Ring Automated Protection Switching message including a type-length-value element, the method further comprising:
 receiving a ring topology request at the first port and the second port;   modifying each ring topology request by adding an identification of a receiving node to the type-length-value element and incrementing the node count; and   forwarding each modified ring topology request to the neighboring node through the other of the first port and the second port than the port on which the ring topology request was received.   
     
     
         4 . The method of  claim 2 , wherein the at least one ring topology request is a Ring Automated Protection Switching message, the method further comprises:
 creating the at least one ring topology request by adding a type-length-value element to the Ring Automated Protection Switching message, the type-length-value element including a node signature for an originating node and the hop count; and   initializing the hop count.   
     
     
         5 . The method of  claim 4 , wherein the ring topology request is forwarded through the first port and the second port, and further wherein receiving at least one response to the ring topology request comprises:
 receiving a response at first port and the second port, each response having been forwarded through the ring from the other of the first port and the second port from which the response was received, each response including a total node count of all the nodes in the ring and an identification of each node in the ring arranged in an order of processing.   
     
     
         6 . The method of  claim 2 , further comprising creating the ring topology request in response to detecting a failure of a link connected to the other of the first port and the second port from which the response was received the transmitting port. 
     
     
         7 . The method of  claim 2 , wherein the ring topology request is a LinkTrace message, the LinkTrace message including a time-to-live value, the method further comprising:
 inserting a ring identifier into the LinkTrace message, the ring identifier being a group address used to keep the ring topology request local to the ring;   receiving a plurality of LinkTrace responses, each LinkTrace response originated by one of the nodes of the plurality of nodes of the ring, each LinkTrace response including an identification of the originating node; and   wherein the indication of a node count needed for the ring topology request to reach the at least one responding node is a time-to-live value.   
     
     
         8 . The method of  claim 7 , wherein the node count needed for the ring topology request to reach the at least one responding node is equal to one half of a difference between the time-to-live value of the LinkTrace message and the time-to-live value of the LinkTrace response. 
     
     
         9 . The method of  claim 2 , wherein the ring topology request is a continuity check message, the continuity check message including a listing of identifications of nodes having previously received continuity check message, the method further comprising:
 receiving the ring topology request at one of the first port and the second port;   modifying the ring topology request by appending an identification of a receiving node to listing of identifications of nodes having previously received continuity check message and incrementing the node count; and   forwarding the modified ring topology request to the neighboring node through the other of the first port and the second port on which the ring topology request was received.   
     
     
         10 . The method of  claim 2 , wherein the ring topology request is a continuity check message, the method further comprising:
 receiving a modified ring topology request through the other of the first port and the second port on which the ring topology request was transmitted, the modified ring topology request including a listing of identifications of nodes having previously received continuity check message in an order of processing and a total node count of all nodes on the ring.   
     
     
         11 . A node of a communication network ring, the ring including a plurality of nodes, the node comprising:
 a first port and a second port, each first port connected to a second port of a neighboring node through a link, each port operable to receive and transmit data; and   a processor electrically connected to each port, the processor operates to:   determine a topology of the ring;   populate static entries in a forwarding database table according to the topology; and   responsive to receiving notice of a failed link, the notice including a source address of a node adjacent to the failed link, the processor further operates to:   use the topology and the source address of the node adjacent to the failed link to reconfigure the forwarding database table; and   forward data using the reconfigured forwarding database table.   
     
     
         12 . The node of  claim 11 , wherein at least one of the first port and the second port receives at least one of a ring topology request and a response to the ring topology request from at least one other node on the ring, the at least one of the ring topology request and the response to the ring topology request including an identification of the at least one other node and a hop count needed to reach the at least one other node, the other of the first port and the second port than the port on which the at least one of a ring topology request and a response to the ring topology request was received is operable to forward the at least one of a ring topology request and a response to the ring topology request to at least one neighboring node on the ring. 
     
     
         13 . The node of  claim 12 , wherein the processor determines the topology based on the identification of the at least one node, the hop count, and an identification of the forwarding port. 
     
     
         14 . The node of  claim 12 , wherein the ring topology request is a Ring Automated Protection Switching message, the Ring Automated Protection Switching message including a type-length-value element,
 each port further receives a ring topology request; and   the processor further:
 modifies each ring topology request by adding an identification of a receiving node to the type-length-value element and incrementing the node count; and 
 forwards the modified ring topology request to the neighboring node through the other of the first port and the second port than the port on which the ring topology request was received. 
   
     
     
         15 . The node of  claim 12 , wherein the at least one ring topology request is a Ring Automated Protection Switching message, the processor further creates the at least one ring topology request by:
 adding a type-length-value element to the Ring Automated Protection Switching message, the type-length-value element including a node signature for the node and the hop count; and   initializing the hop count.   
     
     
         16 . The node of  claim 15 , wherein the ring topology request is forwarded through both ports, receiving at least one response to the ring topology request comprises:
 receiving a response at each of the first port and the second port, each response having been forwarded through the ring from the opposite port, each response including a total node count of all the nodes in the ring and an identification of each node in the ring arranged in an order of processing.   
     
     
         17 . The node of  claim 12 , wherein the ring topology request is a LinkTrace message, the LinkTrace message including a time-to-live value, the processor further inserts a ring identifier into the LinkTrace message, the ring identifier being a group address insuring that the ring topology request remains local to the ring; and
 at least one of the first port and the second port further receives a plurality of LinkTrace responses, each LinkTrace response originated by one of the nodes of the plurality of nodes of the ring, each LinkTrace response including an identification of the originating node; and   wherein the indication of a hop count needed for the ring topology request to reach the at least one responding node is a time-to-live value.   
     
     
         18 . The node of  claim 17 , wherein the hop count needed for the ring topology request to reach the at least one responding node is equal to one half of a difference between the time-to-live value of the LinkTrace message and the time-to-live value of the LinkTrace response. 
     
     
         19 . The node of  claim 12 , wherein the ring topology request is a continuity check message, at least one port further receives a modified ring topology request through the other of the first port and the second port on which the ring topology request was transmitted, the modified ring topology request including a listing of identifications of nodes having previously received continuity check message in an order of processing and a total node count of all the nodes on the ring. 
     
     
         20 . A system for rerouting data in a communication network ring, the system comprising:
 a plurality of nodes interconnected in a ring configuration, each node including:
 a first port and a second port, each port operable to receive and transmit data; and 
 a processor electrically connected to each port, the processor operating to:
 determine a topology of the ring; 
 populate static entries in a forwarding database table according to the topology; and 
 responsive to receiving notice of a failed link, the notice including a source address of a node adjacent to the failed link, the processor further operating to:
 use the topology and the source address of the node adjacent to the failed link to reconfigure the forwarding database table; and 
 forward data using the reconfigured forwarding database table.