Network translation circuit and method using a segmentable...

Details Network translation circuit and method using a segmentable... Network translation circuit and method using a segmentable...

2000-09-05

2004-05-04

Gossage, Glenn (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S202000, C365S049130, C370S401000

Reexamination Certificate

active

06732227

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a translation circuit for use in a computer network. More specifically, the present invention relates to a translation circuit using a segmentable content addressable memory (CAM).
2. Discussion of Related Art
FIG. 1
is a block diagram of a conventional computer network system
100
. System
100
includes computer networks
101
-
105
and router/switch
111
. Networks
101
and
102
communicate with networks
103
,
104
and
105
through router/switch
111
. In system
100
, networks
101
-
105
may use different address formats. Router/switch
111
must therefore be capable of receiving addresses from network
101
or network
102
, translating these addresses, and routing the translated addresses to the appropriate one of networks
103
-
105
. As the number of networks coupled to router/switch
111
increases, router/switch
111
must therefore be capable of performing address translations for a large number of varying networks.
Typically, these address translations are performed by software. For example, a Central Processing Unit (CPU) in router/switch
111
can perform an address translation using a binary search that uses either a Patricia Tree or a hashing method. This binary search proceeds through a tree structure until a unique match is found. A 32-bit lookup typically requires hundreds of CPU cycles to perform. This address translation speed is acceptable in relatively slow interfaces (e.g., interfaces of less than 10 megabyte/second (Mbyte/sec)). However, as the speed of network system
100
increases to 1 gigabyte/second (Gbyte/sec) or greater, a software address translation is not fast enough. A hardware assist must therefore be provided to speed up address translations.
One conventional hardware assist device is a content addressable memory (CAM). The CAM is a pipelined device that is capable of performing a new lookup or search every CAM clock cycle (e.g., every 10 nanoseconds (ns)). Thus, the CAM performs a rapid pattern recognition function that increases the throughput of network system
100
. In the Ethernet protocol, which is the most common protocol, a new packet of information can arrive every 64 byte transfers. Router/switch
111
must therefore be able to read the address in the header of an incoming packet, and provide a revised header that identifies the translated address and an output port, all within 64 clock cycles, to maintain the line speed throughput of router/switch
111
.
A conventional CAM does not have the ability to efficiently handle variable width address translations in a single device. Some CAMs allow lookups having a width corresponding to the width of the CAM, and additionally provide a mask to enable narrower lookups to be performed.
FIG. 2A
is a block diagram of a CAM
210
that is used to perform address translations for both N-bit and M-bit addresses, where M is greater than N. CAM
210
is logically divided into a first section
211
that is used to translate addresses having a width of N-bits, a second section
212
that is used to translate addresses having a width of M-bits, and a third section
213
, which is not used, having a width of (M-N)-bits. Third section
213
represents a significant amount of wasted capacity within CAM
210
.
FIG. 2B
is a block diagram of another CAM
220
that is used to perform address translations for both N-bit and M-bit addresses. CAM
220
includes a first CAM
221
that is used to translate addresses having a width of N-bits, and a second CAM
222
that is used to translate addresses having a width of M-bits. Because two separate CAMs
221
-
222
are required to form CAM
220
, the resulting router
111
is relatively costly and consumes excessive board space and power.
It would therefore be desirable to have a translation circuit that uses a single CAM to provide the required address translations for multiple different network interfaces, without having significant wasted capacity within the CAM.
SUMMARY
Accordingly, the present invention provides a translation circuit that includes a CAM device having a segmentable CAM array. This CAM array that is logically divided into a plurality of CAM segments. In one embodiment, each of the CAM segments has a width of 288-bits. However, other widths can be used in other embodiments. The CAM segments are designated to perform address comparison operations of different widths. For example, first, second and third sets of CAM segments can be designated to perform address comparison operations having first, second and third widths, respectively. In one embodiment, the first, second and third widths are 72-bits, 144-bits and 288-bits, respectively.
Each of the CAM segments is sub-divided into a plurality of sub-segments, each having the same width. In the given example, each 288-bit CAM segment is sub-divided into four 72-bit wide sub-segments. Thus, to implement a 72-bit comparison operation in the first set of CAM segments, each of the CAM segments in the first set is programmed to store four columns of 72-bit address comparison values.
To implement a 144-bit comparison operation in the second set of CAM segments, each of the CAM segments in the second set is programmed to store two columns of 144-bit address comparison values. Each of these two 144-bit columns is formed by two 72-bit wide sub-segments.
To implement a 288-bit comparison operation in the third set of CAM segments, each of the CAM segments in the third set is programmed to store one column of 288-bit address comparison values. This 288-bit column is formed by four 72-bit wide sub-segments. Fitting address comparison values of different widths into a single CAM array advantageously minimizes wasted CAM capacity.
An instruction is provided to the CAM device to specify an address translation having the first width, the second width or the third width. A comparison operation is performed in the first, second or third set of CAM segments when the instruction specifies an address translation of the first width, the second width or the third width, respectively. Because comparison operations are only performed in the relevant segments, power savings are advantageously realized.
In one embodiment, the CAM device includes a configuration register that is programmed to store values defining the locations of first, second and third sets of CAM segments in the CAM array. This advantageously enables the resources of the translation circuit to be modified in view of the nature of the connected networks.
In another embodiment, the CAM device includes size logic coupled to the CAM array. The size logic processes results from the first, second and third sets of CAM segments in a manner consistent with the widths of the comparison operations performed by these segments. The size logic provides results to a priority encoder, which in turn, generates an index signal representative of the highest priority match detected during the comparison operation. The index signal is then used to address a static random access memory (SARAM), which stores the translated addresses.
Other functions performed by the CAM device can include global and local masking, a bypass function, and burst write capability.


REFERENCES:
patent: 5706224 (1998-01-01), Srinivasan et al.
patent: 6000008 (1999-12-01), Simcoe
patent: 6243281 (2001-06-01), Pereira
patent: 6253280 (2001-06-01), Voelkel
patent: 6324087 (2001-11-01), Pereira
patent: 6374326 (2002-04-01), Kansal et al.

Affiliated with

Also associated with

Rating

Network translation circuit and method using a segmentable... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Network translation circuit and method using a segmentable..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network translation circuit and method using a segmentable... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3190318