Utilizing Betweenness to Determine Forwarding State in a Routed Network

Abstract

A set of critical nodes or links is identified on the network through which most of the shortest paths on the network occur. Each node compares their distance to end points on the network with a distance between the end points and each of the distinct critical nodes. Where the distance between the end points and the critical nodes is shorter than the distance between the end points and the node, the node is not on the shortest path and does not install forwarding state. Where the distance between the end points and the critical node is larger than or equal to the distance between the end points and the node, the node may be on the shortest path between the pair of end nodes and installs forwarding state. Installation of forwarding state may cause packet duplication, but determining forwarding state is dramatically simplified.

What is claimed is: 
     
         1 - 24 . (canceled) 
     
     
         25 . A method of limiting multicast forwarding state at a node of a routed network, the method comprising:
 receiving, by the node, a link state advertisement containing an indication that a multicast destination would like to join a multicast;   determining respective costs of a shortest path from the node to a multicast source and of a shortest path from the node to the multicast destination;   determining respective costs of a shortest path from at least one other node to the multicast source and of a shortest path from the at least one other node to the multicast destination; and   not installing forwarding state for forwarding multicast traffic from the multicast source to the multicast destination, by the node, when the sum of the cost of the shortest path from the node to the multicast source and the cost of the shortest path from the node to the multicast destination is greater than the sum of the cost of the shortest path from the at least one other node to the multicast source and the cost of the shortest path from the at least one other node to the multicast destination.   
     
     
         26 . The method of  claim 25 , wherein the at least one other node is neither the multicast source nor the multicast destination. 
     
     
         27 . The method of  claim 25 , wherein the respective costs of the shortest path from the at least one other node to the multicast source and of the shortest path from the at least one other node to the multicast destination are strictly positive. 
     
     
         28 . The method of  claim 25 , comprising:
 pre-computing a shortest path tree from the node to each other node on the network; and   using the pre-computed shortest path tree to determine the cost of the shortest path from the node to the multicast source and the cost of the shortest path from the node to the multicast destination.   
     
     
         29 . The method of  claim 25 , comprising:
 pre-computing a respective shortest path tree from the at least one other node to each other node on the network; and   using the pre-computed shortest path tree to determine the cost of the shortest path from the at least one other node to the multicast source and the cost of the shortest path from the at least one other node to the multicast destination.   
     
     
         30 . The method of  claim 25 , wherein the at least one other node is selected administratively and advertised on the network. 
     
     
         31 . The method of  claim 25 , wherein the at least one other node is self-selected by the node. 
     
     
         32 . The method of  claim 25 , wherein the at least one node is selected from a predetermined set of nodes, the predetermined set not including some nodes of the routed network. 
     
     
         33 . The method of  claim 32 , wherein the predetermined set of nodes is selected such that a majority of shortest paths between nodes in the routed network include nodes that are in the predetermined set of nodes. 
     
     
         34 . The method of  claim 25 , wherein the shortest paths are determined based on a cost metric selected from cost, capacity, availability, and reliability. 
     
     
         35 . A node for a routed network, the node being adapted to limit multicast forwarding state, the node comprising:
 at least one processor; and   at least one storage element storing instructions for execution by the at least one processor, the instructions comprising instructions executable by the at least one processor:   to receive, at the node, a link state advertisement containing an indication that a multicast destination would like to join a multicast;   to determine respective costs of a shortest path from the node to a multicast source and of a shortest path from the node to the multicast destination;   to determine respective costs of a shortest path from at least one other node to the multicast source and of a shortest path from the at least one other node to the multicast destination; and   to not install forwarding state for forwarding multicast traffic from the multicast source to the multicast destination, by the node, when the sum of the cost of the shortest path from the node to the multicast source and the cost of the shortest path from the node to the multicast destination is greater than the sum of the cost of the shortest path from the at least one other node to the multicast source and the cost of the shortest path from the at least one other node to the multicast destination.   
     
     
         36 . The node of  claim 35 , wherein the at least one other node is neither the multicast source nor the multicast destination. 
     
     
         37 . The node of  claim 35 , wherein the respective costs of the shortest path from the at least one other node to the multicast source and of the shortest path from the at least one other node to the multicast destination are strictly positive. 
     
     
         38 . The node of  claim 35 , wherein the instructions comprise:
 instructions executable to pre-compute a shortest path tree from the node to each other node on the network; and   instructions executable to use the pre-computed shortest path tree to determine the cost of the shortest path from the node to the multicast source and the cost of the shortest path from the node to the multicast destination.   
     
     
         39 . The node of  claim 35 , wherein the instructions comprise:
 instructions executable to pre-compute a respective shortest path tree from the at least one other node to each other node on the network; and instructions executable to use the pre-computed shortest path tree to determine the cost of the shortest path from the at least one other node to the multicast source and the cost of the shortest path from the at least one other node to the multicast destination.   
     
     
         40 . The node of  claim 35 , wherein the instructions comprise instructions executable to receive an advertisement identifying the at least one other node when the at least one other node is selected administratively and advertised on the network. 
     
     
         41 . The node of  claim 35 , wherein the instructions comprise instructions executable to cause the node to self-select the at least one other node. 
     
     
         42 . The node of  claim 35 , wherein instructions comprise instructions executable to determine the shortest paths are determined based on a cost metric selected from cost, capacity, availability, and reliability.