Patent ID: 8284787
Filing Date: 2012-10-09
Classification: H04L

Abstract:
1. 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.