Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-10-22
2003-10-28
Nguyen, Van Thu (Department: 2824)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230060, C711S108000
Reexamination Certificate
active
06639819
ABSTRACT:
BACKGROUND OF THE INVENTION
1) Field of the Invention
The present invention relates to an associative memory apparatus and a routing apparatus suitable for use in address switching at a relay point in a network, for example.
2) Description of the Related Art
With rapid spread of use of the Internet technology, speed-up of the network becomes more important issue. Particularly, a router that is a relay point in the network is required to distribute a packet (for example, IP [Internet Protocol] datagram) flowing in the network on a proper route in a high-speed routing operation.
In such the routing operation on the network, a CAM (Content Addressable/Associative Memory) device is heretofore used as an apparatus for searching a destination address. The CAM device performs a process to search a destination address for an inputted packet by hardware.
When used as the above destination address searching apparatus, the CAM device is required to have a function of performing a, so-called, Longest Prefix Match searching to select the longest prefix bits which are not masked among addresses matching in the search.
As the CAM device performing the above longest prefix match searching, there is a Ternary-CAM
100
as shown in
FIG. 15
, for example. The ternary CAM
100
searches for a matching address (a coinciding address in the address bit matching) among entered destination addresses
104
on the basis of an address
101
that is a search key.
The ternary CAM
100
shown in
FIG. 15
comprises a plurality of entry units
103
-
1
to
103
-
n
, each of which can store a destination address (address 1 to n) and prefix bits
105
corresponding to the destination address
104
, match lines
102
provided for the respective entry units
103
-
1
to
103
-
n
, and a priority encoder
106
.
The destination addresses
104
stored in the respective entry units
103
-
1
to
103
-
n
are beforehand arranged in order of length of consecutive bits (a length of consecutive bits of value “1”) in the prefix bits
105
.
In the case of value “1” in the prefix bits
105
, a condition that a result of matching is not ignored is given in the matching of corresponding address bit digit. In the case of value “0”, a condition that a result of the matching is ignored (Don't care condition) is given in the matching of corresponding address bit digit.
In this case, a destination address having the longest prefix bits
105
is stored in the entry unit
103
-
1
, and a destination address having the second longest prefix bits is stored in the entry unit
103
-
2
. In the entry units
103
-
3
to
103
-
n
, destination addresses are stored in order of length of the prefix bits.
When search match signals (match) from the entry units
103
-
1
to
103
-
n
compete, the priority encoder
106
outputs a search match signal having a longer prefix bits
105
from the entry unit
103
-
1
,
103
-
2
, . . . or
103
-
n
as a result of the searching.
FIG. 16
is a block diagram showing a CAM cell configuring each of the entry units
103
-
1
to
103
-
n
shown in FIG.
15
. Namely, each of the entry units
103
-
1
to
103
-
n
comprises the CAM cells
200
shown in
FIG. 16
in number corresponding to bits assumed to configure a destination address.
One CAM cell
200
comprises a data register
201
for storing address data of one bit configuring a destination address, a mask register
202
for storing a prefix bit of one bit corresponding to the address data, a comparator
203
for comparing address data from the data register
201
with address data that is a search key from bit lines
206
and
207
, and a mask circuit
204
for performing a masking process (refer to a reference character
208
) on the basis of a value of the mask register
202
.
With the above structure, in the ternary CAM
100
show in
FIG. 15
, a search for coincidence with an address that is a search key is made in each of the ternary units
103
-
1
to
103
-
n
. An entry unit
103
-
1
,
103
-
2
, . . . , or
103
-
n
storing a destination address matching with the address that is a search key outputs this effect as a search match signal (match signal) to the priority encoder
106
through the match line
102
.
In this case, all entries (destination addresses stored in the entry units
103
-
1
to
103
-
n
) are arranged in order of length of the prefix bits
105
and accommodated. Therefore, when a plurality of destination addresses match, the priority encoder
106
outputs a match signal from the entry unit
103
-
1
,
103
-
2
, . . . , or
103
-
n
given the highest priority among matching destination addresses in the search as a result of the longest prefix match.
In order to appropriately obtain a result of the longest prefix match in the ternary CAM
100
in
FIG. 15
, it is necessary to beforehand arrange all entries in order of length of the prefix and accommodate them. Namely, when a new distribution destination is registered or when a distribution destination that becomes not to be used is deleted, it is necessary to add or delete the entry.
When an entry is added, an entry unit
103
-
1
,
103
-
2
, . . . or
103
-
n
to which the entry should be inserted is determined according to the length of the prefix among the entry units
103
-
1
to
103
-
n
, entries lower than the relevant position are moved down, an entry unit
103
-
1
,
103
-
2
, . . . or
103
-
n
at a position at which the new entry should be added is emptied, after that, the entry to be added is stored. Whereby, the entry can be added without breaking the order of length of the prefix.
When an entry is added or deleted as above, it is necessary to rearrange all the entries in order of prefix, and again accommodate them. However, a series of this updating work requires a considerable time. Moreover, it is necessary to stop the CAM device in service.
Since a high-speed, continuous operation of the CAM device is required to more speed up the network, such the updating work causes serious interruption. With spread of the Internet, there is a demand for a larger-capacity of the CAM because of an increase of the number of entries, or an increase of the number of address bits under application of IPv6 (Internet Protocol version 6). When such the updating work is done on a CAM having a large capacity, a load of the work more increases.
U.S. Pat. No. 6,144,574 discloses an apparatus which accommodates an entry of an arbitrary length at an arbitrary position, obtains a result of full match (multi-match) searching and the longest prefix length in the first search cycle, feeds back the longest prefix length obtained in the first cycle in the second cycle, again carries out the searching operation on the prefix of all the entries, and outputs a matching entry as a result of the longest prefix match searching, while reducing a load of the updating work.
However, the above apparatus requires two search cycles as the searching process. For this, there is a problem that the speed-up is disturbed even in such the configuration where two search cycles are required. In order to satisfy a demand for speed-up and larger-capacity of the above CAM device, it is necessary to provide a technique for more shortening a processing time required to carry out the above searching process twice.
SUMMARY OF THE INVENTION
In the light of the above problems, an object of the present invention is to provide an associative memory apparatus and a routing apparatus, which can reduce a load of the updating work, readily cope with an increase of the capacity, and shorten a time for the searching process by outputting longest prefix match in one searching operation.
The present invention therefore provides an associative memory apparatus comprising a plurality of entry units storing bit data to be searched and entry data differing from one another having mask identifying data for masking a necessary bit length required by the bit data, and matching each of the entry data with the bit data that is a search key, a matching-masking state outputting means inputted information reflecting a result of
Ooba Yasuhiro
Uzawa Yuichi
Fujitsu Limited
Katten Muchin Zavis & Rosenman
Nguyen Van Thu
LandOfFree
Associative memory apparatus and routing apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Associative memory apparatus and routing apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Associative memory apparatus and routing apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3125953