System and Method for Updating State Information in a Router
First Claim
1. A method in a data processing system for dynamically updating routing table information, the data processing system including a router connected to a network and having a memory storing a routing table including routing table entries for links in the network, the method comprising the steps of:
- determining that the routing table requires an update;
determining whether the router has available resources;
performing a routing table update in accordance with a first update method when the router is determined to have available resources sufficient for the update, wherein the first update method includes adding a new entry for one of the links in the network before deleting an old entry for the one link in the network; and
performing a routing table update in accordance with a second update method that is different from the first update method when the router is determined to have insufficient resources for the update, wherein the second update method includes deleting the old entry for the one link from the routing table before adding the new entry to the routing table for the one link.
2 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods consistent with the present invention enable routing table updates are performed by optimally utilizing the resources of a node without exceeding the resources of the node. Using feedback on the amount of resources available to the nodes, such as in terms of available memory, the node may make new connections before breaking old one where those updates will not exceed available resources. This is referred to as make-before-break. When not enough resources are available, the node will break old connections before making new ones. This is referred to as break-before-make. Unlike the strict make-before-break and break-before-make models, this “loose” make-before-break method considers the amount of available resources in view of the resources required to perform the routing table updates without a node failure. Routes may also be tagged to prioritize the addition of more important routes and the deletion of less significant routes. Methods and systems consistent with the present invention, therefore, provide a routing table update method with which routing table updates are achieved without crashing and at the same time minimizing black hole intervals.
27 Citations
20 Claims
-
1. A method in a data processing system for dynamically updating routing table information, the data processing system including a router connected to a network and having a memory storing a routing table including routing table entries for links in the network, the method comprising the steps of:
-
determining that the routing table requires an update; determining whether the router has available resources; performing a routing table update in accordance with a first update method when the router is determined to have available resources sufficient for the update, wherein the first update method includes adding a new entry for one of the links in the network before deleting an old entry for the one link in the network; and performing a routing table update in accordance with a second update method that is different from the first update method when the router is determined to have insufficient resources for the update, wherein the second update method includes deleting the old entry for the one link from the routing table before adding the new entry to the routing table for the one link. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer-readable medium storing computer executable instructions for performing a method of dynamically updating routing table information in a router connected to a network and having a memory storing a routing table including routing table entries for links in the network, the method comprising the steps of:
-
ranking entries in the routing table; determining that the routing table requires an update; determining whether the router has sufficient available resources to perform the update; performing a routing table update in accordance with a first update method when the router is determined to have available resources sufficient for the update, wherein entries are updated in order of rank, and wherein the first update method includes adding a new entry for the link in the routing table before deleting an old entry for the link from the routing table; and performing a routing table update in accordance with a second update method when the router is determined to have insufficient resources for the update, wherein entries are updated in order of rank, and wherein the second update method includes deleting the old entry for the link from the routing table before adding the new entry for the link to the routing table. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A data processing system including a router for dynamically updating routing table information, the router connected to a network and comprising:
-
a memory comprising; a routing table including routing table entries for associated links in the network; and a computer program that determines the number of routing table entries to be updated, determines the amount of resources available to the router, updates an old routing table entry by creating a new routing table entry for the associated link before deleting the old routing table entry for the link while the amount of available resources is sufficient, and updates the old routing table entry by deleting the old routing table entry for the link before creating the new routing table entry for the link when the amount of available resources is insufficient; and a processor for executing the computer program.
-
Specification