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.
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.
USPTO Backgrounds
USPTO Backgrounds