Patent ID: 7571156
Filing Date: 2009-08-04
Classification: H04L,Y10S

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