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, 2008
Filed:
May. 15, 2003
David Richard Barach, Boxborough, MA (US);
Bobby Batacharia, Brookline, MA (US);
David Richard Barach, Boxborough, MA (US);
Bobby Batacharia, Brookline, MA (US);
Cisco Technology, Inc., San Jose, CA (US);
Abstract
The present invention provides a technique for efficiently looking up address-routing information in an intermediate network node, such as a router. To that end, the node locates routing information stored in its memory using one or more 'lookup' tables (LUT) which can be searched using a small, bounded number of dependent lookups, thereby reducing the number of dependent lookups conventionally performed. The LUTs are arranged so each table provides routing information for network addresses whose subnet mask lengths are within a different range ('stride') of mask lengths. According to the technique, the node locates a network address's routing information by searching the LUTs, in order of decreasing prefix lengths, until the routing information is found. Preferably, several tables are searched in parallel. A match in a LUT may further point to a small MTRIE that enables the final bits of a prefix to be matched. That final MTRIE is searched using a relatively small, bounded number of dependent lookups.