Efficient search and organization of a forwarding database or the like
US6343289B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jul 17, 1998 |
| Grant date | Jan 29, 2002 |
| Priority date | — |
| Expiry date | Jul 17, 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 searching a forwarding database or similar data structure are provided. According to one aspect of the present invention, the overall average time required to forward a packet from the ingress port of a network device to one or more egress ports may be reduced by attacking the worst case forwarding database search. Data is received at a first port of the network device and a search key is extracted from the data. Typically the search key includes one or more of a source or destination Internet Protocol (IP) address, a souce or destination Media Access Control (MAC) address, and/or a Virtual Local Area Network (VLAN) tag. Ultimately, the data is forwarded to a second port of the network device based upon a matching entry located by the search. The search includes retrieving keys from entries of the forwarding database and comparing the search key to the keys until a matching entry is located. The retrieval includes causing a pipelined memory in which the forwarding database is stored to access memory locations in an order that minimizes a worst case search of the forwarding database. For example, a request is made to load a first key from memor…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.