Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1998-08-31
2001-09-25
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S128000, C711S154000, C711S156000, C365S049130, C712S224000, C712S300000
Reexamination Certificate
active
06295576
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a network system having a router using an associative memory and, in particular, to an associative memory having a mask function.
Referring to
FIG. 1
, a conventional computer network will be described. A user or a subscriber of the network has a connection apparatus, such as a computer terminal, for connection to the network. The connection apparatus (hereinafter referred to as a user's terminal) is assigned with a specific network address in accordance with a predetermined rule when it is connected to the network. Herein, the network address is represented by a numeral of a plurality of digits of, for example, first through fourth digits (a, b, c, d). The predetermined rule defines a hierarchical structure of the network address. For example, the first digit of the numeral represents a zone, such as Asia, America, and Europe. The second digit of the numeral represents a nation in the zone, such as China and Japan, if the zone is Asia. The third digit of the numeral represents a city in the nation, such as Beijing and Shanghai. In the following description, these hierarchical items will be called areas.
Referring to
FIG. 1
, each area is depicted by a rectangular block. Specifically, the network includes a first area (AREA
1
), a second area (AREA
2
), and a third area (AREA
3
) at a highest hierarchical level. The first area (AREA
1
) and the second area (AREA
2
) include a fourth area (AREA
4
) and a fifth area (AREA
5
), respectively. The fourth area (AREA
4
) and the fifth area (AREA
5
) include a sixth area (AREA
6
) and a seventh area (AREA
7
), respectively. A user's terminal (PC)
301
-
1
exists in the fifth area. The first area has a network address (1, *, *, *) in which a first digit alone is specified as “1”. The fourth area subordinate to the first area has a network address (1, 2, *, *) in which first and second digits “1” and “2” are specified. The sixth area subordinate to the fourth area has a network address (1, 2, 2, *) in which first through third digits “1”, “2”, and “2” are specified. Thus, the user's terminal
301
-
1
in the sixth area has a specific or unique network address (1, 2, 2, 3). As will be understood from the above, a symbol “*” contained in these addresses represents “don't care”.
In order to connect or establish communication between a plurality of user's terminals in the network, each area is provided with a network router (hereinafter simply called a router). As illustrated in the figure, the first through the seventh areas are provided with first through seventh routers
300
-
1
through
300
-
7
, respectively. Each router is supplied from any user's terminal or any router connected to the router with transfer data and a transfer address annexed thereto. With reference to the transfer address and the relationship of connection of network apparatuses, the router calculates an optimum transfer route and transfers the transfer data via the optimum transfer route thus calculated.
The user's terminals are not directly connected by the use of the communication channels but carry out communication by controlling network connection by the use of communication control functions of the routers. Thus, communication channels as limited resources are saved.
Next referring to
FIG. 2
, the third router
300
-
3
will be described by way of example. Other routers have a similar structure.
The third router
300
-
3
memorizes, as address information or data, the network addresses for the areas except the third area to which the third router
300
-
3
belongs. Each digit of each network address is represented by a binary number of two bits. Thus, each network address is represented by a bit sequence of eight bits in total. For example, a network address (1, *, *, *) is represented by a bit sequence (01, 00, 00, 00). Since the symbol “*” represents “don't care” for each of second through fourth digits, it is necessary to indicate that the first and the second bits (01) in the bit sequence (01, 00, 00, 00) alone are valid and the remaining bits (00, 00, 00) are invalid. For this purpose, mask information (or mask data) is combined with the address information or data. In the illustrated example, the mask information (or mask data) is given by a bit sequence (00, 11, 11, 11). Herein, “0” and “1” represent a mask invalid state and a mask valid state, respectively. In the third router
300
-
3
, the address information or data and the mask information or data are stored in an associative memory
100
with a mask function, as illustrated in FIG.
2
.
Herein, a typical associative memory with a mask function (hereinafter simply called a mask associative memory) will be described. The mask associative memory can store mask information or data for every single word or every plural words of storage data (namely, the address data). As disclosed in Japanese Unexamined Patent Publication (JP-A) No. 1-220293 (220293/1989), the associative memory has a search (or retrieving) function or a mask searching function in addition to write/read functions of writing and reading storage data at a designated memory address in the manner similar to an ordinary memory circuit. The searching function is for searching same storage data exactly coincident with input search or retrieval data to provide a memory address of the same storage data as a search result. The mask searching function is for searching similar storage data partially coincident with the input search data to provide a memory address of the similar storage data as a search result. Herein, a part of the storage data is excluded from comparison by the use of the mask information.
Referring to
FIG. 3
, the n-bit/m-word associative memory
100
has first through m-th data word lines
102
-
1
through
102
-m and first through m-th mask word lines
103
-
1
through
103
-m both as input signal lines, first through m-th word match lines
104
-
1
through
104
-m as output signal lines, and first through n-th bit lines
101
-
1
through
101
-n as input/output signal lines. The associative memory
100
comprises first through m-th associative memory words
106
-
1
through
106
-m. Each of the first through the m-th associative memory words
106
-
1
through
106
-m is connected to the first through the n-th bit lines
101
-
1
through
101
-n. Each of the associative memory words
106
(suffixes omitted) is connected to a corresponding one of the data word lines
102
(suffixes omitted) and a corresponding one of the mask word lines
103
(suffixes omitted) both as input lines and to a corresponding one of the word match lines
104
(suffixes omitted) as an output line. For example, the first associative memory word
106
-
1
is connected to the first data word line
102
-
1
and the first mask word line
103
-
1
as the input lines and to the first word match line
104
-
1
as the output line.
Upon carrying out a writing operation, the first through the n-th bit lines
101
-
1
through
101
-n are supplied from an external source with write data to be written into data cells or mask cells in a desired one of the associative memory words
106
. Upon carrying out a reading operation, read data are supplied from the data cells to the first through the n-th bit lines
101
-
1
through
101
-n. In order to write or read the data into and from the data cells, a selected one of the first through the m-th data word lines is activated (active or valid state). Then, a corresponding one of the associative memory words
106
is supplied with the write data on the first through the n-th bit lines
101
-
1
through
101
-n. Alternatively, the read data are supplied from the corresponding associative memory word
106
to the first through the n-th bit lines
101
-
1
through
101
-n. For the mask cells, a similar operation is carried out except that the mask word lines
103
are controlled instead of the data word lines
102
. In the following description, the data memorized or to be memorized in the data cells will be referred to as sto
Murase Tutomu
Ogura Naoyuki
Anderson Matthew D.
Foley & Lardner
Kim Matthew
NEC Corporation
LandOfFree
Associative memory having a mask function for use 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 Associative memory having a mask function for use in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Associative memory having a mask function for use in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2467069