Techniques for efficiently updating routing information
View Patent ↗Techniques for efficiently updating routing information in a network device such as a router. According to an embodiment of the present invention, the routing information is updated upon creation or deletion of an overlay tunnel without the network device having to regenerate a Shortest Path Tree (SPT) by performing full Shortest Path First (SPF) processing.
1. A system comprising:
a memory configured to:
store routing information used by the system for forwarding a packet from the system; and
store information for a shortest path tree (SPT) generated by the system, the SPT comprising a first node and a second node; and
a processor configured to:
determine a first cost metric indicative of a cost for communicating data from the first node to the second node via a path from the first node to the second node in the SPT, the first cost metric determined based upon the generated SPT;
receive, after the SPT has been generated, tunnel information identifying a tunnel starting at the first node and ending at the second node, the tunnel information including a second cost metric indicative of a cost for communicating data from the first node to the second node using the tunnel; and
update the routing information without regenerating the SPT upon determining that the second cost metric is equal to or greater than the first cost metric.
2. The system of claim 1 wherein the processor is configured to:
determine a list of one or more nodes from the SPT that are descendant nodes of the second node in the SPT; and
update the routing information without regenerating the SPT based upon the list of one or more nodes from the SPT that are descendants of the second node in the SPT.
3. The system of claim 1 wherein the processor is configured to:
determine, for the second node, a list of one or more nodes from the SPT that are child nodes of the second node in the SPT; and
determine an update to be made to the routing information based upon the determined list of one or more nodes from the SPT that are child nodes of the second node in the SPT.
4. The system of claim 3 wherein the processor is configured to:
for a first child node in the list of one or more nodes from the SPT that are child nodes of the second node in the SPT:
determine a third cost metric indicative of a cost of communicating data from the first node to the first child node via a path in the SPT from the first node to the first child node;
determine a fourth cost metric indicative of a cost of communicating data from the first node to the first child node via the tunnel; and
compare the third cost metric with the second cost metric.
5. The system of claim 4 wherein the processor is configured to, upon determining that the third cost metric is equal to the second cost metric, determine, for the first child node, a list of one or more nodes from the SPT that are child nodes of the first child node in the SPT.
6. The system of claim 1 wherein the tunnel is an Multiprotocol Label Switching (MPLS) tunnel.
7. A method comprising:
storing, by a network device, information for a shortest path tree (SPT), the SPT comprising a first node and a second node;
determining, by the network device, a first cost metric indicative of a cost for communicating data from the first node to the second node via a path from the first node to the second node in the SPT, the first cost metric determined based upon the generated SPT;
receive, by the network device, after the SPT has been generated, tunnel information identifying a tunnel starting at the first node and ending at the second node, the tunnel information including a second cost metric indicative of a cost for communicating data from the first node to the second node using the tunnel; and
updating, by the network device, the routing information without regenerating the SPT upon determining that the second cost metric is equal to or greater than the first cost metric.
8. The method of claim 7 further comprising:
determining, by the network device, a list of one or more nodes from the SPT that are descendant nodes of the second node in the SPT; and
wherein the updating comprises updating the routing information without regenerating the SPT based upon the list of one or more nodes from the SPT that are descendants of the second node in the SPT.
9. The method of claim 7 further comprising:
determining, by the network device, for the second node, a list of one or more nodes from the SPT that are child nodes of the second node in the SPT; and
determining, by the network device, an update to be made to the routing information based upon the determined list of one or more nodes from the SPT that are child nodes of the second node in the SPT.
10. The method of claim 9 further comprising:
for a first child node in the list of one or more nodes from the SPT that are child nodes of the second node in the SPT:
determining a third cost metric indicative of a cost of communicating data from the first node to the first child node via a path in the SPT from the first node to the first child node;
determining a fourth cost metric indicative of a cost of communicating data from the first node to the first child node via the tunnel; and
comparing the third cost metric with the second cost metric.
11. The method of claim 10 further comprising:
upon determining that the third cost metric is equal to the second cost metric, determining, for the first child node, a list of one or more nodes from the SPT that are child nodes of the first child node in the SPT.
12. The method of claim 7 wherein the tunnel is an Multiprotocol Label Switching (MPLS) tunnel.
13. A non-transitory computer-readable storage medium storing a plurality of instructions for controlling a processor, the plurality of instructions comprising:
instructions that cause the processor to store information for a shortest path tree (SPT), the SPT comprising a first node and a second node;
instructions that cause the processor to determine a first cost metric indicative of a cost for communicating data from the first node to the second node via a path from the first node to the second node in the SPT, the first cost metric determined based upon the generated SPT;
instructions that cause the processor to receive, after generation of the SPT, tunnel information identifying a tunnel starting at the first node and ending at the second node, the tunnel information including a second cost metric indicative of a cost for communicating data from the first node to the second node using the tunnel; and
instructions that cause the processor to update the routing information without regenerating the SPT upon determining that the second cost metric is equal to or greater than the first cost metric.
14. The non-transitory computer-readable storage medium of claim 13 wherein:
the plurality of instructions further comprises instructions that cause the processor to determine a list of one or more nodes from the SPT that are descendant nodes of the second node in the SPT; and
the instructions that cause the processor to update the routing information comprise instructions that cause the processor to update the routing information without regenerating the SPT based upon the list of one or more nodes from the SPT that are descendants of the second node in the SPT.
15. The non-transitory computer-readable storage medium of claim 13 wherein the plurality of instructions further comprises:
instructions that cause the processor to determine, for the second node, a list of one or more nodes from the SPT that are child nodes of the second node in the SPT; and
instructions that cause the processor to determine an update to be made to the routing information based upon the determined list of one or more nodes from the SPT that are child nodes of the second node in the SPT.
16. The non-transitory computer-readable storage medium of claim 15 wherein the plurality of instructions further comprises:
for a first child node in the list of one or more nodes from the SPT that are child nodes of the second node in the SPT:
instructions that cause the processor to determine a third cost metric indicative of a cost of communicating data from the first node to the first child node via a path in the SPT from the first node to the first child node;
instructions that cause the processor to determine a fourth cost metric indicative of a cost of communicating data from the first node to the first child node via the tunnel; and
instructions that cause the processor to compare the third cost metric with the second cost metric.
17. The non-transitory computer-readable storage medium of claim 16 further comprising:
upon determining that the third cost metric is equal to the second cost metric, instructions that cause the processor to determine, for the first child node, a list of one or more nodes from the SPT that are child nodes of the first child node in the SPT.
18. The non-transitory computer-readable storage medium of claim 13 wherein the tunnel is an Multiprotocol Label Switching (MPLS) tunnel.