JP5206441B2 - Packet identification apparatus, method and program - Google Patents

Description

  The present invention relates to a packet identification device, method, and program, and can be applied, for example, in a network such as an IP (Internet Protocol) network to identify a flow related to a packet from header information of the received packet.

  In the conventional packet identification method, generally, information (for example, all or a part of header information) of a packet to be identified is stored in advance in a content addressable memory (CAM), and information extracted from the input packet is stored. The CAM is searched based on the result, “packet discard”, “packet transfer destination”, “priority of packet transfer” and the like are determined based on the search result, and the packet is transferred appropriately. Here, the search condition set in the CAM has the same bit width as the packet information to be extracted, and is set in the CAM by the number of registrations (number of entries) to identify the input packet (Patent Document 1). reference).

JP 2008-17216 A

  However, in the conventional packet identification method, the capacity of the CAM has to be increased in order to increase the search target information or increase the number of identification target packets. Due to the specification restrictions related to the capacity of the CAM, the above-described increase in information and the increase in the number of identification target packets may not be met. Even if a high-capacity CAM can be used, the use of the high-capacity CAM increases the cost.

  In particular, in the case of an IP packet, the search target information included in the packet is expected to increase significantly with the shift from IPv4 (IP version 4) to IPv6 (IP version 6). In recent years, IPv6 has been introduced to cope with scalable network architecture, improved security, and integration of service quality functions. In IPv6, the configuration of the IP header has been simplified and packet processing overhead has been reduced. The bit width (search target information) necessary for identification is increasing such that the address and destination address are 128 bits compared to 32 bits in the conventional IPv4.

  On the other hand, in actual operation, there are cases where a plurality of identification target packets are handled collectively and processing is performed on a plurality of identification target packets, and storing all information of a plurality of identification target packets that can be input is not possible. Inefficient.

  Therefore, there is a demand for a packet identification device, method, and program that can reduce the capacity of search target information stored in advance for packet identification.

In the first aspect of the present invention, the packet information extraction unit extracts the packet identification information from the input packet, and the search processing unit matches the extracted packet identification information with the packet identification information stored in the storage unit in advance. In the packet identification device for determining whether or not (1) the storage means is (1-1) the remaining elements excluding some elements constituting the packet identification information are the corresponding elements in the extracted packet identification information A remaining element collating storage unit configured to be able to collate whether or not they match, and (1-2) the partial element corresponding to the remaining element defined in the remaining element collating storage unit A partial element matching storage unit configured to be able to check whether or not the corresponding element in the extracted packet identification information matches, (2) the search processing means includes (2-1) ) A remaining element search unit for determining whether or not a remaining element in the received packet identification information matches any remaining element stored in the remaining element matching storage unit; and (2-2) the remaining element. When the search unit determines that there is a remaining element stored in the remaining element matching storage unit that matches the remaining element in the extracted packet identification information, one of the extracted packet identification information A partial element search unit that determines whether or not the partial element matches any partial element specified by the information stored in the partial element matching storage unit , (3) The partial element matching storage unit includes information indicating whether the values of one or more partial elements corresponding to the remaining elements defined in the remaining element matching storage unit are continuous or non-continuous. and characterized in that the de

According to the second aspect of the present invention, the packet information extraction unit extracts packet identification information from the input packet, and the search processing unit matches the extracted packet identification information with the packet identification information stored in advance in the storage unit. In the packet identification method for determining whether or not (1) as the storage means, (1-1) the remaining elements excluding some elements constituting the packet identification information are the corresponding elements in the extracted packet identification information A remaining element collating storage unit configured to be able to collate whether or not they match, and (1-2) the partial element corresponding to the remaining element defined in the remaining element collating storage unit , a part whether matches the corresponding element is configured to enable collation element collation storage unit in the extracted packet identification information, defined above balance element matching storage unit Corresponding to the rest elements are, by preparing a part element matching storage unit the value of one or more of the part element contains information indicating discontinuous whether continuous, (2) above The remaining element search unit in the search processing means determines whether or not the remaining element in the extracted packet identification information matches any of the remaining elements stored in the remaining element matching storage unit (3 ) The partial element search unit in the search processing means matches the remaining element in the extracted packet identification information in the remaining elements stored in the remaining element matching storage unit. Whether or not a partial element in the extracted packet identification information matches any partial element specified by the information stored in the partial element matching storage unit when it is determined that there is a packet Determine And wherein the door.

A third aspect of the present invention is a packet identification program for extracting packet identification information from an input packet and determining whether or not the extracted packet identification information matches packet identification information stored in advance. 1) The remainder configured to enable the computer to check whether or not (2) the remaining elements excluding some elements constituting the packet identification information match the corresponding elements in the extracted packet identification information. It is possible to verify whether the partial element corresponding to the remaining element defined in the element matching storage unit and the remaining element matching storage unit matches the corresponding element in the extracted packet identification information. a part element matching storage unit configured to correspond to the rest element defined above balance element matching storage unit, the value of one or more of the part elements communicating A storage means comprising a part element matching storage unit which contains information indicating that either a non-continuous or with, (3) the balance elements in the extracted packet identification information is stored in the remainder element matching storage unit The remaining element search unit that determines whether or not the remaining element matches any of the remaining elements, and the remaining element search unit are extracted from the remaining elements stored in the remaining element matching storage unit. Any part of the extracted packet identification information is identified by the information stored in the partial element matching storage unit when it is determined that there is a match with the remaining element in the packet identification information. It is made to function as a search processing means provided with the partial element search part which discriminate | determines whether it matches with a partial element of.

  According to the present invention, the capacity of search target information stored in advance for packet identification can be reduced.

It is explanatory drawing which shows the detail of the search process part and CAM in the packet identification device of embodiment. It is a block diagram which shows the whole structure of the packet identification device of embodiment. It is a flowchart which shows operation | movement (packet identification method) of the packet identification apparatus of embodiment.

(A) Main Embodiment Hereinafter, an embodiment of a packet identification device, method, and program according to the present invention will be described in detail with reference to the drawings.

(A-1) Configuration of Embodiment FIG. 2 is a block diagram illustrating the overall configuration of the packet identification device of the embodiment. The packet identification device according to the embodiment is mounted on a device having a function of receiving a packet and a function of transferring a packet. A device equipped with a packet identification device may be a general-purpose device such as a personal computer as well as a dedicated device that receives a packet related to predetermined data (for example, content). In the latter case, the packet identification device is mainly composed of a CPU and a program executed by the CPU, but even in this case, it can be functionally represented in FIG.

  2, the packet identification device 100 according to the embodiment includes a packet information extraction unit 101, a search processing unit 102, and a CAM (associative memory) 103.

  The packet information extraction unit 101 extracts information necessary for identifying the packet from the input packet. The packet information extraction unit 101 gives the extracted packet information to the search processing unit 102.

  The CAM 103 stores information on a packet to be identified. In the case of this embodiment, the CAM 103 includes two tables, which will be described later, so that a range matching search can be performed.

  The search processing unit 102 applies the extracted packet information, performs a search process on the CAM 103, and acquires a search result from the CAM 103. The search processing unit 102 performs a re-search process on the CAM 103 as necessary based on the acquired search results. The first search is a search for whether or not it belongs to the range, and the second search (re-search) is a search for whether or not it is valid within the range. The search processing unit 102 outputs a search result indicating whether or not the input packet identification information is entered in the CAM 103.

  The method of using the search result is not related to the features of this embodiment and is arbitrary. For example, in the case where identification information of a packet to be discarded is entered and identified in the CAM 103, the input packet is discarded when a search result indicating entry is output. Also, for example, if the identification information of a packet to be transferred to another device is entered and identified in the CAM 103, the input packet is transferred to the other device when a search result indicating entry is output. The Further, for example, in the case where identification information of a packet having a higher processing priority than other packets is entered and identified in the CAM 103, when a search result indicating entry is output, the input packet is It is processed with priority over other packets.

  FIG. 1 is an explanatory diagram showing details of the search processing unit 102 and the CAM 103 shown in FIG. 2, and the same parts as those in FIG. FIG. 2 shows a case where the input packet is an IP packet (IPv6 packet) according to IPv6.

  As shown in FIG. 1, the CAM 103 includes a first RM (Range Matching) table 202 and a second RM table 203. The search processing unit 102 has an RM entry storage unit 204.

  The configuration of the first RM table 202 is shown in a configuration diagram 206 located in FIG. The first RM table 202 includes, in each entry (each record), five pieces of information SrcIP (source IP address), DstIP (destination IP address), and PID (protocol indicating whether the protocol is TCP or UDP). Stored are values in which SrcIP, DstIP, PID, and SrcPort other than DstPort are specified among protocol identification), SrcPort (source port number), and DstPort (destination port number). Here, the first RM table 202 may not include the DstPort column, and may include the DstPort column, which describes that any value may be included in the column. Also good. In the embodiment, since the value of DstPort is used as a range defining element, it is an entry that can handle packet transfer processing in a batch.

  The RM entry storage unit 204 has a record (row) corresponding to each entry (each record) in the first RM table 202, and the entry number (address number; figure in the first RM table 202). The record of the RM entry storage unit 204 is specified by (not shown). The RM entry storage unit 204 stores information defining a range to which DstPort belongs among the five pieces of identification information of the identification target packet.

  The record of the RM entry storage unit 204 defines a continuous / non-consecutive flag F, a range start number Start, and a range end number End. The continuous / non-continuous flag F describes a flag indicating whether it is a range search target (continuous entry) or not a range search target (non-continuous entry). In the example of FIG. 1, flag F = 1 represents a continuous entry, and flag F = 0 represents a non-continuous entry. In the non-continuous entry, the range start number Start and the range end number End have no meaning, and are blank or meaningless values are stored.

  The configuration of the second RM table 203 is shown in a configuration diagram 207 located in FIG. The second RM table 203 identifies a DstPort for each entry (each record) in the first RM table 202 in which the flag F of the RM entry storage unit 204 represents a non-consecutive entry. The value of is described.

  For example, the relationship between DstPorts of a plurality of identification target packets having the same set of SrcIP, DstIP, PID, and SrcPort among the five pieces of information is examined. If the DstPort of a plurality of identification target packets constitutes a continuous value range, it becomes a continuous entry, and if it does not constitute a continuous value range, it becomes a non-continuous entry, and stores the first RM table 202 and the RM entry. The value is registered in the unit 204 and the second RM table 203.

(A-2) Operation of Embodiment Next, the operation (packet identification method of the embodiment) of the packet identification device 100 of the embodiment will be described with reference to the flowchart of FIG.

  When a packet is input, first, the value of information (SrcIP, DstIP, PID, SrcPort, DstPort) used for identification is extracted from the packet (step S1). Assume that a packet 201 having SrcIP as SA, DstIP as DA, PID as TCP, SrcPort as SP, and DstPort as DP as shown in FIG.

  Next, of the extracted five pieces of information, the first RM table 202 is searched based on the values SA, DA, TCP, and SP of SrcIP, DstIP, PID, and SrcPort (step S2). It is determined whether or not (step S3).

  If the corresponding entry cannot be searched in the search for the first RM table 202, a result indicating that the input packet 201 is not an identification target packet is output (step S4).

  On the other hand, if the corresponding entry can be searched by searching the first RM table 202, the RM entry is based on the number of the searched entry (the address of the CAM 103 (first RM table 202)). Information on the entry is acquired from the storage unit 204 (step S5), and it is determined whether the entry is a continuous entry or a discontinuous entry (step S6). In the configuration example of the first RM table 202 shown in FIG. 1 described above, entries having the extracted SrcIP, DstIP, PID, and SrcPort values SA, DA, TCP, and SP exist in the first RM table 202. When the information is acquired from the RM entry storage unit 204 based on the entry number, F = 1, Start = 1, and End = 5 are obtained.

  When it is determined that the entry is a continuous entry, it is further determined whether or not the value DP of DstPort extracted from the input packet is a value within the continuous range defined by the acquired Start and End (step S7). . If the value DP is out of the continuous range, the input packet 201 outputs a result indicating that the packet is not an identification target packet (step S4). If the value DP is within the continuous range, the input packet 201 outputs a result indicating that the packet is an identification target packet (step S8). In the example shown in FIG. 1 described above, since F = 1, it is determined that the entry is a continuous entry, and since Start = 1 and End = 5, it is confirmed whether the value DP belongs to a range of 1 or more and 5 or less. . For example, if the value DP is 2, the result that the input packet 201 is the identification target packet is output, and if the value DP is 8, the result that the input packet 201 is not the identification target packet is output. Is output.

  If it is determined in step S6 that the entry is a non-consecutive entry, based on the retrieved entry number (the address of the CAM 103 (first RM table 202)), the second RM table 203 Information about the entry is acquired (step S9), and it is determined whether or not the acquired information includes the value DP of DstPort extracted from the input packet (step S10). If the value DP of DstPort extracted from the input packet is not included in the information acquired from the second RM table 203, a result indicating that the input packet 201 is not an identification target packet is output (step S4). If it is included in the information acquired from the second RM table 203, a result indicating that the input packet 201 is an identification target packet is output (step S8). The above-described example shown in FIG. 1 shows the case of continuous entries. However, it is assumed that F = 0 is a non-continuous entry and information is acquired from the second RM table 203. As shown in FIG. 1, if the values 1, 3, and 5 are acquired, for example, if the value DP is 3, the result that the input packet 201 is an identification target packet is output, and the value DP is If it is 4, a result indicating that the input packet 201 is not an identification target packet is output.

  The above operation is repeatedly executed each time a packet is input, and a search result as to whether or not each input packet is an identification target packet (processing target packet) is output to each input packet.

  Hereinafter, the operation will be described more specifically.

[Operation Example 1]
Assume that SrcIP is SA, DstIP is DA, PID is TCP, SrcPort is SP, and a packet whose DstPort is any one of 1 to 5 is transferred, and other packets are discarded.

  In this case, the entry setting in the first RM table 202 is set to SA, DA, TCP, and SP with search targets other than DstPort as shown in the configuration diagram of FIG. The setting in the RM entry storage unit 204 is such that F = 1, Start = 1, and End = 5 are set to the first RM table 202 because DstPort of the search processing target packet can be expressed in a continuous range of 1 to 5. Set to an address corresponding to the entry address.

  Assume that packet information of SrcIP = SA, DstIP = DA, PID = TCP, SrcPort = SP, and DstPort = 2 is extracted in such a setting state.

  As a result of the search with respect to the first RM table 202, there is a corresponding entry without depending on DstPort, so the search processing unit 102 acquires the entry address. By referring to the RM entry storage unit 204 using the acquired entry address, it is determined that the packet is a continuous entry (F = 1) in DstPort. Therefore, whether the DP that is the DstPort value of the input packet is within the range of Start and End is compared, and a result that is within the range and is a transfer target is output.

  As a result, the input packet 201 is transferred without being discarded.

[Operation example 2]
Assume that SrcIP is SA, DstIP is DA, PID is TCP, SrcPort is SP, and a packet whose DstPort is 1, 3 or 5 is transferred, and other packets are discarded.

  In this case, the entry setting in the first RM table 202 is set to SA, DA, TCP, and SP with search targets other than DstPort as shown in the configuration diagram of FIG. Also, since the setting in the RM entry storage unit 204 is non-continuous with DstPort being 1, 3 or 5, F = 0 is set to an address corresponding to the entry address of the first RM table 202. Set. Furthermore, the entry setting to the second RM table 203 is that packets whose DstPort is 1, 3 or 5 are transferred, so that 1, 3 and 5 are set to the entry addresses (or the first RM table 202) (or Address corresponding to the address of the RM entry storage unit 204).

  Assume that packet information of SrcIP = SA, DstIP = DA, PID = TCP, SrcPort = SP, and DstPort = 3 is extracted in such a setting state. By referring to the RM entry storage unit 204 using the acquired entry address, it is found that the packet is a non-continuous entry (F = 0) in DstPort. Therefore, the second RM table 203 is searched for the value 3 of the DstPort of the input packet. When the value 3 of DstPort corresponding to the second RM table 203 exists, a result indicating that it is a transfer target is output.

  As a result, the input packet is transferred without being discarded.

(A-3) Effect of Embodiment According to the above-described embodiment, it is possible to reduce the amount of CAM used while handling the same number of packet information as compared with the conventional method. Or according to the said embodiment, it becomes possible to process more packet information than before, applying CAM of the same capacity | capacitance as the conventional method.

  Hereinafter, it will be described with a specific example that the amount of CAM used can be suppressed when the same number of packet information is handled.

  In the conventional case, the number of bits of one entry is 296 bits in total in SrsIP, DstIP, PID, SrcPort, and DstPort. The number of CAM use bits of 10 entries is 2,960 bits = 296 bits × 10 entries.

  In the case of continuous entry in the embodiment, the number of bits of one entry is 296 bits in total in SrsIP, DstIP, PID, SrcPort, and DstPort. If 10 entries are continuous, only one entry of the CAM is required, and 296 bits = 296 bits × 1 entry. In other words, compared with the above-described conventional case, the amount used is 10%.

  In the case of non-consecutive entries in the embodiment: The number of bits of one entry is 296 bits in total in SrsIP, DstIP, PID, SrcPort, and DstPort. Even if 10 entries are discontinuous, only one entry is required in the first RM table 202. In the second RM table 203, 10 entries of DstPort (16 bits) are used. As a result, the amount used in the CAM is 456 bits = (296 bits × 1 entry) + (16 bits × 10 entries). That is, compared with the above-mentioned conventional case, the amount used is about 15%.

(B) Other Embodiments In the above embodiment, the parameter (extraction information from the packet) for determining whether the range is the continuous range or the non-continuous range is not considered in the entry to the first RM table 202. While some have been shown, other parameters can be used as well.

  The number of such parameters is not limited to one. For example, SrcPort and DstPort are set as parameters to be discriminated, and those having the same SrsIP, DstIP, and PID are entered into the first RM table 202, and continuous / non-continuous information about SrcPort and , The continuous / non-continuous information regarding DstPort may be written together, and the non-continuous information for SrcPort and the non-continuous information for DstPort may be stored in the second RM table 203.

  The information distribution to the plurality of storage units is not limited to that in the above embodiment. For example, the second RM table 203 may be omitted, and the RM entry storage unit 204 may also store the storage information of the second RM table 203. Further, for example, if the first RM table 202 (or the second RM table 203) is realized by a memory other than the CAM, the first RM table 203 and the RM entry storage unit 204 are merged. You may make it comprise.

  In the above-described embodiment, the two states related to the range are continuous and non-continuous, but other states may be used. A state where the elements in the range are odd numbers, a state where the elements in the range are even numbers, or the like may be applied. For example, in the case of an odd number, a flag value indicating the odd number is prepared, and an odd start value and end value are described in the RM entry storage unit 204, and the value extracted from the input packet is an odd value within the corresponding range. Check if it is a numerical value.

  In the above embodiment, the case where the packet to be identified is an IPv6 packet has been described as an example. However, the present invention can be similarly applied to packet identification according to another protocol.

  DESCRIPTION OF SYMBOLS 100 ... Packet identification apparatus, 101 ... Packet information extraction part, 102 ... Search processing part, 103 ... CAM (associative memory), 202 ... 1st RM (Range Matching) table, 203 ... 2nd RM table, 204 ... RM entry storage.

Claims (5)

A packet information extracting unit extracts packet identification information from an input packet, and a search processing unit determines whether or not the extracted packet identification information matches the packet identification information stored in the storage unit in advance. In the identification device,
The storage means
A remaining element collating storage unit configured to be able to collate whether or not the remaining element excluding some elements constituting the packet identification information matches the corresponding element in the extracted packet identification information;
A part configured to be able to verify whether or not the partial element corresponding to the remaining element defined in the remaining element verification storage unit matches the corresponding element in the extracted packet identification information An element matching storage unit,
The search processing means is
A remaining element search unit that determines whether or not the remaining element in the extracted packet identification information matches any remaining element stored in the remaining element matching storage unit;
When the remaining element search unit determines that there is a remaining element stored in the remaining element matching storage unit that matches the remaining element in the extracted packet identification information, the extracted packet identification A partial element search unit for determining whether or not a partial element in the information matches any partial element specified by the information stored in the partial element matching storage unit ,
The partial element matching storage unit includes information indicating whether values of one or a plurality of the partial elements corresponding to the remaining elements specified in the remaining element matching storage unit are continuous or discontinuous. packet identification device, characterized in that the containing. The partial element matching storage unit also stores the leading and trailing values when the values of the partial elements corresponding to the remaining elements are continuous,
The partial element search unit determines that the remaining element search unit matches the remaining elements in the extracted packet identification information among the remaining elements stored in the remaining element matching storage unit. And when it is determined that the partial element corresponding to the remaining element is one of the continuous values based on the storage contents of the partial element matching storage unit, The packet identification device according to claim 1 , wherein it is determined whether or not there is a value of a partial element in the extracted packet identification information within a fixed range. The partial element matching storage unit stores all values of the partial elements corresponding to the remaining elements when the values of the partial elements corresponding to the remaining elements are discontinuous,
The partial element search unit determines that the remaining element search unit matches the remaining elements in the extracted packet identification information among the remaining elements stored in the remaining element matching storage unit. And when it is determined that the partial element corresponding to the remaining element is any non-continuous value based on the storage content of the partial element matching storage unit, the value stored individually The packet identification device according to claim 1 , wherein it is determined whether or not values of some elements in the extracted packet identification information match. A packet information extracting unit extracts packet identification information from an input packet, and a search processing unit determines whether or not the extracted packet identification information matches the packet identification information stored in the storage unit in advance. In the identification method,
As the storage means,
A remaining element collating storage unit configured to be able to collate whether or not the remaining element excluding some elements constituting the packet identification information matches the corresponding element in the extracted packet identification information;
A part configured to be able to verify whether or not the partial element corresponding to the remaining element defined in the remaining element verification storage unit matches the corresponding element in the extracted packet identification information An element matching storage unit that includes information indicating whether or not the values of one or more of the partial elements corresponding to the remaining elements defined in the remaining element matching storage unit are continuous A partial element verification storage unit
The remaining element search unit in the search processing means determines whether or not the remaining element in the extracted packet identification information matches any remaining element stored in the remaining element matching storage unit,
The partial element search unit in the search processing means matches the remaining element in the extracted packet identification information among the remaining elements stored in the remaining element matching storage unit by the remaining element search unit. Whether or not a partial element in the extracted packet identification information matches any of the partial elements specified by the information stored in the partial element matching storage unit. A packet identification method characterized by discriminating. A packet identification program that extracts packet identification information from an input packet and determines whether or not the extracted packet identification information matches packet identification information stored in advance,
Computer
A remaining element collating storage unit configured to be able to collate whether or not the remaining element excluding some elements constituting the packet identification information matches the corresponding element in the extracted packet identification information; and A part configured to be able to verify whether or not the partial element corresponding to the remaining element defined in the remaining element verification storage unit matches the corresponding element in the extracted packet identification information An element matching storage unit that includes information indicating whether or not the values of one or more of the partial elements corresponding to the remaining elements defined in the remaining element matching storage unit are continuous Storage means comprising a partial element verification storage unit
A remaining element search unit for determining whether or not a remaining element in the extracted packet identification information matches any remaining element stored in the remaining element matching storage unit, and the remaining element search unit includes: When it is determined that there is a remaining element stored in the remaining element matching storage unit that matches the remaining element in the extracted packet identification information, a partial element in the extracted packet identification information is And functioning as a search processing means including a partial element search unit that determines whether or not it matches any of the partial elements specified by the information stored in the partial element matching storage unit. A packet identification program characterized by the above.

Images