Range content-addressable memory

Details Range content-addressable memory Range content-addressable memory

2001-02-07

2003-10-14

Bragdon, Reginald G. (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S158000

Reexamination Certificate

active

06633953

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of Content Addressable Memory (CAM). More particularly, the invention relates to a method and apparatus for storing associative ranges containing keys and data associated with said ranges, in form of a lookup table, in which a searched associative key found within a range is used to extract the associated data.
BACKGROUND OF THE INVENTION
Content Addressable Memory (CAM) devices are specially designed for storing information in the form of a lookup table. CAM structures allow a direct and fast search of data items, a search which is based on an associative key. Software implementations of such data structures are usually slow for real time applications, especially in view of the great advances of the recent years, in data transmission rates.
In general, CAM comprises storage of key words, and a separate storage for associated data items. For each of the stored key words, there is a corresponding associated data item. Therefore, the structure and operation of CAMs differs from those of conventional memory devices, such as RAM, wherein each data item is addressed by utilizing a unique address. In CAMs, data items are fetched from the CAM device by submitting a key value. The key words storage is then searched to determine if a matching key word is stored inside the CAM. If there is a key-matching entry found in the CAM, a ‘match’ indication is issued, and the corresponding associated data (i.e., the data item associated with the key) is output from the CAM. If there is no matching key, a ‘mismatch’ indication is issued.
The efficiency and high speed, inherent to the CAM implementations, makes them very attractive for address filtering and routing in networking applications. The Internet routers, for instance, maintain a list of Internet Protocol (IP) Destination Addresses (IPDAs), and their associated interfaces (e.g., port numbers) through which the router should forward the received packet. This list is utilized to determine the best route for a packet of information received by the router to reach its destination. More particularly, said list of IPDAs and the interfaces is organized in the form of a lookup table. The key word associated with each IPDA, is the router interface of the destined network node (i.e., the next routing point, to which the received packet is destined).
Each IPDA is a unique 32-bit entity, usually represented in the form of four octets (sequences of eight bits, e.g., 192.30.50.0), comprising address information of the destined node within that network.
The original IP network classification method, utilizing five basic Classes for any network on the Internet, turned out to be very expansive in terms of IPDA address space consumption, and in terms of the routing table size, required for forwarding lookups. As a consequence, the Internet ran out of address space very quickly. This has also led to an outstanding growth in the size of the routers' lookup tables.
I order to overcome the problems described herein above, the Internet Engineering Task Force (IETF) devised a more flexible method (as described in RFC1519), known as the Classless Inter-Domain Routing (CIDR). The CIDR resolves the difficulties stemming from the original network Address-Class hierarchy by aggregating multiple routes into a single representation. Address aggregation is achieved by masking a contiguous number of address 32-p least significant bits, which leads to a representation of a range of addresses by a single address and its mask. This leaves p bits also defined as the address prefix, which should be compared. p can be any integer value from 0 to 32. The convention used to describe a CIDR address entry is A/p, where A is the address and p is the prefix. For example, the CIDR address entry 192.30.50.0/24 matches any IPDA address in the range 192.30.50.0←→192.30.50.255.
Generally a CIDR address may match with multiple number of entries in the router's key list, this due to the presence of overlapping address ranges. Selection of one out of multiple matches is based upon the most specific match, which is the one with the longest prefix.
The CIDR addressing scheme allows a more efficient allocation of IP addresses, which results in significant reduction in the size of the routing table, yet the growth of the Internet is seems to be increasing with time, and the difficulties stemming from this growth in routing table size still remain.
The modern routers are now designed for CIDR compliance. Ternary CAM technology is widely adopted in routers implementation, but the substantial growth in the size of routing tables, and the many comparison operations required to determining a key match, influence performance and power consumption. Other complications in Ternary CAM (TCAM) implementations are due to the complexity involved in determining the key match to a range of possible values, and especially utilizing CIDR's longest-prefix-match policy. The conventional CAM implementations are efficiently designed for lookup tables when an exact match of key values is required, but the situation is more complex when a range of values need to be matched. Moreover, the aggregation efficiency is greatly influenced by the allocated address space, which in many cases is not covered by a single mask prefix, resulting in a substantial increase of routing table's sizes.
In addition, Ternary CAMs are limited with respect to the ranges boundaries, which are limited only to integer values being &agr;·2
32−p
, where a is an integer, and p is the prefix length. Therefore, the boundary values do not represent the whole range of non-negative integer values. This eliminates the capability of further aggregation over and beyond the one offered by the CIDR method.
Since, multiple matches are feasible all the entries must be simultaneously compared to a key, which stems in a high power consumption, that grows proportionally to the number of entries and with the lookup rate. For instance a typical 64 K Ternary CAM consumes about 10 Watts at a rate of 66 million lookups per second.
Due to the requirement to arrange Ternary CAM entries in prefix-length order, the database update may become cumbersome and lengthy in time.
Ternary CAM's basic cell is complex, since it incorporates the address, the mask and the comparator. The resulting cell size, substantially limits the amount of entries per TCAM device in comparison with an SRAM. The biggest TCAM (for instance SiberCore's SiberCAM Ultra-2M) implemented today, incorporates 64 K IPv4 CIDR address entries without the associated data.
“IP Lookups using Multiway and Multicolumn Search”, B. Lampson et al, Proceedings of IEEE Infocom, Volume 3, April 1998, pages 1248-1256 discloses a search method based on an interaction between a processing device and a memory, using binary search based algorithm for CIDR address searches. This method results in having a unique memory entry in which the result may reside. However, it offers a search performance, which varies as log
2
n, where n represents the number of entries. This is worse in performance than a Ternary CAM, which is insensitive to the lookup table size. Furthermore, this implementation is unsuitable for high-performance routing, due to it lookup rate limitation.
All the methods described above have not yet provided satisfactory solutions to the problem of efficient storage of associative data in lookup tables, and which might result in low power consumption and in high search performance.
It is an object of the present invention to provide a Range Content Addressable Memory (RCAM) being capable of Searching a whether a submitted key belongs to a range bounded by two non-negative integers, that has a common associated data.
It is another object of the present invention to provide an RCAM for storing and searching associative data items related to, disjoined and/or overlapping ranges.
It is another object of the present invention to provide an RCAM, which allows efficient associative data aggregation, using less

Affiliated with

Also associated with

Rating

Range content-addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Range content-addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Range content-addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3127173