CAM cell array, TCAM cell, TCAM cell array, address search...

Details CAM cell array, TCAM cell, TCAM cell array, address search... CAM cell array, TCAM cell, TCAM cell array, address search...

2003-02-27

2004-05-04

Auduong, Gene (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S168000, C365S189060

Reexamination Certificate

active

06731526

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a technology for searching a network address in a so-called pipeline system.
BACKGROUND OF THE INVENTION
As Internet users and construction of local area networks (LANs) in enterprises increase in recent years, ternary content addressable memories (TCAMs) serving as address search apparatuses are used frequently in routers at relay points on a network in order to enhance the processing capability. Hereafter, the TCAM will be explained by referring to
FIGS. 15
to
20
.
FIG. 15
is a diagram which shows a configuration example of a network system in which the TCAM serving as the address search apparatus is used.
FIG. 16
is a diagram which shows a classifying algorithm of packets using hardware processing.
FIG. 17
is a concept diagram which shows a basic configuration and search operation of the TCAM.
FIG. 18
is a block diagram which shows a detailed configuration of the TCAM.
FIG. 19
is a concept diagram which shows a configuration of a conventional TCAM cell shown in FIG.
18
.
FIG. 15
shows a system example shown in “Algorithms for Packet Classification” IEEE Network, March/April 2001. In
FIG. 15
, a network
1601
is administered by an Internet service provider (ISP
1
). An intra-enterprise network (E
1
)
1603
is connected to the network
1601
via a router at a relay point (“junction router”)
1602
. An intra-enterprise network (E
2
)
1605
is connected to the network
1601
via a junction router
1604
.
In addition, a network access point (NAP)
1607
is connected to the network
1601
via a junction router
1606
. A network
1608
administered by an Internet service provider (ISP
2
) and a network
1609
administered by an Internet service provider (ISP
3
) are connected to the NAP
1607
.
In the junction routers
1602
,
1604
and
1606
in the configuration heretofore explained, a rule stated in a header of a received packet is looked up, and packet classification is conducted. For example, in the junction router
1606
, packets received from the NAP
1607
are classified, such as “this packet should go to the intra-enterprise network E
1
”, “this packet should not go to the intra-enterprise network E
1
, but hop to the intra-enterprise network E
2
”, and “this packet should not go anywhere”.
In headers of packets, such various kinds of information are stated in the form of rules, and they serve as search keys for classification in junction routers. In each junction router, it is necessary to look up what action each of all rules included in various received packets requires and to instantaneously determine to which routers the respective packets should be delivered (hopped).
There are various techniques for the packet classification (“Algorithms for Packet Classification” IEEE Network, March/April 2001). Today, a packet classification algorithm using hardware processing as shown in
FIG. 16
is used most frequently. In this algorithm, special hardware called ternary content addressable memory (TCAM) is used.
With reference to
FIG. 16
, in the packet classification algorithm using hardware processing, a TCAM
1701
, a priority encoder
1702
, and an action memory
1703
are used.
In the TCAM
1701
, a rule is held every entry. Since TCAM in these days is too expensive, only a rule name, i.e., only a label is typically held in each entry. An action to be subsequently executed is stored in the action memory
1703
formed of comparatively inexpensive DRAMs or SRAMs.
If a rule as a destination address is given to an input pin of the TCAM
1701
from the packet, parallel coincidence comparison is started all at once between the rule given to the input pin and internally held rules. And an entry number (or entry numbers) bearing coincidence or a highest resemblance is output. For example, if a rule (R
4
, R
5
and R
6
) is given, an entry number #
3
is output.
When there are plurality of search results of the TCAM
1701
, the priority encoder
1702
supplies an entry having a lowest number to the action memory
1703
as an entry having high priority. With respect to the entry input from the priority encoder
1702
, the action memory
1703
searches out an action to be subsequently conducted. As a result, the next router is specified and a packet is transferred. Hopping to the next step is thus conducted.
For example, if a rule is an IP address, an “X” value (don't care) is often used. This means that it is removed from search targets of coincidence comparison. If a stored value is “X”, the TCAM
1701
determines it to be unconditional coincidence. Therefore, information to be stored by an internal cell of the TCAM
1701
also becomes ternary, “0”, “1” and “X”. The name of ternary CAM (content addressable memory) comes from this.
A basic hardware configuration of the TCAM and basic operation of the search will now be explained by referring to FIG.
17
. In
FIG. 17
, a search port
1801
is provided in the TCAM. In the search port
1801
, a data sequence of a search command is disposed. A plurality of TCAM cells
1802
are provided in each of entries (entries #
0
to #n). The plurality of TCAM cells
1802
are connected to the data sequence of the search port
1801
by search operation bit lines (search lines)
1803
in one-to-one correspondence. The plurality of TCAM cells
1802
provided for each of entries (entries #
0
to #n) are connected in common to a search output line (match line)
1804
. Each of the TCAM cells
1802
stores a ternary value of “0”, “1”, or “X”.
If the search command is supplied to an input pin, not shown, at the time of search operation, then the search command is transferred to the search port
1801
, and the data sequence of the search command is disposed on the search operation bit lines
1803
and transferred to all TCAM cells
1802
of each entry. As a result, comparison is simultaneously started in all entries to determine whether the data sequence coincides with data held in the TCAM cells
1802
.
The search output line
1804
is precharged to a high (“H”) level before the search operation is started. Typically, on a search output line
1804
connected to coincident TCAM cells
1802
, the “H” level is held as it is. On the other hand, on a search output line
1804
connected to a non-coincident TCAM cell
1802
, discharge is conducted via a transistor in the cell and the search output line
1804
is lowered to a low (“L”) level. In other words, the TCAM
1701
serving as an address search apparatus shown in
FIG. 16
checks the entry number of the search output line
1804
that holds the “H” level and outputs the entry number to the priority encoder
1702
. This is the role of the TCAM
1701
.
A detailed configuration of the TCAM and outline of its search operation will be explained with reference to FIG.
18
. As shown in
FIG. 18
, the TCAM includes a data input/output pin
1901
, a command control pin
1902
, an address input pin
1903
, and a search result output pin
1904
as pins for connection to the outside.
A command decoder
1921
is connected to the command control pin
1902
. A command supplied to the command control pin
1902
is decoded by the command decoder
1921
. An operation command resulting from the decoding is sent to each section.
A decoder
1931
is connected to the address input pin
1903
. A row decoder
1932
is connected to an output terminal of the decoder
1931
. An output terminal of a search encoder
1941
is connected to the search result output pin
1904
.
Between an output terminal of each row of the row decoder
1932
and an input terminal of a corresponding row of the search encoder
1941
, a plurality of TCAM cells
1910
are arranged so as to form one lateral line. A mask data word line
1933
and a valid data word line
1943
are connected to the output terminal of each row of the row decoder
1932
. A plurality of TCAM cells arranged in one lateral line are connected to the mask data word line
1933
and the valid data word line
1943
in parallel.
A search output line (match line)
1942
is connected to th

Affiliated with

Also associated with

Rating

CAM cell array, TCAM cell, TCAM cell array, address search... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with CAM cell array, TCAM cell, TCAM cell array, address search..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and CAM cell array, TCAM cell, TCAM cell array, address search... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3188538