Reduction of message and computational overhead in networks

Abstract

Various exemplary embodiments relate to a method and related network node including one or more of the following: receiving, at the node, a network update message; determining whether the network update message should be propagated to other nodes; if the network update message should be propagated to other nodes, forwarding the network update message to at least one other node; and if the network update message should not be propagated to other nodes, refraining from forwarding the network update message to any other node. Various further embodiments relate to a method and related network node including one or more of the following: determining a first time period for the network update message; setting the first time period as a delay time; waiting for the delay time; and after the delay time has elapsed, computing new routing information based on the network update message.

What is claimed is: 
     
         1 . A method of reducing overhead in a network performed at a network node, the method comprising:
 receiving, at the node, a network update message;   determining whether the network update message should be propagated to other nodes;   if the network update message should be propagated to other nodes, forwarding the network update message to at least one other node; and   if the network update message should not be propagated to other nodes, refraining from forwarding the network update message to any other node.   
     
     
         2 . The method of  claim 1 , wherein the step of determining whether the network update message should be propagated comprises:
 determining whether routing information of the node should be changed in response to the network update message;   if routing information should be changed, determining that the network update message should be propagated to other nodes; and   if routing information should not be changed, determining that the network update message should not be propagated to other nodes.   
     
     
         3 . The method of  claim 1 , wherein the step of determining whether the network update message should be propagated comprises:
 determining whether the network update message indicates that a link is up or down;   determining whether a relevant network path structure includes the link;   if the link is up and the relevant network path structure includes the link, determining that the network update message should not be propagated to other nodes; and   if the link is down and the relevant network path structure does not include the link, determining that the network update message should not be propagated to other nodes.   
     
     
         4 . The method of  claim 3 , further comprising, if the link is down and the relevant network path structure includes the link, determining that the network update message should be propagated to other nodes. 
     
     
         5 . The method of  claim 3 , further comprising, if the link is down and the relevant network path structure includes the link:
 computing new routing information based on the network update message;   determining whether the current routing information and the new routing information are different;   if the current routing information and the new routing information are different, determining that the network update message should be propagated to other nodes; and   if the current routing information and the new routing information are not different, determining that the network update message should not be propagated to other nodes.   
     
     
         6 . The method of  claim 3 , wherein the link is a link between a second node and a third node, the method further comprising, if the link is up and the relevant network path structure does not include the link:
 determining a cost of a current path from the node to the second node;   determining a cost of a current path from the node to the third node;   determining a cost of the link;   determining whether the cost of the current path to the second node is greater than the sum of the cost of the current path to the third node and the cost of the link;   determining whether the cost of the current path to the third node is greater than the sum of the cost of the current path to the second node and the cost of the link; and   if the cost of the current path to the second node is not greater than the sum of the cost of the current path to the third node and the cost of the link and the current path to the third node is not greater than the sum of the cost of the current path to the second node and the cost of the link, determining that the network update message should not be propagated to other nodes.   
     
     
         7 . The method of  claim 1  further comprising:
 determining a delay time for the network update message; 
 waiting for the delay time; and 
 after the delay time has elapsed, computing new routing information based on the network update message. 
 
     
     
         8 . The method of  claim 1 , further comprising, if the network update message should not be propagated to other nodes:
 constructing a marked network update message including at least a portion of the network update message and an indication that the network update message should not be propagated; and   transmitting the marked network update message to at least one other node.   
     
     
         9 . The method of  claim 1 , wherein the step of refraining from forwarding the network update message to any other node comprises:
 refraining from immediately forwarding the network update message to any other node;   storing the network update message;   waiting for a period of time; and   after the period of time has elapsed, transmitting the network update message to at least one other node along with at least one additional network update message.