Provider link state bridging (PLSB) computation method
View Patent ↗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 neighbor node of the first node and any nodes of the network subtending the neighbor 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. A method of multicast route computation in a link state protocol controlled network, the method comprising:
computing by a first node of the network a spanning tree from the first node to every other node in the network using a known shortest path tree algorithm;
dividing the network into partitions, each partition encompassing an immediate neighbour node of the first node on the computed spanning tree and any nodes of the network subtending the neighbour node on the computed spanning tree;
merging two or more of the partitions when a predetermined criterion is satisfied;
examining nodes within all of the partitions except a largest one of the partitions to identify node pairs for which a respective shortest path traverses the first node.
2. The method as claimed in claim 1 , wherein each one of a first partition and a second partition includes a respective one of the neighbour nodes, and wherein the predetermined criterion is that a shortest path between each of the included neighbour nodes does not traverse the first node.
3. The method as claimed in claim 2 , wherein the shortest path is a direct link.
4. The method as claimed in claim 2 , wherein the shortest path is selected, from a set of two or more equal cost paths between each of the involved neighbour nodes, by a tie-breaking method which is symmetric and locally consistent.
5. The method as claimed in claim 1 , wherein a first partition comprises a respective one of the neighbour nodes and a second partition is a super-partition comprising two or more of the neighbour nodes, and wherein the predetermined criterion is that respective shortest paths between the one neighbour node of the first partition and the two or more neighbour nodes of the second partition, do not traverse the first node.
6. The method as claimed in claim 5 , wherein at least one of the shortest paths is a direct link.
7. The method as claimed in claim 5 , wherein at least one of the shortest paths is selected from a set of two or more equal cost paths between the one neighbour node of the first partition and one of the two or more neighbour nodes of the second partition by a tie-breaking method which is symmetric and locally consistent.
8. The method as claimed in claim 1 , wherein a first partition comprises a respective one of the neighbour nodes and a second partition is a super-partition comprising two or more of the neighbour nodes, the one neighbour node of the first partition being connected to each of the two or more neighbour nodes of the second partition by a respective set of one or more shortest paths, at least one set of shortest paths comprising two or more equal cost paths selected by a tie-breaking method which is symmetric and locally consistent, and wherein the predetermined criterion is that none of the two or more equal cost paths within any given set of shortest paths traverses the first node.
9. A computer software product tangibly embodied on a non-transitive computer readable storage medium, the computer software product implementing a method of multicast route computation in a link state protocol controlled network by controlling a first node of the network to perform the steps of:
computing a spanning tree from the first node to every other node in the network using a known shortest path tree algorithm;
dividing the network into partitions, each partition encompassing an immediate neighbour node of the first node on the computed spanning tree and any nodes of the network subtending the neighbour node on the computed spanning tree;
merging two or more of the partitions when a predetermined criterion is satisfied;
examining nodes within all of the partitions except a largest one of the partitions to identify node pairs for which a respective shortest path traverses the first node.
10. The computer software product as claimed in claim 9 , wherein each one of a first partition and a second partition includes a respective one of the neighbour nodes, and wherein the predetermined criterion is that a shortest path between each of the included neighbour nodes does not traverse the first node.
11. The computer software product as claimed in claim 10 , wherein the shortest path is a direct link.
12. The computer software product as claimed in claim 10 , wherein the shortest path is selected, from a set of two or more equal cost paths between each of the involved neighbour nodes, by a tie-breaking method which is symmetric and locally consistent.
13. The computer software product as claimed in claim 9 , wherein a first partition comprises a respective one of the neighbour nodes and a second partition is a super-partition comprising two or more of the neighbour nodes, and wherein the predetermined criterion is that respective shortest paths between the one neighbour node of the first partition and the two or more neighbour nodes of the second partition, do not traverse the first node.
14. The computer software product as claimed in claim 13 , wherein at least one of the shortest paths is a direct link.
15. The computer software product as claimed in claim 13 , wherein at least one of the shortest paths is selected from a set of two or more equal cost paths between the one neighbour node of the first partition and one of the two or more neighbour nodes of the second partition by a tie-breaking method which is symmetric and locally consistent.
16. The computer software product as claimed in claim 9 , wherein a first partition comprises a respective one of the neighbour nodes and a second partition is a super-partition comprising two or more of the neighbour nodes, the one neighbour node of the first partition being connected to each of the two or more neighbour nodes of the second partition by a respective set of one or more shortest paths, at least one set of shortest paths comprising two or more equal cost paths selected by a tie-breaking method which is symmetric and locally consistent, and wherein the predetermined criterion is that none of the two or more equal cost paths within any given set of shortest paths traverses the first node.