Method and apparatus for minimizing calculations required to construct multicast trees
First Claim
1. A method of maintaining a multicast tree, the method comprising:
- calculating forwarding entries of the multicast tree;
identifying a change associated with a particular network area;
recalculating forwarding entries in the particular network area in response to identifying the change; and
recalculating forwarding entries affected by changed summary information in other areas in response to identifying the change, wherein the changed summary information results from the identified change.
10 Assignments
0 Petitions
Accused Products
Abstract
A system is provided for recalculating multicast trees by identifying a network change associated with a network area. In response to the network change, forwarding entries in the network area are recalculated. Additionally, the system recalculates forwarding entries affected by the changed summary information in other areas resulting from the identified change. Forwarding entries associated with a group may be recalculated in response to receiving a new group membership link state advertisement (LSA). The system determines whether the originator of the LSA is reachable from a calculating router. If the LSA is reachable from the calculating router, then the forwarding entries associated with the group are recalculated. If the LSA is not reachable from the calculating router, then the forwarding entries associated with the group are not recalculated. Additionally, multicast tree construction can be terminated if all of the calculating router'"'"'s interfaces that have adjacent neighbors have been added to the forwarding table for the tree, or if all of the calculating router'"'"'s downstream vertices have been added to a candidate list. Multicast tree construction may also be terminated if all of the reachable group membership LSAs for the tree have been considered.
97 Citations
58 Claims
-
1. A method of maintaining a multicast tree, the method comprising:
-
calculating forwarding entries of the multicast tree;
identifying a change associated with a particular network area;
recalculating forwarding entries in the particular network area in response to identifying the change; and
recalculating forwarding entries affected by changed summary information in other areas in response to identifying the change, wherein the changed summary information results from the identified change. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method for maintaining multicast trees, the method comprising:
-
calculating forwarding entries of the multicast trees;
receiving a new group membership link state advertisement (LSA) associated with a group;
determining whether the originator of the new group membership LSA is reachable from a calculating router; and
if the originator of the new group membership LSA is reachable from the calculating router recalculating forwarding entries associated with the group in response to receiving the new group membership LSA, otherwise, maintaining forwarding entries associated with the group without the recalculating of forwarding entries. - View Dependent Claims (9, 10, 11, 12)
-
-
13. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
determining the number of interfaces having adjacent neighbors;
initializing a value in a counter to the number of interfaces that have adjacent neighbors;
decrementing the value in the counter if an interface is added to a forwarding table; and
terminating construction of the multicast tree if the value in the counter reaches zero. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
the determining the number of interfaces having adjacent neighbors considers only those neighbors in a same area as a calculating router. -
15. The method of claim 13 wherein
the determining the number of interfaces having adjacent neighbors includes counting all neighbors on an interface if the interface is configured to forward multicast packets using link-level unicast. -
16. The method of claim 13 wherein the method is performed by a network routing device.
-
17. The method of claim 13 wherein the method is performed by a switching system product.
-
18. The method of claim 13 wherein the method is performed by a transmission system product.
-
19. The method of claim 13 wherein the counter is an interface-neighbor counter.
-
20. The method of claim 13 further comprising
repeating the determining the number of interfaces that have adjacent neighbors and the initializing the value of the counter with the number, each time the state of an interface changes. -
21. The method of claim 13 wherein
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources.
-
-
22. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
initializing a counter to zero, the counter to count downstream vertexes;
incrementing the counter when a downstream vertex of the calculating router is added to a candidate list;
decrementing the counter when a downstream vertex of the calculating router is moved to the multicast tree from the candidate list; and
terminating construction of the multicast tree when the counter reaches zero. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29)
the counter is a downstream-neighbors counter. -
27. The method of claim 22 further comprising:
incrementing the counter twice for a vertex that is both a router vertex and a network vertex.
-
28. The method of claim 22 wherein
the candidate list is a list of network devices or nodes of vertices. -
29. The method of claim 22 wherein
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources.
-
-
30. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
determining a number of reachable group membership link state advertisements (LSAs) associated with the multicast tree;
initializing a value in a counter to the number of reachable group membership link state advertisements (LSAs) associated with the multicast tree;
decrementing the value in the counter when a group membership LSA is considered; and
terminating construction of the multicast tree when the value in the counter reaches zero. - View Dependent Claims (31, 32, 33, 34)
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources.
-
-
35. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
counting, using a counter, a number of reachable group membership link state advertisements (LSAs) associated with the multicast tree and counting twice each group membership LSA that contains both a router vertex and a network vertex;
decrementing the counter when a group membership LSA is considered; and
terminating construction of the multicast tree when the counter reaches zero. - View Dependent Claims (36, 37)
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources. -
37. The method of claim 35 wherein
the method is preformed by one of a network routing device, a switching system product, or a transmission system product.
-
-
38. A computer software product including a medium readable by a processor to maintain multicast trees, the medium having stored thereon a sequence of instructions which, when executed by the processor, cause the processor to:
-
calculate forwarding entries in a particular network area;
identify a change associated with the particular network area;
recalculate forwarding entries in the particular network area in response to identifying the change; and
recalculate forwarding entries affected by the changed summary information in other areas in response to identifying the chance, wherein the changed summary information results from the identified change. - View Dependent Claims (39, 40)
-
-
41. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
determining the number of vertices in all group membership link state advertisements (LSAs) in the area for a group;
determining the number of reachable wildcard receivers in the area;
determining a sum by summing together the number of vertices in all group LSAs in the area for the group and the number of reachable wildcard receivers in the area;
initializing a value in a counter to the sum;
decrementing the value in the counter if a vertex is listed in a group link state advertisement (LSA); and
terminating construction of the multicast tree if the value in the counter reaches zero. - View Dependent Claims (42, 43, 44)
the counter is a group counter. -
43. The method of claim 41 further comprising:
decrementing the value in the counter if the vertex is a wildcard receiver.
-
44. The method of claim 41 wherein
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources.
-
-
45. A method for determining when to terminate construction of a multicast tree, the method comprising:
-
summing together a number of vertices in all group LSAs in an area for a group and a number of reachable wildcard receivers in the area;
initializing a value in a first counter to the sum;
determining the number of interfaces that have adjacent neighbors;
initializing a value in a second counter to the number of interfaces that have adjacent neighbors;
decrementing the value in the first counter if a vertex is listed in a group link state advertisement (LSA);
decrementing the value in the second counter if an interface is added to a forwarding table; and
terminating construction of the multicast tree if the value in the first counter or the value in the second counter reaches zero. - View Dependent Claims (46, 47, 48)
the first counter is a group counter and the second counter is an interface-neighbor counter. -
47. The method of claim 45 further comprising:
decrementing the value in the first counter if the vertex is a wildcard receiver.
-
48. The method of claim 45 wherein
the Dijkstra algorithm is used to construct the multicast tree and is terminated by the terminating construction of the multicast tree when the value in the counter reaches zero to conserve computational resources.
-
-
49. A method for conserving computation resources in a network device to maintain a network tree, the method comprising:
-
using a Dijkstra algorithm to calculate the network tree in a network area; and
terminating the Dijkstra algorithm early after completion of the network tree in the network area and before completion of the Dijkstra algorithm in order to minimize unnecessary computations. - View Dependent Claims (50, 51, 52, 53, 54, 55, 56, 57, 58)
the network tree is a unicast tree. -
51. The method of claim 49 wherein
the network tree is a multicast tree. -
52. The method of claim 49 wherein
the Dijkstra algorithm is terminated when all of a calculating router'"'"'s interfaces that lead to transit vertices have been placed into a forwarding entry. -
53. The method of claim 49 wherein
the Dijkstra algorithm is terminated when all of a calculating router'"'"'s interfaces that have adjacent neighbors have been added to a forwarding table for the network tree. -
54. The method of claim 49 wherein
the Dijkstra algorithm is terminated before the list of candidates is empty. -
55. The method of claim 49 wherein
the Dijkstra algorithm is terminated when no additional candidates are possible downstream from the calculating router. -
56. The method of claim 49 wherein
the Dijkstra algorithm is terminated when all of a calculating router'"'"'s downstream vertices have been moved to the network tree. -
57. The method of claim 49 wherein
the Dijkstra algorithm is terminated when all reachable group membership link state advertisements have been considered. -
58. The method of claim 49 wherein
the Dijkstra algorithm completes the network tree when all destination nodes have been placed in a path.
-
Specification