Address routing using address-sensitive mask decimation scheme
US6223172A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 29, 1998 |
| Grant date | Apr 24, 2001 |
| Priority date | — |
| Expiry date | Jun 29, 2018 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99933
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for efficiently performing a longest match search are provided. According to one aspect of the present invention, an entry in a forwarding database, a routing table, or the like is located using an improved longest match search. A mask is applied to an address, such as a destination Internet Protocol (IP) address, to determine a masked address that is to be used for purposes of locating a matching entry in the forwarding database. The forwarding database is searched for an entry that matches the masked address. Subsequent masks are produced by performing an address-sensitive decimation of the former mask. For example, the former mask may be shortened based upon the location of the least significant bit containing a one in the masked address. According to another aspect of the present invention, data forwarding employs the improved longest match search. Data is received at a port. An address is extracted from the data. A forwarding database is searched for a longest match for the address by comparing a portion of the address indicated by a mask to entries in the forwarding database and using progressively shorter masks, determined based upon the masked address…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.