Scalable high speed IP routing lookups
US6018524A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 9, 1997 |
| Grant date | Jan 25, 2000 |
| Priority date | — |
| Expiry date | Sep 9, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for an exponentially faster technique than is presently utilized in routers for looking-up destination addresses and matching them to a prefix in order to determine an output data link for routing of the data message to a destination. The basic algorithm includes arranging the prefix and corresponding output data link information in sub-databases arranged by prefix length and then using a multi-step prefix length binary search algorithm to sort through the sub-databases to determine a best matching prefix for routing of the data packet. Various refinements of the basic algorithm are disclosed to further enhance the search time including adding markers representative of sub-database entries having a longer prefix length and also various searching methodologies to minimize the number of searching steps including rope searching in various formats. Thus, methodologies are disclosed for building the sub-databases, as appropriate to implement the corresponding novel search routines and perform the novel search routines themselves, and the router which implements all of the foregoing. Many of the inventive features disclosed herein are applicable to other routing DP…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.