Provider link state bridging (plsb) computation method

Abstract

A method of multicast route computation in a link state protocol controlled network. A spanning tree is computed from a first node to every other node in the network using a known spanning tree protocol. The network is then divided into two or more partitions, each partition encompassing an immediate neighbour node of the first node and any nodes of the network subtending the neighbour node on the spanning tree. Two or more of the partitions are merged when a predetermined criterion is satisfied. Nodes within all of the partitions except a largest one of the partitions are then identified, and each identified node examined to identify node pairs for which a respective shortest path traverses the first node.

1 - 8 . (canceled) 
     
     
         9 . A forwarding node for a link state protocol controlled communication network, the forwarding node comprising:
 a plurality of communication interfaces for connection to immediate neighbour nodes of the forwarding node via links of the communication network;   at least one processor; and   at least one storage element storing instructions executable by the at least one processor, the instructions comprising:
 instructions executable to compute a spanning tree from the forwarding node to every other node in the network using a shortest path algorithm; 
 instructions executable to divide the network into partitions, each partition encompassing an immediate neighbor node of the forwarding node on the computed spanning tree and any other nodes on any branches extending from that immediate neighbor node on the computed spanning tree; and 
 instructions executable to examine nodes within all but a selected partition to identify node pairs for which a respective shortest path traverses the forwarding node. 
   
     
     
         10 . The forwarding node of  claim 9 , wherein each partition encompasses a respective number of nodes and the instructions comprise instructions executable to select a partition encompassing a largest number nodes as the selected partition. 
     
     
         11 . The forwarding node of  claim 9 , wherein the instructions comprise instructions executable to merge at least two of the partitions satisfying at least one predetermined merge criterion before selecting the selected partition. 
     
     
         12 . The forwarding node of  claim 11 , wherein:
 a first partition comprises a first immediate neighbor node of the forwarding node on the computed spanning tree;   a second partition comprises a second immediate neighbor node of the forwarding node on the computed spanning tree; and   the first and the second partitions satisfy a predetermined merge criterion when a shortest path between the first immediate neighbor node and the second immediate neighbor node does not traverse the forwarding node.   
     
     
         13 . The forwarding node of  claim 12 , wherein:
 the instructions executable to compute the shortest path tree comprise instructions executable, when multiple equal cost shortest paths exist between the first immediate neighbor node and the second immediate neighbor node, to select a shortest path using a symmetric, locally consistent tie-breaking method; and   the instructions executable to merge at least two of the partitions comprise instructions executable to evaluate the predetermined merge criterion using the selected shortest path.   
     
     
         14 . The forwarding node of  claim 12 , wherein the instructions executable to merge at least two of the partitions comprise instructions executable to merge the first partition and the second partition to form a super-partition. 
     
     
         15 . The forwarding node of  claim 11 , wherein:
 a first partition comprises a first immediate neighbor node of the forwarding node on the computed spanning tree;   a second partition is a super-partition comprising at least two immediate neighbor nodes of the forwarding node on the computed spanning tree; and   the first and second partitions satisfy a predetermined merge criterion when each respective shortest path between the first immediate neighbor node of the forwarding node in the partition and each of the at least two immediate neighbor nodes of the forwarding node in the super-partition does not traverse the forwarding node.   
     
     
         16 . The forwarding node of  claim 15 , wherein:
 the instructions executable to compute the spanning tree comprise instructions executable, when multiple equal cost shortest paths exist between a pair of nodes comprising one immediate neighbor node of the forwarding node in the partition and one immediate neighbor node of the forwarding node in the super-partition, to select a respective shortest path using a symmetric, locally consistent tie-breaking method; and   the instructions executable to merge at least two of the partitions comprise instructions to evaluate the predetermined merge criterion using the selected respective shortest path.   
     
     
         17 . The forwarding node of  claim 15 , wherein the instructions executable to merge at least two of the partitions comprise instructions executable to merge the first partition and the second partition to form another super-partition. 
     
     
         18 . The forwarding node of  claim 9 , wherein the instructions executable to compute the spanning tree comprise instructions executable to select from each set of at least two equal cost paths between a pair of nodes a respective one of the equal cost paths as a shortest path between the pair of nodes, the selections being symmetric and locally consistent. 
     
     
         19 . The forwarding node of  claim 9 , wherein the instructions comprise instructions executable to compute multicast routes.