The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jan. 29, 2002
Filed:
Jul. 17, 1998
Van A. Hunter, San Jose, CA (US);
Milan Momirov, San Francisco, CA (US);
Nortel Networks Limited, St. Laurent, CA;
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 memory that is associated with a database entry and subsequent requests may be made in a pipelined manner to load subsequent keys, whereby the memory is caused to access keys of different entries during consecutive clock cycles.