Method and apparatus for generating and using enhanced tree bitmap data structures in determining a longest prefix match
US7899067B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 31, 2002 |
| Grant date | Mar 1, 2011 |
| Priority date | — |
| Expiry date | Mar 15, 2031 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Methods and apparatus are disclosed for generating and using an enhanced tree bitmap data structure in determining a longest prefix match, such as in a router, packet switching system. One implementation organizes the tree bitmap to minimize the number of internal nodes that must be accessed during a lookup operation. A pointer is included in each of the trie or search nodes to the best match so far entry in the leaf or results array which allows direct access to this result without having to parse a corresponding internal node. Moreover, one implementation stores the internal node for a particular level as a first element in its child array. Additionally, one implementation uses a general purpose lookup engine that can traverse multiple tree bitmaps or other data structures simultaneously, and perform complete searches, partial searches, and resume partial searches such as after receiving additional data on which to search.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.