Enhanced searching method and apparatus for variable bit chains
US6421660B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 18, 1998 |
| Grant date | Jul 16, 2002 |
| Priority date | — |
| Expiry date | Dec 18, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present method and apparatus provide a searching operation of variable bit chain keys, the implementation being possible in software and cost effective in hardware. When implemented in the network routers, this solution sustains performance required for routing IPV4 OR IPV6 datagrams node insert and delete operations maintain the data base with no need for further garbage collection. The Extended patricia tree data structure of the invention the determination in advance of the process time and the storage resources which will be used. Variable bit chain keys padded with zeros and their prefix length are stored in the extended patricia tree. A search is performed in two parts, a first up-down displacement in the tree followed by a down-up displacement to find the key stored in one node in the tree having the longest matching prefix with the key to be searched.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.