Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-05-09
2003-06-03
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C712S224000, C712S244000, C710S049000, C710S048000, C710S262000, C710S266000, C365S189070, C365S230060
Reexamination Certificate
active
06574702
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to content addressable memory (CAM) devices.
BACKGROUND
The Internet Protocol (IP) is used to relay packets of information in the Internet. IPv4 is a common addressing scheme that includes a 32-bit binary address represented in dotted decimal notation of the form M.N.O.P where M, N,
0
, and P are decimal values ranging from 0 to 255. The 32-bit address is segmented into Network and Host address fields and can be implemented in a classfull or classless model. In the classfull model, the IPv4 address is segmented into Class A, B, and C addresses each having a number of the 32 bits designated for the Network address field and the remainder of the 32 bits designated for the Host address field. The classfull scheme has generally resulted in wasted addresses and large IP address tables.
In the Classless Inter Domain Routing (CIDR) scheme, the traditional classfull segmentation is replaced with an IP address that has a generalized network prefix that generally ranges from 13 to 27 bits of the 32-bit IPv4 address. The network prefix or mask indicates the number of left-most contiguous bits in the IP address that are used to filter an IP address in a routing table. That is, the network prefix indicates the number of higher-order or left-most contiguous bits in the IP address that participate in an address comparison with the routing table. A CIDR address is typically written as the IPv4 address followed by “/Z” where Z indicates the prefix length in decimal notation. An IPv4 address followed by the prefix length /Z will hereafter be referred to as a “CIDR address”.
Routing table entries typically include the IP addresses and their corresponding prefixes.
FIG. 1
shows a routing table having five CIDR addresses where an “X” entry indicates that these bits do not participate in a search with a search key. Any search key whose most significant eight bits have the decimal equivalent of 168 will potentially match all of the entries. For example, 168.0.0.0/8, 168.64.0.0/12, and 168.69.0.0/16 all match the search key of 168.69.43.100. However, it is desirable that a search would yield 168.69.0.0/16 as this entry has the largest number of unmasked most significant bits that match the search key.
Routing table entries are typically stored in a CAM device that can rapidly perform a search against the search key to locate the longest matching CIDR address. As there may be multiple matching entries, CAM devices typically include a priority encoder that selects a matching entry that has the lowest logical or numerical address in the CAM array. For example, if a CAM device stores the table of
FIG. 1
in a prearranged order such that 168.69.62.0/24 is stored in a lower logical address than 168.0.0.0/8 (as shown in FIG.
1
), then the CAM device would correctly indicate the longest matching CIDR address as 168.69.0.0/16. If, however, the entries were stored in an arbitrary manner as indicated in
FIG. 2
, then the CAM device would incorrectly indicate a match of 168.64.0.0/12 as this entry is located at a lower logical address than 168.69.0.0/16 and 168.0.0.0/8. 168.64.0.0/12 is not, however, the longest matching CIDR address. Thus, CIDR addresses are generally pre-sorted or prearranged prior to entry into a CAM device such that the CIDR address with the longest network prefix is located in the lowest logical address of the CAM device, and the CIDR address with the shortest network prefix is located in the highest logical address of the CAM device.
A considerable amount of time is generally required to prearrange all of the CIDR address entries prior to loading the entries into a CAM device. Additionally, a considerable amount of time and overhead is also generally required to maintain the order of the routing table when entries are deleted or overwritten, or when new entries are to be added. A typical routine for updating the table includes a bubble sorting algorithm that generally takes many clock cycles to read the entries in the table, compare the entries, and then reload the table. Another approach segments the CAM array into separately addressable hierarchical blocks that each store entries associated only with certain prefixes. However, this approach has the disadvantages of wasting unused CAM locations, and of limiting the number of entries into any one block. This approach also requires that the CAM array be loaded with CIDR addresses in a prearranged fashion.
SUMMARY OF THE INVENTION
A method and apparatus for determining a longest prefix match in a content addressable memory (CAM) device is described. The CAM device includes a CAM array that may be arbitrarily loaded with CIDR addresses that are not prearranged prior to their entry into the CAM device. For one embodiment, the CAM array is a ternary CAM array that includes CAM cells storing CAM data, mask cells storing prefix mask data for the corresponding CAM cells, a CAM match line for indicating a match between a search key and the CAM data (as masked by the prefix mask data), prefix match lines, and prefix logic circuits for comparing the CAM match line with the prefix mask data. The prefix logic circuits determine the longest prefix among the CAM locations that match the search key, regardless of where the matching locations are logically located in the CAM array. The longest prefix is then compared against the prefix mask data stored in the mask cells to determine the location in the CAM array that stores the CIDR address corresponding to the longest prefix. The CAM index or address of the matching CIDR address may then be output from the CAM device. Additionally and/or alternatively, additional or associated data stored at the CAM index may be accessed. The additional or associated data may be, for example, routing information for the stored CIDR address.
A method and apparatus for determining an exact match in a ternary CAM device is also described. Each ternary CAM cell includes CAM cells for storing CAM data, local mask cells for storing prefix mask data for the corresponding CAM cells, and a mask override circuit. Each local mask cell includes a masking circuit that masks the prefix mask data or CAM data provided to the comparison circuit, or masks the comparison result from the match line of a CAM cell. The mask override circuit effectively overrides the prefix mask data stored in the local mask cell. The mask override circuit performs the override function by negating the operation of the mask circuit such that no masking operation occurs when an exact match compare or invalidate function is performed by the ternary CAM device. For example, during an exact match operation, the CAM cells compare comparand data with unmasked CAM data and provide the compare results to CAM match lines. The local mask cells also compare mask data with the stored prefix mask data and provide the results to mask match lines. If both compares result in a match, then an exact match entry is located in the ternary CAM device. The locations or indexes of the exact match entries may then be output from the CAM device. One or more of the exact match locations may also be invalidated or deleted.
Other objects, features, and advantages of the present invention will be apparent from the accompanying drawings and from the detailed description that follows below.
REFERENCES:
patent: 3257646 (1966-06-01), Roth
patent: 3353159 (1967-11-01), Lee, III
patent: 3602899 (1971-08-01), Lindquist
patent: 3675211 (1972-07-01), Raviv
patent: 3685020 (1972-08-01), Meade
patent: 3868642 (1975-02-01), Sachs
patent: 4112502 (1978-09-01), Scheuneman
patent: 4244033 (1981-01-01), Hattori
patent: 4472805 (1984-09-01), Wacyk
patent: 4523301 (1985-06-01), Kadota
patent: 4646271 (1987-02-01), Uchiyama
patent: 4656626 (1987-04-01), Yudichak
patent: 4670858 (1987-06-01), Almy
patent: 4747080 (1988-05-01), Yamada
patent: 4758982 (1988-07-01), Price
patent: 4780845 (1988-10-01), Threewitt
patent: 4785398 (1988-11-01), Joyce
patent: 4791606 (1988-12-01), Threewitt
patent: 4813002 (1989-03-01), Joyce
patent: 4831586 (198
Khanna Sandeep
Nataraj Bindiganavale S.
Srinivasan Varadarajan
NetLogic Microsystems, Inc.
Peikari B. James
LandOfFree
Method and apparatus for determining an exact match in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for determining an exact match in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining an exact match in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3151534