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:
Aug. 10, 2004
Filed:
Oct. 09, 2001
Priyank Ramesh Warkhede, Santa Clara, CA (US);
William N. Eatherton, San Jose, CA (US);
Shyamsundar N. Maniyar, San Jose, CA (US);
Peram Marimuthu, Sunnyvale, CA (US);
Cisco Technology, Inc., San Jose, CA (US);
Abstract
Methods and apparatus are disclosed for allocating and using range identifiers as input values to associative memories, especially binary content-addressable memories (CAMs) and ternary content-addressable memories (TCAMs). In one implementation, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result. One implementation uses a trie representation of a range tree of the intervals to derive the unique identifiers. Moreover, one implementation evaluates and selects among various possible trie representations, especially to determine identifiers such that a TCAM prefix may match multiple intervals corresponding to a desired range.