Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2001-07-30
2002-05-07
Phan, Trong (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C711S108000
Reexamination Certificate
active
06385072
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a content addressable memory (CAM)(which is also generally called an “associative memory”)
2. Description of the Related Art
Conventionally, a content addressable memory (CAM) is known as a memory used such that storage data is stored in each of a plurality of word memories (which constitute a memory region) to permit overwriting, retrieval data is entered, and storage data corresponding to the retrieval data is retrieved.
One of the major applications is a network frame repeater that relays communications of network frames. The network frame repeater will be outlined hereinbelow.
Conventionally, a network system includes a network frame repeater called, for example, a “hub”. The network frame repeater relays transmission of network frames, each of which is a packet of information that is communicated in the network system.
FIG. 3
is a circuit block diagram showing an example configuration of a network frame repeater
30
.
The network frame repeater
30
includes n pieces of port controllers
32
_
1
to
32
_n connected to a bus
31
. In addition, a plurality of terminals A, B, . . . , C and a plurality of terminals E, F, . . . , G are connected via local area networks
34
_
1
to
34
_n (LANs) to ports
33
_
1
to
33
_n, respectively, which correspond to the port controllers
32
_
1
to
32
_n.
In addition, the bus
31
is connected to a CAM
35
, a random access memory
36
(RAM), a central processing unit
37
(CPU), and a packet memory
38
.
Compared to an ordinary RAM, the CAM
35
, to which a retrieval function is added, is expensive in terms of the cost per bit and has a small memory capacity. To solve this problem, the network frame repeater
30
shown in
FIG. 3
uses both the CAM
35
and the RAM
36
. Data directly required for retrieval is stored in the CAM
35
, and data not directly required for retrieval is stored in the RAM
36
. The addresses of word memories of the CAM
35
are correlated to the addresses of memory regions of the RAM
36
via a signal line
39
. The CAM
35
stores address data representing the addresses of the individual terminals and time stamp data (which will be described hereafter). On the other hand, the RAM
36
stores the port numbers of the individual ports
33
_
1
to
33
_n connected to the terminals. In addition, the RAM
36
stores other data, such as data related to a virtual LAN (VLAN), and data accessed by hardware of the network frame repeater
30
(detailed description of the data is omitted herefrom).
The CPU
37
performs the overall control of the network frame repeater
30
. The packet memory
38
temporarily stores received network frames.
Ordinarily, the network frame repeater
30
includes various other devices. However, since the devices are not directly concerned with the intended subject matter, they are neither described nor illustrated.
Hereinbelow, description will be made with reference to an example case where information in the form of a network frames is transmitted from the terminal B connected to the LAN
34
_
1
to the terminal E connected to the LAN
34
_n.
A header portion of the network frame contains data identifying a destination address representing the terminal E, and a transmission source address representing the terminal B.
The network frame transmitted from terminal B via the port
33
_
1
is controlled to pass through the port controller
32
_
1
and the bus
31
, and is then temporarily stored in the packet memory
38
. The CPU
37
extracts the destination address representing a data transmission destination (terminal E in the example case) from the header portion of the network frame, and then sends it to the CAM
35
. The CAM
35
contains address data representing the individual terminals A, B, . . . , C and the individual terminals E, F, . . . , G, which constitute the network system. On the other hand, the RAM
36
stores the port numbers individually identifying destinations to which the terminals A, B, . . . , C and the terminals E, F, . . . , G are connected via the ports
33
_
1
to
33
_n. Address data representing the destination address is input into the CAM
35
. Subsequently, the CAM
35
outputs to the signal line
39
an HHA (highest hit address) of a word memory of the CAM
35
, which contains address data identical to the aforementioned input address data. In response to the output, the port number representing the destination terminal indicated by the destination address is read out of the address corresponding to the HHA of the RAM
36
. Based on the port number that has been read out, the CPU
37
recognizes the present network frame as data that is due to be transmitted to port
33
_n.
When the port number is read out of the RAM
36
in the above-described manner, the network frame is input from the packet memory
38
via the bus
31
to the port controller
32
_n, and is further sent to the terminal E via the port
33
_n and the LAN
34
_n.
In this way, the network frame repeater
30
uses CAM
35
for performing high-speed retrieval of addresses.
FIG. 4
shows a MAC (media access control) table in the network frame repeater
30
shown in FIG.
3
.
The MAC table shown in
FIG. 4
contains address data representing the addresses (MAC addresses) of the terminals A, B, . . . , C and terminals E, F, . . . , G; the corresponding port numbers; and the corresponding time stamp data.
As described above, a destination address extracted from a network frame is used for retrieval. The port number to which the network frame is to be transmitted can be known from a retrieved address stored in the RAM
36
, which corresponds to the HHA. As shown in
FIG. 4
, in addition to terminal address data, each of the word memories also contains time stamp data. Hereinbelow, the time stamp data will be described.
FIG. 5
is a view for explaining time stamp data.
As shown in
FIG. 5
, a predetermined time interval is set for one time slot, and p pieces of the time slots are cycled one by one as time passes. To discriminate the p pieces of the time slots from each other, their numbers, for example, numerals
1
,
2
, . . . , and p are assigned to represent the time stamp data T
1
, T
2
, . . . , and Tp, respectively.
In the CAM
35
, in an event where a retrieval has been carried out by using a source address extracted from a network frame, the retrieval has detected an address identical to the source address thereof, time stamp data of the corresponding word memory is overwritten with the time stamp data that represents the time slot at that time (current time). However, in an event where the retrieval has not detected an address identical to the source address, data of the source address and time stamp data representing a time slot of the current time is written into a empty address field (empty word memory). On the other hand, into the RAM
36
are written the port number of a port from which a network frame having that source address has been transmitted. In the CAM
35
, at each time interval that defines each of the time slots, retrieval is carried out by using the time stamp data of the time slot (time slot whereat the longest time has passed) immediately preceding the current time slot. As a result, if time stamp data identical to the input time stamp data is detected, data in the corresponding word memory is erased. By erasing the address data of terminals that have not been involved in communication for a long time, a empty address field is secured in the CAM
35
, thereby enabling the CAM
35
to store new data. In this case, the erasure of data means that, for example, one bit in the word memory is allocated as a bit (empty bit) that is used to determine the existence of data, and the bit is overwritten so as to be converted from logic representing a data-existence to logic representing a data-nonexistence. In addition, each of the word memories may have an empty flag as a flipflop that indicates whether valid data is stored or not in the word memory, and data can be erased by overwriting the fla
Kawasaki Microelectronics Inc.
Oliff & Berridg,e PLC
LandOfFree
Content addressable memory using part of memory region to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory using part of memory region to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory using part of memory region to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2871523