Boundary addressable memory

Details Boundary addressable memory Boundary addressable memory

2001-11-07

2004-04-13

Elmore, Reba I. (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S105000, C711S108000

Reexamination Certificate

active

06721842

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to semiconductor memories, and more specifically to a boundary addressable memory (BAM) device.
BACKGROUND OF THE INVENTION
In a computer network, data transferred from one network device to another network device via the computer network is typically broken down into small blocks of data called packets. Packet filtering is a basic requirement of networking devices, such as routers, upper layer switches, firewalls, bandwidth managers, and similar devices.
A content addressable memory (CAM) device is a well-known semiconductor device that is used to perform data filtering in classification systems. A CAM permits the contents of the memory to be searched and matched instead of having to specify one or more particular memory locations to retrieve data from the memory. One example of an application in which CAM devices are often used is to search a routing table to look for a matching destination address, such as an Internet Protocol (IP) destination address, so that data may be routed to the appropriate destination address. After the matching address is identified, it is often required to apply additional filtering criteria to determine whether the matching address falls within a certain range. Range checking has applications in computer networking, such as checking for port number ranges and valid length and type values in Ethernet MAC headers. Implementing range checking for a non-binary CAM, however, requires multiple entries. Having multiple entries would make routing very expensive and space inefficient. Moreover, CAM-like memory devices search for matching data by looking up the entire area in memory in multiple cycles, thereby increasing latency.
Therefore, what is needed is a memory device for performing arithmetic range checking.
SUMMARY OF THE INVENTION
The present invention overcomes the deficiencies and limitations of the prior art with a boundary addressable memory (BAM) device for performing arithmetic range checking in classification systems. The present invention is particularly advantageous because it performs arithmetic comparisons using a range check, instead of performing CAM-like equality comparisons. Arithmetic range checking provides a method for matching an input value that is greater than or equal to a stored lower bound value and at the same time less than or equal to an upper bound value.
The BAM device of the present invention comprises an array of BAM word modules. Each BAM word module includes a plurality of BAM cells. In a preferred embodiment of the present invention, each BAM cell includes a memory cell that stores an n
th
bit of an upper bound value and a memory cell that stores an n
th
bit of a lower bound value. The BAM cell further includes an upper bound comparator for performing arithmetic comparisons between the n
th
bit of the upper bound value and the n
th
bit of the input data. The BAM cell also includes a lower bound comparator for performing arithmetic comparisons between the n
th
bit of the lower bound value and the n
th
bit of the input data.
In a preferred embodiment of the present invention, a search of the BAM device for a BAM word with a lower bound value less or equal to the input data and an upper bound value greater than equal to the input data occurs in the following manner. An n
th
bit of the input data is provided to both the upper bound comparator and the lower bound comparator. The upper bound comparator compares the n
th
bit of the input signal with the n
th
bit of the stored upper bound value. Simultaneously, the lower bound comparator compares the n
th
bit of the input data with the n
th
bit of the stored lower bound value. The comparisons are performed bit-by-bit and propagate down all the way from the highest order bit to the lowest order bit. As a result, a BAM word asserts a signal indicating whether the input data is less than or equal to the upper bound value and greater than or equal to the low bound value or the input data is greater than or equal to the upper bound value and less than or equal to the low bound value.
A logic gate is coupled to receive the less than or equal and greater than or equal outputs of each BAM word module and to generate a matching signal in response to the received outputs. In one embodiment of the present invention, the matching signal indicates that the input data falls within the range specified by the upper bound value and the lower bound value. In another embodiment, the matching signal indicates that the input data falls outside the range specified by the upper bound value and the lower bound value.


REFERENCES:
patent: 3845465 (1974-10-01), Hosick et al.
patent: 4627024 (1986-12-01), Whalen et al.
patent: 4760374 (1988-07-01), Moller
patent: 5509006 (1996-04-01), Wilford et al.
patent: 5561429 (1996-10-01), Halberstam et al.
patent: 5574910 (1996-11-01), Bialkowski et al.
patent: 5608662 (1997-03-01), Large et al.
patent: 5761424 (1998-06-01), Adams et al.
patent: 5802054 (1998-09-01), Bellenger
patent: 5884033 (1999-03-01), Duvall et al.
patent: 2002/0093347 (2002-07-01), Henderson et al.
patent: 2003/0152078 (2003-08-01), Henderson et al.
patent: 2003/0154328 (2003-08-01), Henderson et al.
patent: WO 94/01828 (1994-01-01), None

Affiliated with

Also associated with

Rating

Boundary 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 Boundary addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boundary addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3214600