Dynamic tree bitmap for IP lookup and update
AssigneeUniversity of Florida Research Foundation, Inc.
InventorsSartaj Kumar Sahni, Haibin Lu
Life of this patent
Estimating the term…
Abstract
The subject invention provides a data structure and method for IP lookups, insertions, and deletions using a dynamic tree bitmap structure (DTBM) that utilizes an array of child pointers for each node instead of the typical TBM approach using one pointer to an array of children.
Claims14
A method for inserting a prefix using a dynamic treebitmap (DTBM) data structure whose stride is s, said DTBM including a prefix bitmap for representing a sub-trie, a next hop array, an array of child pointers, and a count of the number of non-null children, wherein the prefix bitmap, the next hop array, the array of child pointers, and the count of the number of non-null children represent a node of the sub-trie, wherein each node stores an internal bitmap (IBM), the method comprising:
- walking through the DTBM one node at a time to find an appropriate node to insert the prefix, where the walk consumes s bits of the prefix;
- if during the walk the prefix has fewer than s bits left, the remaining bits of the prefix less than s bits are used to insert the prefix into the last node encountered;
- and
- if an appropriate node does not exist, new nodes are added to the DTBM until fewer than s bits are left in the prefix, where the remaining bits of the prefix less than s bits are used to insert the prefix into the last node encountered.
A method for deleting a prefix using a dynamic treebitmap (DTBM) data structure including a prefix bitmap for representing a sub-trie, a next hop array, an array of child pointers, and a count of the number of non-null children, wherein the prefix bitmap, the next hop array, the array of child pointers, and the count of the number of non-null children represent a node of the sub-trie, wherein each node stores an internal bitmap (IBM), the method comprising:
- searching the DTBM for a node that contains the prefix;
- and
- if the prefix is found in the DTBM, the prefix is removed from the node,
- wherein if the IBM of the node is zero and the node has no children, then the node along with its continuous ancestors with count equal to 1 and IBM equal to zero are deleted.
A method for memory management using a dynamic treebitmap (DTBM) data structure including a prefix bitmap for representing a sub-trie, a next hop array, an array of child pointers, and a count of the number of non-null children, wherein the prefix bitmap, the next hop array, the array of child pointers, and the count of the number of non-null children represent a node of the sub-trie, wherein each node stores an internal bitmap (IBM), the method comprising:
- using a single chain of free nodes, where each node on the single chain is of the same size;
- allocating a node by removing the first node on a chain;
- and
- deallocating a node by adding the deallocated node to the front of a chain, where all memory is initialized to zero and whenever a node is deallocated, all of its children fields are zero.
A method for memory management using a dynamic treebitmap (DTBM) data structure including a prefix bitmap for representing a sub-trie, a next hop array, an array of child pointers, and a count of the number of non-null children, wherein the prefix bitmap, the next hop array, the array of child pointers, and the count of the number of non-null children represent a node of the sub-trie, wherein each node is a 28-word node and packs several leaves, the method comprising:
- designating the 28-word nodes as the root of the DTBM;
- and
- representing the DTBM root by storing its IBM in a register and its nextHop fields in predetermined memory locations,
- wherein the 28-word node is a type A node and may be partitioned into type B nodes and type C nodes.
Dependencies are inferred from the claim text.