Network device, storage medium and methods for incrementally updating a forwarding database
View Patent ↗Network devices, storage mediums and methods for updating a memory structure in a data plane of the network device when route updates are received in the control plane of the network device. The methods described herein can be used to perform one of the following algorithms: a Basic Incremental Split-Merge (BISM) algorithm, a Lazy Incremental Split-Merge (LISM) algorithm, and a Down-support Split-Merge (DSM) algorithm. Each of the algorithms described herein may be used to incrementally update portions of a forwarding database stored within the memory structure, where the updated portions correspond to only those portions affected by the route updates.
1. A method for updating a forwarding database that includes a total number N of prefixes, the method comprising:
forming a hierarchical binary tree structure having root, branch and leaf nodes that define (i) at least a minimum number N/T of sub-databases of the forwarding database and (ii) respective bit combinations associated with the sub-databases, wherein each prefix of the N prefixes is stored within one of the sub-databases having an associated bit combination that matches corresponding bits within the prefix, and wherein each of the sub-databases has no more than a predetermined maximum number T of prefixes, and at least one of the sub-databases includes a plurality of the prefixes that are not stored in any of the other sub-databases;
modifying the hierarchical tree structure in accordance with one or more update operations; and
updating one or more of the sub-databases to reflect modifications made to the hierarchical tree structure, wherein the one or more updated sub-databases correspond to only those portions of the hierarchical tree affected by the update operations.
2. The method of claim 1 , wherein said forming comprises, beginning with a most significant bit of the N number of prefixes, repeatedly splitting the N number of prefixes into a plurality of nodes extending between and including a root node and a plurality of leaf nodes, and wherein each of the leaf nodes corresponds to one of the sub-databases.
3. The method of claim 2 , wherein said modifying comprises performing the update operations on one or more of the plurality of leaf nodes, wherein the update operations are selected from a group comprising: adding a new prefix to the forwarding database, deleting an existing prefix from the forwarding database and modifying an existing prefix in the forwarding database.
4. The method of claim 3 , wherein said modifying further comprises performing the update operations on one or more of the branch nodes.
5. The method of claim 3 , wherein said modifying further comprises:
splitting, into at least one additional pair of leaf nodes, a leaf node associated with a sub-database to which a new prefix is to be added and which, upon adding the new prefix would contain more than T prefixes; and
merging, with a branch node, a leaf node associated with a sub-database which, upon completion of an update operation, would be left with fewer than a predetermined number of prefixes.
6. The method of claim 5 , wherein said merging is performed if either (i) a total number of sub-databases defined by the hierarchical tree structure would be, absent said merging, greater than a predetermined number, or (ii) a predetermined time period has passed, in which no merging was performed.
7. The method of claim 6 , wherein said merging further comprises repeatedly merging the leaf node and the branch node up towards the root node if the total number of prefixes within the leaf node, the branch node and any subsequently merged branch nodes remains less than the minimum number of prefixes.
8. The method of claim 5 , wherein said merging is performed only if no other node exists below the branch node that can be paired with the leaf node, such that the combined number of prefixes within the leaf node and the other node is greater than T.
9. The method of claim 8 , wherein said merging is performed no more than one time in response to an update operation.
10. A computer-readable storage medium having recorded therein one or more sequences of instructions which, when executed by a processor, cause the processor to update a forwarding database having a total number N of prefixes, including causing the processor to:
form a hierarchical binary tree structure having root, branch and leaf nodes that define (i) at least a minimum number N/T of sub-databases of the forwarding database and (ii) respective bit combinations associated with the sub-databases, wherein each prefix of the N prefixes is stored within one of sub-databases having an associated bit combination that matches corresponding bits within the prefix, and wherein each of the sub-databases has no more than a predetermined maximum number T of prefixes, and at least one of the sub-databases includes a plurality of the prefixes that are not stored in any of the other sub-databases;
modify the hierarchical tree structure in accordance with one or more update operations; and
update one or more of the sub-databases to reflect modifications made to the hierarchical tree structure, wherein the one or more updated sub-databases correspond to only those portions of the hierarchical tree affected by the update operations.
11. The computer readable storage medium of claim 10 , wherein the computer readable storage medium is directly coupled to, or incorporated within, the processor, and wherein at least a portion of the sub-databases are contained within the computer readable storage medium.
12. The computer readable storage medium of claim 11 , wherein the computer readable storage medium comprises random access memory.
13. The computer readable storage medium of claim 11 , wherein the computer-readable storage medium comprises one or more of a random access memory, a content-addressable memory, or a network search engine (NSE).