WO2004054186A1

WO2004054186A1 - Data relay apparatus, associative memory device, and associative memory device utilization information search method

Info

Publication number: WO2004054186A1
Application number: PCT/JP2002/013042
Authority: WO
Inventors: Yuichi Uzawa; Yasuhiro Ooba
Original assignee: Fujitsu Limited
Priority date: 2002-12-12
Filing date: 2002-12-12
Publication date: 2004-06-24
Also published as: JP3837670B2; JPWO2004054186A1

Abstract

It is possible to effectively input a search request command to an associative memory (CAM) device. When a packet is input, a search request (10) is generated by a network processor (1) and passed to the associative memory device (2). In the associative memory device (2), structure of the search request (10) is analyzed and a plurality of search conditions are generated. In the associative memory device (2), search is performed according to the search conditions and a memory address (21) corresponding to the search object information detected is output to a memory device (3). From the memory device (3), a search result candidate corresponding to the memory address (21) is passed as a search result (22) to the network processor (1).

Description

Data relay device, associative memory device, and associative memory device utilization information retrieval method

The present invention relates to a data relay device for relaying a packet to be transmitted, and a data relay device for transmitting a

The present invention relates to an associative memory device use information retrieval method for retrieving information related to an associative memory device and a packet to be used by using an associative memory device. Food

The method relates to a method of retrieving information on disk usage.

Background art

In a device such as a router or a switch (hereinafter, referred to as a data relay device) serving as a relay point of a network, routing processing is performed by a destination of a packet flowing in the network. This route selection may be realized by software using a general-purpose computer, or may be realized by dedicated hardware.

Generally, when high-speed route selection is required, packet routing is realized by dedicated hardware. A dedicated processor for route selection called a network processor is installed in the data relay device with a dedicated hardware configuration.

The network processor determines the physical port to be output by referring to various information such as the IP (Internet Protocol) address of the bucket that has been input. Generally, a network processor has a memory for storing what IP address of a terminal device is connected to its physical port. When transferring a packet, the destination physical port can be specified by referring to the contents of the memory. Thus, the route selection always involves memory access in the data relay device. Therefore, in order to select a path at high speed, it is desired to improve the efficiency of memory access. As a technique for improving the efficiency of access from a CPU (Central Processing Unit) to a memory, for example, there is a technique of buffering commands in a command access circuit (or a memory control circuit) between the CPU and the memory. . For example, see JP-A-8-87441 and JP-A-2000-99394.

In particular, when high-speed and large-capacity routing is performed, notification is performed using a special memory called a CAM (Content Addressable / Associative Memory) device. A route selection circuit using a CAM device is also called a network change.

The CAM device stores information such as an IP address. When information such as an IP address is input, the CAM device outputs a memory address of a storage area in which the information is stored. CAM devices are used not only for data relay devices but also for speeding up memory in various systems. See JP-A-2000-231785 (paragraph “002 3”).

By the way, in the route search for one packet, the memory access in the network processor may be performed a plurality of times. For example, the IP address (source address: SA and destination address: DA) extracted from the packet and the port numbers (source port number and destination port number) such as T.CP transmission Control Protocol) / UDP (User Datagram Protocol) ) And may be searched twice.

Hereinafter, a route search process involving a plurality of CAM device accesses will be described.

FIG. 17 is a diagram showing a conventional route search process involving multiple CAM device accesses. As shown in FIG. 17, the data center device is provided with a network processor 911, a CAM device 912, and a context RAM (Random Access Memory) 913. The storage area of the CAM device 912 is provided with an IP address storage area and a port number storage area. In the example of Fig. 17, one packet When transferring a packet, two searches are performed by IP address and port number.

[Step S101] When the bucket information is input to the data relay device, the search key 921, the mask setting command 922, and the mask setting command 922 from the network processor 911 to the CAM device 912 are transmitted. A search command 9 23 is sent. The search key 9 21 is an IP address. The mask setting command 922 is a command for specifying mask processing (other than the search target) other than the storage area of the IP address in the CAM device 912.

The CAM device 912 masks the range specified by the mask setting command 922. Masked areas are excluded from the search. Then, the CAM device 912 searches for data matching the search key 921, and outputs the memory address of the area where the data is stored. The output memory address is input to the context RAM 913 as a read memory address. Then, the data 924 is output from the area corresponding to the input memory address from the context RAM 913, and is input to the network processor 911. This is a Layer 3 (network layer) search process.

[Step S102] Next, a search key 931, a mask setting command 932, and a search command 933 are sent from the network processor 911 to the CAM device 912. The search key 931 is a port number indicating the application on the destination side of the packet to be transferred. The mask setting command 932 is a command for designating a mask process other than the storage area of the port number in the CAM device 912.

The CAM device 912 masks the area specified by the mask setting command 932. Then, the CAM device 912 searches for data matching the search key 931, and outputs the memory address of the area where the data is stored. The output memory address is input as a read address to the context RAM 913. Then, data 934 is output from the area corresponding to the input memory address from the context RAM 913, and is input to the network processor 911. This is a Layer 4 (transport layer) search process. Performing the search twice in this way is to provide services such as QoS (Quality-of-Service). In addition to searching for Layer 3 IP addresses (SA, DA), information up to Layer 4 can be obtained. This is because it is necessary to identify the flow based on

If multiple CAM device accesses are performed during one bucket transfer, a mask setting command or search command is issued for each search. This can increase access to CAM devices and degrade network processor performance. Therefore, it is desired to improve the efficiency of command transfer at the time of accessing the CAM device in order to perform high-speed judgment processing such as packet path selection. Disclosure of the invention

SUMMARY OF THE INVENTION The present invention has been made in view of such a point, and an object of the present invention is to provide a data storage device capable of efficiently inputting a search request command to a content addressable memory (CAM) device.

Another object of the present invention is to provide an associative memory device capable of efficiently inputting a search request command.

Another object of the present invention is to provide an associative memory device utilization information search method capable of efficiently inputting a search request command to an associative memory device.

In the present invention, in order to solve the above problems, a data relay device as shown in FIG. 1 is provided. The data relay device of the present invention relays a packet to be transmitted, and includes a network processor 1, an associative memory device 2, and a memory device 3. Each element has the following functions.

When a packet is input, the network processor 1 uses a plurality of elements in the packet as search keys 11 and 12 and searches using the plurality of search keys 11 and 12 and the search keys 11 and 12 respectively. A search request 10 including a plurality of applied mask information 13 and 14 indicating the target range of is output. The associative memory device 2 stores a plurality of search target information, receives the search request 10 output from the network processor 1, and By analyzing the structure of the request 10, a plurality of search conditions including search keys 11, 12, applied mask information 13, 14 and power are generated, and the search target information is searched according to the search conditions. Outputs the memory address 21 uniquely associated with the detected search target information. The memory device 3 stores a plurality of search result candidates, and outputs a search result candidate stored in association with the memory address 21 output from the associative memory device 2 as a search result 22.

According to such a data relay device, when a packet is input, a search request 10 is generated by the network processor 1 and passed to the associative memory device 2. Then, the structure of the search request 10 is analyzed in the associative memory device 2, and a plurality of search conditions are generated. Then, in the associative memory device 2, a search according to the search condition is performed, and the memory address 21 corresponding to the detected search target information is output to the memory device 3. The search result candidate corresponding to the memory address 21 is output from the memory device 3 as the search result 22.

The above and other objects, features and advantages of the present invention will become apparent from the following description taken in conjunction with the accompanying drawings which illustrate preferred embodiments of the present invention. BRIEF DESCRIPTION OF THE FIGURES

FIG. 1 is a conceptual diagram of the invention applied to the embodiment.

FIG. 2 is a diagram illustrating a configuration example of a network system to which the first embodiment is applied.

FIG. 3 is a block diagram showing the internal configuration of the data relay device.

FIG. 4 is a diagram illustrating an example of a data structure of a search request.

FIG. 5 is a block diagram showing the internal configuration of the CAM device.

FIG. 6 is a diagram showing an outline of the search processing.

FIG. 7 is a diagram showing a search request analysis process.

FIG. 8 is a diagram showing an IP address search process.

FIG. 9 is a diagram illustrating a port number search process. FIG. 10 is a sequence diagram illustrating a service content determination process in the network processor according to the first embodiment.

FIG. 11 is a diagram illustrating a configuration example of the data relay device according to the second embodiment. FIG. 12 is a diagram illustrating a configuration of a CAM device according to the second embodiment. FIG. 13 is a diagram illustrating a search process according to the second embodiment.

FIG. 14 is a sequence diagram illustrating a service content determination process in the network processor according to the second embodiment.

FIG. 15 is a diagram illustrating a configuration example of a data relay device according to the third embodiment. FIG. 16 is a diagram illustrating a configuration example of a data relay device according to the fourth embodiment. FIG. 17 is a diagram showing a conventional route search process involving multiple CAM device accesses. BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, embodiments of the present invention will be described with reference to the drawings.

First, an outline of the invention applied to the embodiment will be described, and then, specific contents of the embodiment will be described.

FIG. 1 is a conceptual diagram of the invention applied to the embodiment. The data relay device according to the present invention is for relaying a packet to be transmitted, and includes a network processor 1, an associative memory device 2, and a memory device 3. Each element has the following functions.

When a packet is input, the network processor 1 uses a plurality of elements in the packet as search keys 11 and 12, and performs a search using the plurality of search keys 11 and 12 and the search keys 11 and 12 respectively. A search request 10 including a plurality of applied mask information 13 and 14 indicating the target range of is output. Which element of the packet # 2 is used as a search key is defined in the network processor 1 in advance.

The associative memory device 2 stores a plurality of pieces of search target information. Then, the associative memory device 2 receives the search request 10 output from the network processor 1. Then, the structure of the search request 10 is analyzed to generate a plurality of search conditions including the search keys 11 and 12 and the applied mask information 13 and 14. For example, one search condition is generated by combining the search key 11 and the applied mask information 13, and another search condition is generated by combining the search key 12 and the applied mask information 14. The generated search condition is stored in a predetermined register or the like.

After that, the associative memory device 2 searches for the search target information according to the generated search condition, and outputs the memory address 21 uniquely associated with the detected search target information to the memory device 3. Specifically, the associative memory device 2 excludes the area indicated by the applied mask information in the search condition from the search target, and searches for the search target information that matches the search key from the area to be searched. Then, the associative memory device 2 outputs the memory address of the storage area in which the detected search target information is stored to the memory device 3.

The memory device 3 stores a plurality of search result candidates, and retrieves the search result data stored in association with the memory address 21 output from the associative memory device 2 as the search result 22 to the network processor 1. Output to

According to such a data relay device, when a bucket is input, a search request 10 is generated by the network processor 1 and passed to the associative memory device 2. Then, the structure of the search request 10 is analyzed in the associative memory device 2, and a plurality of search conditions are generated. Then, in the associative memory device 2, a search according to the search condition is performed, and the memory address 21 corresponding to the detected search target information is output to the memory device 3. The search result candidate corresponding to the memory address 21 is output from the memory device 3 to the network processor 1 as the search result 22.

As described above, a plurality of search keys and application mask information are included in the search request, and the structure of the search request is analyzed in the continuous | memory device 2 to generate a plurality of search conditions. Even if multiple searches are required in one packet transfer, the search key and applied mask information can be transferred only once. As a result, search requests can be efficiently delivered and search efficiency can be improved. Hereinafter, embodiments of the present invention will be specifically described.

[First Embodiment]

FIG. 2 is a diagram illustrating a configuration example of a network system to which the first embodiment is applied. In the data, the relay device 100 has a plurality of physical ports 101-108. A network can be connected to the physical ports 101 to 108. A plurality of terminal devices 31 1-317 and other data relay devices 200 are connected to the data relay device 100 via a network. Terminal devices 318 and 319 are similarly connected to the other data relay devices 200.

FIG. 3 is a block diagram showing the internal configuration of the data relay device. The data relay device 100 includes a network processor 110, a CAM device 120, and a context RAMI 30. The network processor 110 and the CAM device 120 are connected by a search data input bus 141. The CAM device 120 and the context RAMI 30 are connected by an address bus 142 for inputting an address to the context RAMI 30. The context RAMI 30 and the network processor 110 are connected by a data path 143 for outputting data from the context RAMI 30. The network processor 110 is connected to each physical port 101-108. Each of the physical ports 101 to 108 is actually connected to the network processor 110 via a communication interface or the like, but is omitted in FIG.

The network processor 110 interprets the contents of the packet input from the physical ports 101 to 108 and extracts an IP address and a port number. Then, the network processor 110 outputs a search request to the CAM device 120 by using the IP address and the port number as a determination factor of route selection and service content (transfer rate and the like). At this time, the search request includes the judgment factor as a search key and a mask setting command for each search key. The search results for the search request are passed on to the context RAMI. For example, the port number of the physical port to which the packet should be forwarded is passed. The network processor 110 sends a packet according to the search result. Determine the transfer route of the port and output from the corresponding physical port.

The CAM device 120 searches for judgment factors such as an IP address of a terminal device connected via a network and a TCP / IP port number corresponding to an application mounted on the terminal device for data communication. It is stored as target information. The CAM device 120 performs a search on the stored search target information in response to a search request from the network processor 110. Then, the CAM device 120 outputs the memory address of the area where the detected search target information is stored to the context RAMI 30.

The context RAMI 30 stores search result candidates that can be search results corresponding to the search request output by the network processor 110. Search results suggestions include

This includes information indicating the packet transfer path and information indicating the service contents (transfer rate, etc.) for the packet. For example, it is the number of the physical port to which the packet should be sent, or information that instructs to discard the packet. Each search result candidate is associated with a judgment element stored in the CAM device 120. Specifically, the memory address in the CAM device 120 of the area where the judgment element is stored is the memory address in the context RAMI 30 of the area where the search result catch corresponding to the judgment element is stored.

When a memory address is input from the CAM device 120, the context RAMI 30 sets a search result candidate stored at the memory address as a search result, and passes the search result to the network processor 110.

FIG. 4 is a diagram illustrating an example of a data structure of a search request. The search request 400 includes a search key group 410 and a search command 420. The search key group 410 includes a plurality of search keys 411 and 412 for route determination and service content determination. For example, search key 411 is an IP address and search key 412 is a port number. The search command 420 includes a statement 421 and applicable mask information 422 and 423. In the statement 421, a statement instructing the CAM device 120 to execute the search is set. Applicable mask information 422, 423 contains search keys 411, 412 Information indicating a time mask is set. In the first embodiment, the identification numbers of the mask information defined in the CAM device 120 are indicated by the applied mask information 422 and 423.

FIG. 5 is a block diagram showing the internal configuration of the CAM device. As shown in FIG. 5, the CAM device 120 has a data storage circuit 121, command format definition information 122, a mask information group 123, an analysis circuit 124, a search condition storage unit 125, and a search circuit 126.

The data storage circuit 121 is a circuit block (CAM cell array) that stores information serving as a path determination element. The judgment factor is that the storage area is divided by type. In the example of FIG. 5, an area 121a for storing an IP address and an area 121 for storing a port number are provided.

The command format definition information 122 defines the data format of the search request shown in FIG. For example, from the beginning of search request 400, 32 bits are the first search key, the next 16 bits are the second search key, the next 16 bits are the statement, the next 8 bits are the first applied mask information, and the next 8 bits are the Contents such as the second applicable mask information are defined.

The command format definition information 122 can be rewritten by a CPU that controls the entire data relay device 100. Further, the setting content of the command format definition information 122 may be included in the search request, and the command format definition information 122 may be rewritten when the setting content is received.

In the mask information group 123, a plurality of mask information 123a, 123b, and 123m that specify an area to be excluded from the search target in the data storage circuit 121 are set. For example, MASK # 1 is mask information for masking areas other than the IP address storage area, and MASK # 2 is mask information for masking areas other than the port number storage area. An identification number is set in each of the mask information 123a, 123b, 123m. This identification number specifies the mask information to be provided at the time of the search.

The analysis circuit 124 analyzes the structure of the search request, and analyzes the search request from the search key and the applied mask information. Is generated. Specifically, upon receiving the search request, the analysis circuit 124 receives a plurality of search keys, command statements, and a plurality of applications in order from the beginning of the search request according to the definition content of the command format definition information 122. Extract mask information. Then, the analysis circuit 124 stores the set of the search key and the applied mask information in the search condition storage unit 125.

The search condition storage section 125 is a register group capable of storing a plurality of pairs of a search key and applicable mask information.

The search circuit 126 sequentially retrieves a set of the search key and the applicable mask information stored in the search condition storage section 125, and searches the data storage circuit 122. More specifically, the search circuit 126 refers to the mask information group 123 to extract mask information corresponding to the applied mask information extracted from the search condition storage unit 125. Next, the search circuit 126 searches the data storage circuit 122 for information matching the search key, excluding the area specified by the extracted mask information from the search target. When matching information is detected, the search circuit 126 outputs the memory address of the area where the information is stored to the context RAM I30.

The following processing is performed by the data relay device 100 configured as described above. First, when a packet is input, the network processor 110 analyzes the contents.

A search request including a search key and applicable mask information for each search key is generated by using a determination element such as a route selection as a search key. Among the information related to the input packet (including the information contained in the packet ゃ the reception status of the packet, etc.), information to be used as a judgment factor for route selection and the like is defined in advance in the network processor 110. I have. In the following example, the IP address and the port number are used as route selection judgment factors. Further, in the network processor 110, application mask information for each determination element is also defined in advance. Thereafter, a search according to the search request is performed.

FIG. 6 is a diagram showing an outline of the search processing. The network processor 110 extracts an IP address and a port number from a predetermined location of the header of the arriving bucket, and generates a search request. One search request is generated for one packet. The generated search request is input to the CAM device 120 via the search data input bus 141. The CAM device 120 performs a mask process on the data storage circuit 121, and searches the stored entries for the corresponding information 121c and 121d. If multiple search keys are included in the search request, the corresponding information is searched for each search key.

Then, the CAM device 120 sequentially inputs the memory address of the area in which the corresponding information is stored to the context RAM 130 via the end address path 142. Then, in the context RAMI 30, information 131 and 132 stored in an area corresponding to the input memory address are output via the data path 143. The information output via the data bus 143 is received by the network processor 110 as a search result.

The network processor 110 determines the processing of the input bucket (physical port to output, transfer rate, etc.) according to the search result.

Next, the internal processing of the CAM device 120 will be described in detail.

FIG. 7 is a diagram showing a search request analysis process. In the example of FIG. 7, the search key 510 of the search request 500 has the IP address “Add # 1” and the port number “8080” set as the search keys 511 and 512. In the search command 520, “Search” is set as the command statement 521, and “MASK # 1” and “MASK # 2” are set as the applied mask information 522 and 523. The applied mask information 522 indicates an applied mask of the search key 511, and the applied mask information 523 indicates an applied mask of the search key 512.

When such a search request 500 is input to the analysis circuit 124, the data structure of the search request 500 is analyzed according to the command format definition information 122. Then, the analysis circuit 124 stores a set of the search key 511 and the applied mask information 522 in the search condition storage unit 125 as one search condition. Next, a set of the search key 512 and the applied mask information 523 is stored in the search condition storage unit 125 as another search condition. When the search condition including the search key and the applied mask information is stored in the search condition storage unit 125, the search condition is retrieved by the search circuit 126 in the order of storage. Then, the search circuit 126 searches the data storage circuit 121 according to the extracted search conditions. In the example of FIG. 7, first, a search for the IP address “Ad d # l” is performed. FIG. 8 is a diagram showing an IP address search process. As shown in FIG. 8, the search circuit 126 extracts the search condition previously registered in the search condition storage unit 125, and obtains a search key 511 and application mask information 522. The search circuit 126 extracts the mask information 123a corresponding to “MASK # 1” set in the applicable mask information 522 from the mask information group 123, and masks the data storage circuit 121 (area not searched). Is determined. In the example of FIG. 8, the area 121a storing the IP address is a search target, and the area 121b storing the port number is not a search target.

Next, the search circuit 126 searches for data matching the search key 511 from within the search target area 121a. Then, the search circuit 126 acquires the memory address of the area where the matched data is stored, and outputs the acquired memory address to the context RAMI 30. Then, search result candidates stored in the area corresponding to the input memory address are extracted from the context RAMI 30 and sent to the network processor 110 as search results. This completes the Layer 3 search process.

When a series of search processing related to the IP address “Ad d # l” is completed, the search circuit 126 performs a search based on the next search key in the search condition storage unit 125 and the applied mask information. In the example of FIG. 7, a search for the port number “8080” is performed.

FIG. 9 is a diagram illustrating a port number search process. As shown in FIG. 9, the search circuit 126 extracts the information registered first in the search condition storage unit 125 at that time, and obtains the search key 512 and the applied mask information 523. The search circuit 126 extracts the mask information 123b corresponding to “MASK # 2” set in the applied mask information 523 from the mask information group 123, and extracts the mask area (the area not to be searched) of the data storage circuit 121. decide. In the example of FIG. 9, the area 121a in which the IP address is stored is out of the search target, and the area 121b in which the port number is to be stored is the search target. Next, the search circuit 1 26 searches the area 1 2 1 b to be searched for data matching the search key 5 1 2. Then, the search circuit 126 acquires the memory address of the area where the matched data is stored, and outputs it to the context RAM I 30. Then, the search result candidates stored in the area corresponding to the memory address are extracted from the context RAM I 30 and sent to the network processor 110 as search results. This completes the Layer 4 search process.

Next, a description will be given of a processing procedure of the network processor when providing an additional service according to the contents of a contract between the sender of the packet and the administrator of the data relay device according to the contents of the input packet. .

FIG. 10 is a sequence diagram illustrating a service content determination process in the network processor according to the first embodiment. Hereinafter, the processing illustrated in FIG. 10 will be described along the step numbers.

[Step S 1] Upon receiving the bucket, the network processor 110 generates one search request by combining the search key such as the IP address and port number of the transmission source and the applied mask information for each search key. .

[Step S 2] The network processor 110 outputs the generated search request to the search data input bus 144. As a result, a search corresponding to the search key is performed in the CAM device 120.

[Step S 3] The network processor 110 receives a search result when the IP address is used as a search key, from the data path 144 of the context RAM I 30. Then, the network processor 110 processes the received search result and recognizes the sender (subscriber) who transmitted the packet.

[Step S4] The network processor 110 receives a search result using the port number as a search key from the data bus 144 of the context RAM I30. Then, the network processor 110 processes the received search result and recognizes the service class.

In this way, the search request from the network processor 110 is sent to one packet. By performing the transfer only once, the search request can be transmitted efficiently via the search data input path 141. In addition, since the application mask can be specified for each search key in the search request, the search target area can be limited in the CAM device, and the search efficiency is improved.

[Second embodiment]

In the second embodiment, search results executed based on one search request are combined and returned to the network processor. That is, in the first embodiment, when a search request includes a plurality of search keys, a plurality of searches are performed, and a search result is output from the context RAM each time. At this time, the network processor receives multiple search results for one search request. Therefore, processing to determine the relevance of multiple search results is required in the network processor. On the other hand, in the second embodiment, a plurality of search results are compiled in the CAM device and then transmitted to the network processor. This simplifies the processing in the network processor, and speeds up the packet transfer processing.

FIG. 11 is a diagram illustrating a configuration example of the data relay device according to the second embodiment. The data relay device 600 has a plurality of physical ports 600 to 608, a network processor 610, a CAM device 620, and a physical port 6 having a context RAM 630. 0 1 to 6 0 8 are connected to the network processor 6 10. The network processor 610 and the CAM device 620 are connected by an input / output bus 640. The CAM device 62 and the context RAM 60 are connected by an address bus 642 and a data bus 643.

Here, the network processor 610 transmits a search request for route selection regarding the bucket input from the physical port to the CAM de-compiler 6200. This search request shall include multiple search keys.

The CAM device 620 performs a search according to the search key. C AM device 6 2 0 Inputs the memory address obtained as a result of the search using the search key to the context RAM 6330 via the address path 642. Then, from the context RAM 630, data corresponding to the input memory address is output from the data bus 634.

The output result of the context RAM 630 performed multiple times is returned to the CAM device 620 and stored in a register or the like for each search result. When all the search results corresponding to the search request are stored in the register, the CAM device 620 transfers the plurality of search results to the network processor 610 as a group of search results. To realize such processing, it is necessary to provide a register for storing the search result in the CAM device 620.

FIG. 12 is a diagram illustrating a configuration of a CAM device according to the second embodiment. As shown in FIG. 12, the CAM device 620 has a data storage circuit 621, a command format definition information 622, a mask information group 623, an analysis circuit 624, and a search condition storage unit 622. 5. It has a search circuit 626, a search result storage section 627, and an output circuit 628. Here, each component shown in FIG. 12 has the following function in addition to the function of the element of the same name in the first embodiment shown in FIG.

The analysis circuit 624 has the same function as the analysis circuit 124 in the first embodiment shown in FIG. 5, and further includes the identification information of the search request and the search key included in the search request. And a function of adding the number of search conditions to the search condition. For example, the analysis circuit 624 generates a search condition based on a search key, applied mask information, an identification number of each input search request, and information indicating the number of search keys in the search request. 25 Store in the register in 5.

Each register in the search condition storage unit 6 25 has a data capacity enough to store the search request identification information and the number of search keys in addition to the search key and the applied mask information. Transmits the memory address obtained by the search of the data storage circuit 621 to the context RAM 630, and at the same time, transmits the memory address obtained by the search key. The identification information of the search request and the number of search keys are stored in a register in the search result storage section 627. The search result output from the context RAM630 is also stored in the register. As a result, the search result output from the context RAM 630 is associated with the identification information of the search request and the number of search keys included in the search request. The search result storage section 627 is composed of a plurality of registers for storing identification information, the number of search keys, and the search result output from the context RAM 630.

The output circuit 628 refers to the information stored in the search result storage unit 627, and when the search results corresponding to the search request are stored by the number of search keys included in the search request, the search is performed. The results are compiled and passed to the network processor 6 10.

FIG. 13 is a diagram illustrating a search process according to the second embodiment. For example, the first search hits entry 651, and its memory address is input to context RAM 630 via address bus 640. Then, information 652 corresponding to the input memory address is passed to the CAM device 62 through the data bus 643 as a search result. In the CAM device 62, the information 652 sent as the search result is stored in a register in the search result storage unit 627.

In the subsequent second search, entry 661 is hit, and its memory address is input to context RAM 6330 via address path 642. Then, information 626 corresponding to the input memory address is passed to the CAM device 620 via the data bus 640 as a search result. In the CAM device 620, the information 626 transmitted as a search result is stored in a register in the search result storage unit 627.

If only two search keys are included in the search request, the number of search results corresponding to the search request becomes two, and the search results are integrated and are connected via the I / O bus 641 Sent to the network processor 6 10.

Next, a description will be given of the network processor processor jl when providing additional services according to the contract between the sender of the packet and the administrator of the data relay device according to the contents of the input bucket. I do.

FIG. 14 is a diagram showing a service in the network processor according to the second embodiment. It is a sequence diagram which shows a capacity determination process. Hereinafter, the processing illustrated in FIG. 14 will be described along the step numbers. ,

[Step S11] Upon receiving the packet, the network processor 610 generates one search request by combining the search key such as the IP address and port number of the transmission source and the applied mask information for each search key. I do.

[Step S12] The network processor 610 outputs the generated search request to the input / output bus 641. As a result, a search corresponding to the search key is performed in the CAM device 620. Then, in the CAM device 620, a plurality of search results are put together.

[Step S 13] The network processor 6 10 is connected to the input / output bus 6 4 1

The search result when the IP address is used as the search key and the search result when the port number is used as the search key are received. Then, the network processor 610 processes the received search result and recognizes the sender (subscriber) who transmitted the packet and the service class.

In this way, a single search request from the network processor can return the search result once. As a result, there is no need for the network processor 6110 to process the search results by V.

That is, in general, the time required for entry search may differ depending on the search bit width of the CAM device. Therefore, the timing of issuing addresses to the context RAM may be shifted. According to the second embodiment, the network processor can collectively receive a plurality of search results, and the difference in the time required for each search in the CAM device, that is, the timing of the result output from the context RAM. This eliminates the need for processing for determining the relevancy of search results with attention to the mining.

[Third embodiment]

In the third embodiment, the present invention is applied to a data relay device having a plurality of network processors.

FIG. 15 is a diagram illustrating a configuration example of a data relay device according to the third embodiment. As shown in FIG. 15, the data relay device according to the third embodiment has a plurality of network processors 701, 702, 703, a CAM device 704, and a context RAM 705.

The network processor 701 is connected to the CAM bus 721 via the output interface 711. The network processor 702 is connected to the CAM bus 721 via an output interface 712. The network processor 703 is connected to the CAM bus 721 via the output interface 713. The CAM bus 721 is connected to the CAM device 704 via the input interface 722. The CAM bus 721 has an arbitration function for multiple data transfer requests (processing for the network processor to become a bus master that can occupy the bus).

The CAM device 704 is connected to the context RAM 705 via an output interface (address bus of the context RAM 705) 723. The context RAM 705 is connected to a context RAM path 725 via an output interface (data bus of the context RAM 705) 724. The context RAM bus 725 is connected to the network processor 701 via the input interface 731. The context RAM bus 725 is connected to the network processor 702 via an input interface 732. The context RAM bus 725 is connected to the network processor 703 via the input interface 733.

Each of the network processors 701, 702, and 703 issues a search request including a search key, applicable mask information, and a search command from the output interfaces 711, 712, and 713 to the CAM device 704, respectively. This search request is input to the CAM device 704 after arbitration in the CAM path 721. Then, the CAM device 704 performs a search. The information hit or missed in the search processing is input to the context RAM 705 as a read address. Here, the search may be repeated several times. The data of the corresponding address in the context RAM 705, that is, the search result is output from the output interface 724 of the context RAM 705 and passed to the network processor which issued the search request.

As described above, if the present invention is applied to a data relay device having a plurality of network processors 701 to 703, a search request between the network processors 701 to 703 is performed only once for a frame to be transferred. The arbitration processing load in 721 is reduced. As a result, it is possible to smoothly transfer search requests.

[Fourth embodiment]

In the fourth embodiment, a function for collecting search results in a right device in data having a plurality of network processors is mounted on a CAM.

FIG. 16 is a diagram illustrating a configuration example of a data relay device according to the fourth embodiment. As shown in FIG. 16, the data relay device according to the fourth embodiment has a plurality of network processors 801, 802, 803, a CAM device 804, and a context RAM 805.

The network processor 801 is connected to a CAM bus 821 via an input / output interface 81 1. The network processor 802 is connected to the CAM bus 821 via an input / output interface 812. The network processor 803 is connected to the CAM bus 821 via an input / output interface 813. The CAM bus 821 is connected to a CAM device 804 via an input / output interface 822. The CAM path 821 has a function of arbitrating a plurality of data transfer requests (processing for the network processor to become a path master that can occupy the path). The CAM device 804 is connected to the context RAM 805 via an input / output interface 823 (including an address bus and a data bus) with the context RAM 805.

Note that the CAM device 804 has the same internal configuration as the CAM device 620 according to the second embodiment shown in FIG. In the data relay device having such a configuration, each of the network processors 801, 802, 803 uses a search key, mask information, Issues a search request that includes a search command. The search request is arbitrated by the CAM bus 822 and passed to the CAM device 804 via the input / output interface 822. The CAM DePay 804 performs a search in response to a search request. The information hit or missed in the search process of the CAM device 804 is input to the context RAM 805 via the input / output interface 823 as an address to the context RAM 805. Then, the data of the corresponding address, that is, the search result is output from the context RAM 805 to the CAM device 804 via the input / output interface 823.

If one search request includes a plurality of search keys, the CAM device 804 holds the obtained search results until a search result corresponding to each search key is obtained. Then, when all the search results based on the same search request are obtained, the CAM device 804 collects the search results and returns the result to the network processor that issued the search request.

In each of the above embodiments, only one CAM device and one context RAM are shown in the data relay device, but each CAM device and context RAM is limited to one chip. Not something. In other words, if memory space is required, each CAM device and context RAM can be composed of multiple chips. However, individual chips do not individually perform processing, and a plurality of chips are integrated to realize the processing of the CAM device and the context RAM of the above embodiment.

As described above, in the present invention, a plurality of search keys and applied mask information are output in one search request, the search request is analyzed in the associative memory device, and a search condition including the search key and the applied mask information is obtained. Generated. Therefore, even if multiple searches for the associative memory device are required to transfer one packet, only one transfer of the search request is required. As a result, the retrieval key is efficiently exchanged, and the retrieval process can be made more efficient. The above merely illustrates the principles of the invention. In addition, many modifications and changes will be apparent to those skilled in the art and the present invention is not limited to the exact configuration and application shown and described above, but all corresponding modifications and equivalents may be made It is considered the scope of the present invention by the appended claims and their equivalents.

Claims

The scope of the claims

1. To the data relay device that relays the transmitted packet!

When the packet is input, a plurality of elements in the packet are used as search keys, and a search including a plurality of the search keys and a plurality of applied mask information indicating a search target range by each of the search keys is performed. A network processor for outputting the request,

It stores a plurality of search target information, receives the search request output from the network processor, analyzes a structure of the search request, and generates a plurality of search conditions including the search key and the applied mask information. An associative memory device that generates, searches for the search target information according to the search condition, and outputs a memory address uniquely associated with the detected search target information;

A memory device that stores a plurality of search result candidates, and outputs the search result candidates stored in association with the memory address output from the associative memory device as search results;

A data relay device comprising:

2. The memory device according to claim 1, wherein the memory device outputs the search result candidate stored in a data storage area corresponding to the memory address to the network processor as a search result. The data relay device according to the above.

3. The memory device according to claim 1, wherein the memory device outputs the search result candidate stored in a data storage area corresponding to the memory address to the associative memory device as a search result. The data relay device according to the item.

4. The associative memory device stores the search result returned according to the output memory address in a buffer, and combines the search results for each of the search keys included in the search request into one to the network processor. 4. The data relay device according to claim 3, wherein the data relay device outputs the data.

5. The plurality of network processors are provided, and the search requests output from the plurality of network processors are transmitted via a common bus for arbitration. 2. The data relay device according to claim 1, wherein the data relay device outputs the data.

6. The associative memory device excludes the storage area specified by the applied mask information from the search target, and searches the storage area to be searched for the search target information that matches the search key. The data relay device according to claim 1, characterized in that:

7. The associative memory device stores a plurality of pieces of mask information indicating storage areas not to be searched in advance, and applies the mask information specified by referring to the applied mask information. 7. The data relay device according to claim 6, wherein the search key corresponding to information is searched.

8. The associative memory device has a register group for storing a plurality of the search conditions. Each time the search request is received, the search condition is stored in the register group, and is stored first. 2. The data relay device according to claim 1, wherein the data relay device is sequentially extracted from the search condition, and performs a search process according to the extracted search condition.

9. The data according to claim 1, wherein the associative memory device has definition information defining a data structure of the search request, and analyzes the search request according to the definition information. Middle, joint device.

10. In an associative memory device having a search function of stored search target information, a data storage circuit storing a plurality of search target information;

When a search request including a plurality of search keys and a plurality of application mask information indicating a range to be searched by each of the search keys is input, the structure of the search request is analyzed and the search key and the applied mask are analyzed. An analysis circuit for generating a plurality of search conditions composed of information; and searching the data storage circuit for the search target information corresponding to the search condition searched by the search circuit. A search circuit that outputs a uniquely associated memory address;

A content addressable memory device, comprising: 1 1 · It further has a plurality of register groups,

The analysis circuit stores the search condition generated by analyzing the search request in the register group,

The associative memory device according to claim 10, wherein the search circuit extracts the search conditions in the order in which the search conditions are stored in the register group, and performs a search process according to the extracted search conditions. .

1 2. An associative memory device utilization information retrieval method for retrieving information related to a packet using an associative memory device.

In the network processor, a plurality of input elements in the bucket are used as a search key, and a search request including a plurality of the search keys and a plurality of application mask information indicating a search target range by each of the search keys is provided. Output,

Analyzing the structure of the search request to generate a plurality of search conditions including the search key, the applied mask information, and a plurality of search conditions;

In the associative memory device, the search target information corresponding to the search condition is searched from a plurality of search target information stored in advance and uniquely associated with the search target information corresponding to the search condition. Output the memory address

Outputting, as a search result, the search result candidate stored from the memory device storing the plurality of search result candidates in association with the memory address;

A method for retrieving information using associative memory devices.