Multiple parallel packet routing lookup
US6212183A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Aug 22, 1997 |
| Grant date | Apr 3, 2001 |
| Priority date | — |
| Expiry date | Aug 22, 2017 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/16
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
The invention provides a method and system for routing information lookup for packets using a routing protocol such as IP. Routing information which has been determined responsive to the packet header, which includes a destination address, a source address, and an input interface for the packet. Routing lookup is performed in response to at least one set of selected routing information, using a lookup table which includes tags both for the routing information and for a bitmask length (thus indicating the generality or scope of the routing information for the routing lookup). The lookup table is structured so that addresses having the most common bitmask length are addressed first, but that more specific addresses are still considered when they are present. It has been discovered that most internet addresses can be found by reference to 24-bit or 21-bit IP addresses, after which 16-bit, 12-bit, and finally 32-bit IP addresses are considered. Lookup flags indicate when a relatively uncommon but more specific 32-bit IP address match is available. A memory controller pipelines the lookup requests to a hash table memory, flushes superfluous requests when a lookup result is found, and ha…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.