JP5682442B2 - Packet classifier, packet classification method, and packet classification program - Google Patents

Description

  The present invention relates to packet classification.

  Packet classification is an important technique for classifying packets into packet strings having a series of attributes called “flows” in routers and switches on the network. Packet classification plays an important role in the realization of network applications with added value, such as providing QoS (Quality of Service) for individual flows and security such as a firewall.

  In packet classification, a “rule” is defined using one or more fields included in the header of a packet. A rule is sometimes called a “filter”. The rules are defined in, for example, a TCP (Transmission Control Protocol) / UDP (User Datagram Protocol) header in addition to a source IP address, a destination IP address, and a protocol number defined in an IP (Internet Protocol) header of the packet. Defined by a plurality of header fields such as a transmission port number and a destination port number. The packet classification in the case where the rule is defined using a plurality of header fields as described above is particularly called multi-field packet classification.

  Usually, a plurality of such rules are defined. When the packet arrives, the field value used for defining the rule is extracted from the packet header. The set of extracted field values is compared with a plurality of rules, and a rule is matched to determine a rule, so that the packet is classified into a flow. Here, a set of field values extracted from the header of the arrived packet is called a “search key”. In general, a priority (Priority) and an action (Action) are defined for each rule. If the search key matches two or more rules among the plurality of rules, a rule with a higher priority is selected. The action defines how to handle an incoming packet when it matches the rule (for example, discard it and send it to the first port).

  In addition, for each field in the rule, Exact Match defined as a specific value, a plurality of upper bits are specified, but a few lower bits are defined as undefined using a wildcard (*). Prefix Match, Range Match defined as a range of two specific values, and Wildcard Match defined by specifying a wild card for each bit unit are used. For example, when an 8-bit field is considered, a specified value such as “00110101” is specified as a value starting from 4 bits of “0011” such as Exact Match, “0011 ***”. The thing is Prefix Match, and the 8-bit field should be within the range of 3 to 64 when considered in decimal as in [3-64]. Range Match, “0 ** 10 * 01” A wildcard match is a wildcard that can be used in bit units.

  With respect to such a multi-field packet classification technique, it is one technical problem how to process this in a high-speed router or switch by increasing the capacity of the rule set and improving the link speed. For example, as a simple method, a linear search (Linear Search) is performed in which all rules included in a rule set are managed in a list in order of priority, and comparison is performed in order from the top of the list (rules with high priority). Conceivable. However, in such a technique, there is a problem that matching comparison processing with all the rules included in the worst rule set is required, and the time required for packet classification processing becomes very long. For this reason, at present, a technique based on the Tertiary Content Addressable Memory (TCAM) is often used to realize high-speed packet classification processing.

  However, TCAM has problems such as high cost, large power consumption and circuit scale. In addition, when Range Match is used, there is a problem that the number of rules increases because the rule needs to be divided into rules using Prefix Match.

  On the other hand, various multi-fields using static random access memory (SRAM) and dynamic random access memory (DRAM) with lower cost and lower power consumption to avoid the problem of high cost and high power consumption of TCAM. Packet classification methods have been proposed.

  For example, Non-Patent Document 1 proposes a method using a “Decision Tree”. In the method using the decision tree, matching is not performed for all rules, but only for a small number of rules that can be matched by the search key. This reduces the time required for the search process. A method using a decision tree will be briefly described with reference to FIGS.

  FIG. 1 shows an example of a rule set consisting of 16 rules from R0 to R15 defined using two fields X and Y each having a length of 4 bits. The fields X and Y correspond to actual packet header fields such as a transmission source IP address and a transmission source port number. The field X is expressed in binary numbers, and “*” indicates a wild card. The field Y is represented by Range Match, and a and b of “[a: b]” represent a lower limit value and an upper limit value (decimal notation), respectively. Further, here, the priority and action given to each rule are omitted.

  FIG. 2 represents the rule set shown in FIG. 1 on a two-dimensional space composed of two axes of fields X and Y. The numbers on the X axis and Y axis in the figure are each expressed in decimal numbers. According to the technique using a decision tree, a multidimensional space as shown in FIG. 2 is divided by paying attention to a plurality of dimensions. The decision tree is constructed by repeating the area division until the number of rules existing in the divided area is equal to or smaller than a threshold value. Here, the rule group managed in the divided area is referred to as a “rule list”.

  FIG. 3 shows an example of a decision tree constructed for the rule set shown in FIG. In the decision tree shown in FIG. 3, the threshold value for the number of rules in the divided area is set to 2. As shown in FIG. 3, first, the entire space is divided into two parts in the X direction and the Y direction, respectively. That is, the entire space (X, Y) = ([0:15], [0:15]) is the region 0 ([0: 7], [0: 7]), region 1 ([0: 7], [8:15]), region 2 ([8:15], [0: 7]), and region 3 ([8:15], [8:15]). The rule list managed in each area is [R7, R8, R9, R11] (area 0), [R0, R6, R9, R10, R11, R12] (area 1), [R1, R2, R3, R4, R5, R13, R14] (region 2) and [R10, R14, R15] (region 3). Since more rules than the threshold value 2 are still managed in each region, further region division is performed until the number of rules is equal to or less than the threshold value for each region. In the example shown in FIG. 3, the entire space is finally divided into 22 regions. Note that the algorithm for constructing a decision tree is described in Non-Patent Document 1 and Non-Patent Document 2, and is omitted here.

  When packet classification is performed, the decision tree is traced while referring to the search key, and matching is performed for all rules that are equal to or less than the threshold number managed by the arrived leaf node. As an example, consider packet classification for packets with search keys X = 0111 and Y = 1001. In the decision tree shown in FIG. 3, the entire space is divided into the above four regions at the root node, and the packet is divided into region 1 ([0: 7], [8:15] among these four regions). ). Subsequently, at the node in the region 1, the space is further divided into two parts in the X direction and the Y direction. That is, region 1 is region 10 ([0: 3], [8:11]), region 11 ([0: 3], [12:15]), region 12 ([4: 7], [8: 11]) and area 13 ([4: 7], [12:15]). It can be seen that the packet belongs to the region 12 among them. Further, the area 12 is divided into four, and it can be seen that the packet belongs to the area 122 ([6: 7], [8: 9]). Then, matching is performed on the two rules R9 and R10 managed in the area 122, and the matched rule is selected. In this example, since the packet matches both the rules R9 and R10, the rule is selected according to the priority assigned to each rule omitted in FIG.

  According to the method using the decision tree as described above, the same rule may be managed in a plurality of divided areas as a result of area division, which is hereinafter referred to as “replication of rules”. . For example, in FIG. 3, rules such as R7 and R9 are duplicated. When rule duplication occurs, the memory capacity for managing the duplicate rule itself or the address value for the duplicate rule increases, and it seems to handle more rules than the actual rule set. Become. That is, rule duplication causes an increase in the amount of data in the decision tree.

  In order to suppress duplication of rules, a method as disclosed in Non-Patent Document 3 has been proposed. In Non-Patent Document 3, a plurality of decision trees are prepared, and different decision trees are constructed by properly using fields (dimensions) used for region division for each decision tree. Each rule is managed in any decision tree in which no rule duplication occurs. Since there is an upper limit on the number of decision trees, if there is no duplication in any decision tree, for example, the rule will be managed in the last decision tree, but multiple decision trees should be used. Can prevent duplication of rules. Note that the method of Non-Patent Document 3 is proposed as a method in which hardware performs packet classification using pipeline processing, as in Non-Patent Document 2.

  In Patent Document 1, there is a packet classifier that manages a combination of a packet type and a rule composed of a plurality of packet field values depending on the packet type using a single classification rule table (rule table). It is disclosed. By using the packet type as an index, rules for various packet types can be managed using the same table.

JP 2006-20317 A

Sumeet Singh, Florin Baboescu, George Varghese, Jia Wang, "Packet Classification Using Multidimensional Cutting", Proceedings of the ACM SIGCOMM 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, 2003 years, pp. 213-224 Weilong Jiang, Victor K. Prasanna, “Large-Scale Wire-Speed Packet Classification on FPGAs”, Processeds of the ACM / SIGDA International Symposium on Field Program. 219-228 Weilong Jiang, Victor K. Prasanna, Norio Yamagaki, “Decision Forest: A Scalable Architecture for Flexible Principal Matching on FPGA”, Proceedings of 2010, International Contest. 394-399

  According to the packet classifier described in the related art, when a rule matching the search key is searched, search processing is executed in all decision trees. However, this leads to an unnecessary increase in the power consumption of the packet classifier. This is because the fields used for area division in each node are different in a plurality of decision trees, and search processing is executed even in a decision tree where there is no possibility that a rule that matches the input search key exists. is there. In the search process, since necessary information is read from the memory, the power consumption of the packet classifier increases unnecessarily.

  One object of the present invention is to provide a technique capable of preventing the occurrence of unnecessary memory access and reducing power consumption in a packet classifier.

  In one aspect of the present invention, a packet classifier that manages rules used for packet classification is provided. Each rule is defined by a combination of one or more fields included in the packet header. The packet classifier includes a command input block and a plurality of rule comparison blocks. The command input block creates, as input commands, a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule. Each of the plurality of rule comparison blocks manages one or more rules and executes processing according to the input command. The plurality of rule comparison blocks are grouped into a plurality of groups by paying attention to the type of combination of one or more fields in the managed rule. Among a plurality of groups, a group that may manage a rule that matches the search key, a new rule, or an existing rule is a selection group. The rule comparison block belonging to the selection group is a selection rule comparison block. The command input block inputs an input command only to the selected rule comparison block by referring to a search key, a new rule, or an existing rule.

  In another aspect of the present invention, a packet classification method is provided by a packet classifier that manages rules used for packet classification. Each rule is defined by a combination of one or more fields included in the packet header. The packet classification method according to the present invention includes (A) a packet classifier providing a plurality of rule comparison blocks. Here, each of the plurality of rule comparison blocks is configured to manage one or more rules and execute processing according to the input command. The input command is a search command for instructing a search for a rule that matches the search key, an insert command for instructing the addition of a new rule, or a delete command for instructing the deletion of an existing rule. The plurality of rule comparison blocks are grouped into a plurality of groups by paying attention to the kind of combination of one or more fields in the managed rule. Among a plurality of groups, a group that may manage a rule that matches the search key, a new rule, or an existing rule is a selection group. The rule comparison block belonging to the selection group is a selection rule comparison block. The packet classification method according to the present invention further includes (B) a step of inputting an input command only to a selection rule comparison block by referring to a search key, a new rule, or an existing rule, and (C) a selection rule comparison block. And executing a process according to the input command.

  In still another aspect of the present invention, there is provided a packet classification program that is executed by a computer and causes the computer to function as a packet classifier that manages rules used for packet classification. Each rule is defined by a combination of one or more fields included in the packet header. The packet classifier includes a command input block and a plurality of rule comparison blocks. The command input block creates, as input commands, a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule. Each of the plurality of rule comparison blocks manages one or more rules and executes processing according to the input command. The plurality of rule comparison blocks are grouped into a plurality of groups by paying attention to the type of combination of one or more fields in the managed rule. Among a plurality of groups, a group that may manage a rule that matches the search key, a new rule, or an existing rule is a selection group. The rule comparison block belonging to the selection group is a selection rule comparison block. The command input block inputs an input command only to the selected rule comparison block by referring to a search key, a new rule, or an existing rule.

  According to the present invention, it is possible to prevent unnecessary memory accesses from occurring in the packet classifier and reduce power consumption.

FIG. 1 is a conceptual diagram illustrating an example of a rule set. FIG. 2 is a conceptual diagram showing a case where the rule set shown in FIG. 1 is arranged in a two-dimensional space consisting of two axes of fields X and Y. FIG. 3 is a conceptual diagram showing an example of a decision tree for the rule set shown in FIG. FIG. 4 is a block diagram showing the configuration of the packet classifier according to the first embodiment of the present invention. FIG. 5 is a conceptual diagram of rules managed by each rule comparison block of the packet classifier according to the first embodiment. FIG. 6 is a block diagram illustrating a configuration when each rule comparison block of the packet classifier according to the first embodiment is realized by a decision tree. FIG. 7 is a conceptual diagram showing a correspondence relationship between a decision tree node processing block and each node of the decision tree in the first embodiment. FIG. 8 is a block diagram showing a configuration of a decision tree node processing block of the decision tree processing block according to the first embodiment. FIG. 9 is a block diagram showing the configuration of the entry count block of the decision tree processing block according to the first embodiment. FIG. 10 is a conceptual diagram showing a correspondence relationship between the rule processing block and the rules included in the rule list of each leaf node of the decision tree in the first embodiment. FIG. 11 is a block diagram illustrating a configuration of a rule processing block of the decision tree processing block according to the first embodiment. FIG. 12 is a block diagram showing a configuration of a command input block according to the first embodiment. FIG. 13 is a conceptual diagram illustrating command output information stored in the command output information storage block of the command input block according to the first embodiment. FIG. 14 is a conceptual diagram illustrating a configuration example of a command in the first embodiment. FIG. 15 is a flowchart illustrating the LOOKUP process according to the first embodiment. FIG. 16 is a flowchart showing the process of step A2. FIG. 17 is a flowchart showing the process of step B1. FIG. 18 is a conceptual diagram illustrating a configuration example of node information according to the first embodiment. FIG. 19 is a diagram for explaining an address calculation method according to the first embodiment. FIG. 20 is a flowchart showing the process of step B3. FIG. 21 is a conceptual diagram illustrating a configuration example of entry information according to the first embodiment. FIG. 22 is a flowchart illustrating the INSERT processing according to the first embodiment. FIG. 23 is a flowchart showing the process of step A4. FIG. 24 is a flowchart showing the process of step B4. FIG. 25 is a flowchart showing the process of step A5. FIG. 26 is a flowchart showing the process of step A7. FIG. 27 is a flowchart illustrating the DELETE process in the first embodiment. FIG. 28 is a flowchart showing the process of step A9. FIG. 29 is a flowchart showing the process of step A10. FIG. 30 is a flowchart showing the process of step B8. FIG. 31 is a block diagram illustrating a configuration of each rule comparison block in the second configuration example of the packet classifier according to the first embodiment. FIG. 32 is a flowchart illustrating the LOOKUP process in the second configuration example of the first embodiment. FIG. 33 is a flowchart showing the process of step A12. FIG. 34 is a flowchart illustrating the INSERT processing in the second configuration example of the first embodiment. FIG. 35 is a flowchart showing the process of step A13. FIG. 36 is a flowchart illustrating a DELETE process in the second configuration example of the first embodiment. FIG. 37 is a flowchart showing the process of step A14 of the INSERT process in the third configuration example of the first embodiment. FIG. 38 is a block diagram showing a configuration of a packet classifier according to the second embodiment of the present invention. FIG. 39 is a block diagram showing a configuration of a command input block according to the second embodiment. FIG. 40 is a conceptual diagram showing command output information stored in the command output information storage block of the command input block according to the second embodiment. FIG. 41 is a block diagram showing a configuration of a packet classifier according to the third embodiment of the present invention. FIG. 42 is a flowchart illustrating the INSERT processing according to the third embodiment. FIG. 43 is a flowchart showing the process of step A15. FIG. 44 is a flowchart showing the process of step A18. FIG. 45 is a block diagram showing a configuration of a packet classifier according to the fourth exemplary embodiment of the present invention.

  Embodiments of the present invention will be described with reference to the accompanying drawings.

1. 1. First embodiment 1-1. Overview FIG. 4 is a block diagram showing a configuration of the packet classifier 1 according to the first exemplary embodiment of the present invention. The packet classifier 1 manages a plurality of rules used for packet classification. Each rule is defined by a combination of one or more fields included in the packet header. Furthermore, the packet classifier 1 according to the present embodiment automatically performs dynamic update of entries (addition of new rules, deletion of existing rules) according to input commands.

  In the present embodiment, the packet classifier 1 is realized by a hardware circuit. More specifically, as shown in FIG. 4, the packet classifier 1 includes one or more rule comparison blocks 2 (2-1 to 2-N: N is an integer of 1 or more), an entry addition target determination block 3 A command input block 4 and a result output block 5 are provided. Further, input data 6 is input to the packet classifier 1, and output data 7 is output from the packet classifier 1.

  The input data 6 depends on the process to be executed by the packet classifier 1. The processing executed by the packet classifier 1 includes (1) processing for searching for a rule matching the search key (hereinafter referred to as “LOOKUP processing”), and (2) processing for adding a new rule (new entry). (Hereinafter referred to as “INSERT processing”), (3) processing for invalidating existing rules (existing entries) (hereinafter referred to as “DELETE processing”), (4) included in packet classifier 1 Configuration processing in which a setting value is written in advance in a memory, a setting register, or the like. Here, the configuration process is performed at the time of initialization, and is to set a value related to the configuration in a setting register or a memory provided in each block included in the packet classifier 1. Only the LOOKUP process, the INSERT process, and the DELETE process will be described below. The input data 6 includes type data indicating a processing type and data used in the processing. In the case of the LOOKUP process, the input data 6 includes type data indicating the LOOKUP process and a search key. In the case of the INSERT process, the input data 6 includes type data indicating the INSERT process and a new rule to be added. In the case of the DELETE process, the input data 6 includes type data indicating the DELETE process and an existing rule to be invalidated.

  The command input block 4 receives the input data 6 and creates an input command corresponding to the input data 6. Similar to the input data 6, the input command includes type data indicating the type of processing and data used in the processing. The search command for instructing execution of the LOOKUP process includes type data indicating the LOOKUP process and a search key. The insertion command for instructing execution of the INSERT process includes type data indicating the INSERT process and a new rule to be added. The delete command for instructing execution of the DELETE process includes type data indicating the DELETE process and an existing rule to be invalidated.

  The command input block 4 inputs the generated input command to the rule comparison block 2. Here, the command input block 4 does not necessarily input the input command to all the rule comparison blocks 2-1 to 2-N, but is necessary among the plurality of rule comparison blocks 2-1 to 2-N. Enter only in (Selection rule comparison block). Specifically, at the time of LOOKUP processing, the command input block 4 inputs an input command only to the rule comparison block 2 that may manage a rule that matches the search key. During INSERT processing, the command input block 4 inputs an input command only to the rule comparison block 2 that may manage a new rule. During the DELETE process, the command input block 4 inputs an input command only to the rule comparison block 2 that may manage the existing rule to be deleted. More details will be described later.

  The rule comparison blocks 2-1 to 2-N manage a plurality of rules used for packet classification in a distributed manner according to a certain policy. Here, it is assumed that a single rule is managed by any one of the rule comparison blocks 2-1 to 2-N so that no duplication occurs. For example, each of the plurality of rule comparison blocks 2-1 to 2-N may constitute a plurality of decision trees used for packet classification. In this case, the plurality of decision trees are configured so that rule duplication does not occur as in the method described in Non-Patent Document 3. That is, each rule is managed in a decision tree where no duplication of the rule occurs. In other words, a single rule is managed only by a single leaf node in any one of a plurality of decision trees.

  Each rule comparison block 2 manages one or more rules. Each rule comparison block 2 executes a LOOKUP process, an INSERT process, or a DELETE process in accordance with the input command input from the command input block 4. The plurality of rule comparison blocks 2-1 to 2-N can execute each process simultaneously and in parallel.

<LOOKUP processing>
The rule comparison block 2 executes a LOOKUP process in response to the search command. Specifically, the rule comparison block 2 determines whether or not the search key matches any rule for the rule group managed by itself. When there is a rule that matches the search key (hereinafter referred to as a match rule), the rule comparison block 2 notifies the result output block 5 of the match rule. When the search key matches a plurality of rules, the rule comparison block 2 notifies the result output block 5 of the highest priority rule among the plurality of match rules. On the other hand, when there is no rule that matches the search key, the rule comparison block 2 notifies the result output block 5 that there is no match rule. The result output block 5 receives the search result from each rule comparison block 2 and selects the match rule with the highest priority. Then, the result output block 5 outputs the output data 7 indicating the selection result as the final result of the LOOKUP process.

<INSERT processing>
The rule comparison block 2 executes INSERT processing in response to the insertion command. Specifically, first, each rule comparison block 2 determines whether the new rule should be managed by itself. For example, if the rule comparison block 2 is configured using a decision tree, the rule does not duplicate even if it is added to its own decision tree, that is, the new rule is a single leaf node in its own decision tree. To determine whether it can only be managed by. When rule duplication occurs, the rule comparison block 2 is not a target for adding a new rule. On the other hand, when it is determined that the new rule may be managed by itself, the rule comparison block 2 is an “entry addition target candidate”. For example, when the rule comparison block 2 is configured using a decision tree, when it is determined that a new rule can be managed only by a single leaf node in its own decision tree, the rule comparison block 2 is “ Entry candidate candidates ”. At this time, the single leaf node becomes an “addition target leaf node”.

  The entry comparison target rule comparison block 2 to which an entry is actually added is selected from the entry addition target candidates. The entry addition target determination block 3 selects the entry addition target. As shown in FIG. 4, the entry addition target determination block 3 is connected to each of the plurality of rule comparison blocks 2-1 to 2-N. Then, the entry addition target determination block 3 recognizes the entry addition target candidate based on the information notified from each rule comparison block 2 and selects the entry addition target from the entry addition target candidates.

  For example, each entry addition target candidate notifies the entry addition target determination block 3 of the number of valid rule entries managed by the rule comparison block 2. At this time, for example, when each entry addition target candidate manages a memory area for managing a rule in the rule comparison block 2, it is already managed in the rule management area to which a new rule is to be added. The number of valid rule entries may be notified. For example, when the rule comparison block 2 is configured using a decision tree, the number of valid rule entries managed by the addition target leaf node is notified. Then, the entry addition target determination block 3 refers to the number of valid entries received from each entry addition target candidate, and selects an entry addition target according to a predetermined policy. For example, the entry addition target determination block 3 selects the entry addition target candidate having the minimum number of valid entries as the entry addition target. In this case, the deviation of the number of rules among a plurality of rule comparison blocks is suppressed, which is preferable.

  The entry addition target determination block 3 notifies each rule comparison block 2 of the selection result of the entry addition target. Specifically, the entry addition target determination block 3 instructs the entry addition target to add a new rule, and instructs the other decision tree processing block 2 not to execute the rule addition process. Then, the rule comparison block 2 as an entry addition target adds a new rule to the rule list managed by itself.

  In this way, the INSERT process is executed. The result output block 5 receives the processing results from the plurality of rule comparison blocks 2-1 to 2-N, and outputs the output data 7 indicating the final result of the INSERT processing.

<DELETE processing>
The rule comparison block 2 executes a DELETE process in response to the delete command. Specifically, each rule comparison block 2 determines whether or not the existing rule to be deleted is managed by itself. When the existing rule is managed by itself, the rule comparison block 2 is “entry deletion target”. When the rule comparison block 2 is configured using a decision tree, the leaf node in which the existing rule that is the deletion target is managed is the “deletion target leaf node”. The rule comparison block 2 that is the entry deletion target invalidates the existing rule.

  In this way, the DELETE process is executed. The result output block 5 receives the processing results from the plurality of rule comparison blocks 2-1 to 2-N, and outputs the output data 7 indicating the final result of the DELETE processing.

<Group selection processing>
As described above, according to the present embodiment, the command input block 4 inputs an input command only to a necessary one (selected rule comparison block) among the plurality of rule comparison blocks 2-1 to 2-N. This process will be described with reference to FIG.

  According to the present embodiment, the plurality of rule comparison blocks 2-1 to 2-N are grouped into a plurality of groups. Here, the grouping standard is the type of combination of packet header fields of interest for managing rules. More specifically, for example, when each rule comparison block 2 is configured by a decision tree, it is the kind of combination of header fields used for area division of the decision tree constituting each rule comparison block 2. In addition, a combination type of packet header fields that do not include a wild card may be used. By performing such management, rules are generally defined by the same combination of packet header fields. However, rules defined by a plurality of different combinations can be managed by the same packet classifier. .

  For example, when the Type field is 0x0800 (meaning IP version 4), the rule includes a source IP address in addition to a header field related to a protocol up to Layer 2 (hereinafter referred to as L2) such as a source MAC address, a destination MAC address, and Type. Assume that upper layer header fields such as destination IP address and protocol number are used. Note that wild cards may be assigned to fields that are not referred to in each rule. Using such a combination of header fields, the rule comparison block 2 that manages each rule is classified into a first group. In the example of FIG. 5, the first group includes rule comparison blocks 2-6 to 2-N.

  When the Type field is 0x8100 (meaning IEEE 802.1Q VLAN tag frame), in addition to the header fields related to the protocol up to L2, such as the source MAC address, destination MAC address, and type, the rule includes VLAN ID and VLAN. It is assumed that a header field up to the VLAN such as Priority is used. Note that wild cards may be assigned to fields that are not referred to in each rule. The rule comparison block 2 for managing each rule using such a combination of header fields is classified into the second group. In the example of FIG. 5, the second group includes rule comparison blocks 2-4 and 2-5.

  When the Type field is other than those described above, it is assumed that a header field related to a protocol up to L2 such as a source MAC address, a destination MAC address, and Type is used for the rule. Note that wild cards may be assigned to fields that are not referred to in each rule. In this case, in this case, the rule comparison block 2 managing each rule using such a combination of header fields is classified into the third group. In the example of FIG. 5, the third group includes rule comparison blocks 2-1 to 2-3.

  In this way, the plurality of rule comparison blocks 2-1 to 2-N are grouped into a plurality of groups according to the types of combinations of header fields of interest for managing the rules. For example, when rules defined in higher-layer header fields such as a header field related to a protocol up to L2, a source IP address, a destination IP address, and a protocol number are managed using a header field related to a protocol up to L2, It is classified into the third group. Similarly, for example, when the rules defined in the header field related to the protocol up to L2 and the header field related to the protocol up to L2 such as VLAN ID and VLAN Priority are managed using the header field related to the protocol up to L2, the third group are categorized. A group to which an input command is to be input among such a plurality of groups is a “selected group”. In the case of the LOOKUP process, the selected group is a group that may manage a rule that matches the search key. In the case of INSERT processing, the selected group is a group that may manage a new rule. In the case of DELETE processing, this is a group that may manage existing rules to be deleted.

  According to the present embodiment, the command input block 4 inputs an input command only to the rule comparison block 2 (hereinafter referred to as “selection rule comparison block 2”) belonging to the selected group, and other rule comparisons. No input command is input to block 2. Therefore, the process according to the input command is executed only in the selection rule comparison block 2. As a result, unnecessary power consumption in the packet classifier 1 is reduced.

  The command input block 4 can determine which of the plurality of groups is a selected group by referring to a search key and a rule (new rule, delete rule). For example, the selected group can be identified based on a header field that can determine the packet configuration, such as a Type field included in the MAC header or a protocol field included in the IP header. In the example shown in FIG. 5, the Type field included in the MAC header is different for each group. Therefore, the command input block 4 can identify the selected group by using the Type field extracted from the search key or the rule as “identification information”.

  For example, in the example shown in FIG. 5, when the Type field of the search key is 0x8100, the selection groups are the second group and the third group, and the command input block 4 includes the selection rule comparison blocks 2-1 to 2 Enter the search command only at -5. When the Type field of the search key is 0x0800, the selection groups are the first group and the third group, and the command input block 4 is only the selection rule comparison blocks 2-1 to 2-3 and 2-6 to 2-N. Enter the search command. When the Type field of the search key is other than that, the selection group is the third group, and the command input block 4 inputs the search command only to the selection rule comparison blocks 2-1 to 2-3.

  As described above, according to the present embodiment, the command input block 4 identifies the selected group by referring to the search key and the rule (new rule, delete rule). Then, the command input block 4 inputs an input command only to the selection rule comparison block 2 belonging to the selection group, and does not input an input command to the other rule comparison blocks 2. Therefore, the process according to the input command is executed only in the selection rule comparison block 2. As a result, unnecessary memory access in the packet classifier 1 can be prevented and power consumption can be reduced.

  The packet classifier 1 according to the present embodiment is deployed, for example, in a network device such as a switch or a router, or in a NIC (Network Interface Card) mounted on a server expansion card or onboard. In this case, the packet classifier 1 is connected to the control block. The control block has a function of analyzing a header of an incoming packet, a function of extracting a search key from the packet header, and a function of causing the packet classifier 1 to execute a LOOKUP process using the search key. Further, the control block has a function for causing the packet classifier 1 to execute an INSERT process for adding a new rule specified from the outside, and a function for causing the packet classifier 1 to execute a DELETE process for deleting an existing rule specified from the outside. Have The packet classifier 1 receives input data 6 corresponding to the processing from the control block, and outputs output data 7 to the control block.

1-2. First Configuration Example Next, a configuration example of the packet classifier 1 according to the present embodiment will be described in more detail. As long as the above rules can be managed, the rule comparison block 2 may execute any rule management mechanism and search processing. Hereinafter, as a typical example, a configuration in the case where each rule comparison block 2 is realized using a decision tree will be described.

  FIG. 6 is a block diagram showing a configuration of each rule comparison block 2 of the packet classifier 1 according to the present embodiment. Hereinafter, the rule comparison block in this case is also referred to as a decision tree processing block. As illustrated in FIG. 6, the decision tree processing block 2 includes a decision tree pipeline block 20, an entry count block 21, and a rule pipeline block 22. Data input from the command input block 4 to the decision tree processing block 2 is input data 23. Data output from the decision tree processing block 2 to the result output block 5 is output data 24. Data exchanged between the decision tree processing block 2 and the entry addition target determination block 3 is input / output data 25.

  The decision tree pipeline block 20 searches for a decision tree by pipeline processing. Specifically, the decision tree pipeline block 20 includes decision tree node processing blocks 200-1 to 200-H having the same number of stages as the depth (number of stages) H of the decision tree. As shown in FIG. 7, the decision tree node processing block 200-i (i = 1, 2,..., H) has a depth j (j = 0, 1,..., H) from the root node of the decision tree. -1) corresponds to the node and performs processing related to the node. By using these decision tree node processing blocks 200-1 to 200-H, the decision tree pipeline block 20 executes a search process node by node from the root node of the decision tree toward the leaf node. Preferably, a process of tracing one node of the decision tree is executed every clock cycle.

  FIG. 8 is a block diagram showing a configuration of decision tree node processing block 200 according to the present embodiment. As shown in FIG. 8, the decision tree node processing block 200 includes a child node determination block 2000 and a node information storage block 2001.

  The node information storage block 2001 is configured by a storage medium such as a memory or a register, and stores node information. The node information indicates, for each of all nodes at the same depth when viewed from the root node, area division information in the node, that is, information on a child node (divided area) managed by the node.

  The decision tree node processing block 200 receives the input data 2002 from the preceding decision tree node processing block 200. However, the decision tree node processing block 200-1 receives the input data 2002 (= input data 23) from the command input block 4. The input data 2002 includes a command corresponding to each process and an address value used for accessing the node information storage block 2001. The input data 2002 from the decision tree node processing block 200 at the preceding stage further includes “effective bit length” information described later.

  The child node determination block 2000 receives the input data 2002 and reads the node information from the node information storage block 2001 with reference to the address value specified by the input data 2002. Then, the child node determination block 2000 calculates an address value in which the node information of the child node of the node is stored based on the node information, the effective bit length, and the command. In addition, the child node determination block 2000 updates the effective bit length. The calculation of the address value and the update of the effective bit length will be described in detail later. The output data 2003 includes the command included in the input data 2002, the calculated new address value, and the updated effective bit length. The child node determination block 2000 outputs the output data 2003 to the decision tree node processing block 200 at the next stage.

  The decision tree node processing block 200-H at the final stage is as follows. In the case of LOOKUP processing or DELETE processing, the address value calculated by the child node determination block 2000 is an address value used for accessing an entry storage block 2201 (described later) of the rule processing block 220 of the rule pipeline block 22. is there. The decision tree node processing block 200-H outputs the output data 2003 to the rule processing block 220-1. In the case of the INSERT processing, the address value calculated by the child node determination block 2000 is an address value used for access to the entry number storage block 211 (described later) of the entry number count block 21. The output data 2004 includes the command included in the input data 2002 and the calculated address value. The child node determination block 2000 outputs the output data 2004 to the entry count block 21.

  The entry count block 21 manages, for each leaf node, the number of valid rule entries managed for all leaf nodes of the decision tree. Note that the processing by the entry count block 21 is executed in a processing cycle corresponding to the depth H of the decision tree.

  FIG. 9 is a block diagram showing a configuration of the entry number counting block 21 according to the present embodiment. As shown in FIG. 9, the entry count block 21 includes a count processing block 210 and an entry count storage block 211.

  The entry number storage block 211 includes a storage medium such as a memory or a register, and stores entry number information. The entry number information indicates the number of valid rule entries managed by each leaf node of the decision tree.

  In the case of the INSERT processing, the count processing block 210 receives the input data 212 (= the above-mentioned output data 2004) from the decision tree node processing block 200-H of the decision tree pipeline block 20. The input data 212 includes an insert command and an address value used for accessing the entry number storage block 211. The count processing block 210 refers to the address value and reads the entry number information (valid entry number) regarding the addition target leaf node from the entry number storage block 211. Then, the count processing block 210 outputs the output data 216 indicating the number of read valid entries to the entry addition target determination block 3 described above.

  The count processing block 210 receives the input data 216 from the entry addition target determination block 3. When the input data 216 specifies “add new rule to decision tree”, the count processing block 210 adds “1” to the number of valid entries related to the addition target leaf node, and the entry number storage block 211. Write to. As a result, the entry number storage block 211 is updated to the latest state. Further, the count processing block 210 outputs the output data 214 to the rule processing block 220-1 of the rule pipeline block 22. The output data 214 includes an insert command and an address value used for accessing the entry storage block 2201 (described later) of the rule processing block 220-1.

  In the case of DELETE processing, the count processing block 210 receives the input data 213 from the rule processing block 220-B of the rule pipeline block 22. The count processing block 210 refers to the address value specified by the input data 213 and reads the entry number information (valid entry number) regarding the deletion target leaf node from the entry number storage block 211. Then, the count processing block 210 subtracts “1” from the number of valid entries and writes it to the entry number storage block 211. As a result, the entry number storage block 211 is updated to the latest state. Further, the count processing block 210 outputs output data 215 indicating completion of the DELETE processing to the result output block 5 as output data 24.

  The rule pipeline block 22 performs rule processing (LOOKUP, INSERT, DELETE) by pipeline control. Specifically, the rule pipeline block 22 includes rule processing blocks 220-1 to 220-B having the same number of stages as the maximum number of rules (rule list size) B that can be managed in each leaf node. As shown in FIG. 10, the rule processing block 220-i (i = 1, 2,..., B) includes a rule j (j = 1, 2,..., Included in the rule list of the leaf node. B) is associated with the rule j, and the rule processing relating to the rule j is executed. By using these rule processing blocks 220-1 to 220-B, the rule pipeline block 22 executes rule processing for each rule included in the rule list of the leaf node. Preferably, rule processing for one rule is executed every clock cycle.

  FIG. 11 is a block diagram showing a configuration of rule processing block 220 according to the present embodiment. As shown in FIG. 11, the rule processing block 220 includes a comparative update processing block 2200 and an entry storage block 2201.

  The entry storage block 2201 includes a storage medium such as a memory or a register, and stores entry information. The entry information includes a validity flag indicating whether the rule is valid or invalid, a rule ID, a rule, and the like.

  In the case of LOOKUP processing or DELETE processing, the rule processing block 220-1 receives the input data 2202 (= the above-described output data 2003) from the decision tree node processing block 200-H of the decision tree pipeline block 20. The input data 2202 includes a command corresponding to each process and an address value used for accessing the entry storage block 2201.

  In the case of the INSERT processing, the rule processing block 220-1 receives the input data 2203 (= the output data 214 described above) from the entry count block 21. The input data 2203 includes an insert command and an address value used for accessing the entry storage block 2201. Thereafter, the input data 2203 is handled in the same manner as the input data 2202 described above.

  The comparison update processing block 2200 receives the input data 2202 and reads the entry information from the entry storage block 2201 with reference to the address value specified by the input data 2202. Then, the comparative update processing block 2200 executes rule processing according to the command based on the read entry information. Details of the rule processing will be described later. The comparison update processing block 2200 outputs the received input data 2202 as output data 2204 to the rule processing block 220 at the next stage.

  Each of the rule processing blocks 220-2 to 220-B receives the input data 2202 (= the output data 2204 described above) from the preceding rule processing block 220. The processing by the comparative update processing block 2200 is the same as described above. In the case of the DELETE processing, the comparison update processing block 2200 of the final-stage rule processing block 220 -B outputs the output data 2205 (= the above-mentioned input data 213) instead of the output data 2204 to the entry count block 21. . The contents of the output data 2205 are the same as the output data 2204.

  FIG. 12 is a block diagram showing a configuration of the command input block 4 of the packet classifier 1 according to the present embodiment. As shown in FIG. 12, the command input block 4 outputs an input command to each of the output destination analysis block 40, the command output information storage block 41, the command output block 42, and the rule comparison blocks 2-1 to 2-N. Output 43-1 to 43-N.

  The command output information storage block 41 holds command output information indicating the correspondence between “identification information” and “selection rule comparison block”. FIG. 13 conceptually shows an example of the command output information. “Identification information” is, for example, the Type field of the MAC header. The output destination data is N-bit data (N = number of rule comparison blocks 2-1 to 2-N), and each bit is associated with the rule comparison blocks 2-1 to 2-N. If the bit value is '0', the rule comparison block 2 is not a selected rule comparison block. On the other hand, if the bit value is ‘1’, the rule comparison block 2 is a selection rule comparison block. That is, the “selection rule comparison block” is represented by bit “1” in the N-bit output destination data. In addition, in a new rule at the time of INSERT processing, a deletion rule at the time of DELETE processing, or the like, a header field such as a Type field may be defined with a wild card in the definition of the rule. In that case, all the rule comparison blocks 2 are selected rule comparison blocks.

  The output destination analysis block 40 receives the above-described input data 6 input to the packet classifier 1 from the outside. The output destination analysis block 40 extracts “identification information” from a search key in the case of LOOKUP, a new rule in the case of INSERT, and a deletion rule in the case of DELETE. This identification information is, for example, the Type field of the MAC header. Then, the output destination analysis block 40 recognizes the selection rule comparison block 2 by referring to the extracted identification information and command output information (FIG. 13). The output destination analysis block 40 outputs a command, data used in the processing, and command output destination information to the command output block 42.

  The command output block 42 uses the command information received with data such as a flag used in internal processing as an in-device command. Then, the command output block 42 outputs the in-device command to the selection rule comparison block 2 according to the command output destination information. At this time, the command output block 42 may output the command information and an enable signal indicating whether the command information is valid to each rule comparison block 2. In this case, the command output block 42 uses each bit of the output destination data read from the command output information storage block 41 as an enable signal for each rule comparison block 2 while outputting the command information to all the rule comparison blocks 2. You can also

  FIG. 14 is a conceptual diagram illustrating a configuration example of the in-device command. The command part includes a processing type, an end flag, and a result flag. For example, if the processing type that is 2-bit data is “00”, it indicates LOOKUP processing, “01” indicates INSERT processing, and “10” indicates DELETE processing. If the end flag is “0”, it indicates that the end is not completed, and if it is “1”, it indicates the end. The result flag is set to “1” when an entry is added or deleted. Note that the end flag and the result flag are referred to only in the INSERT process and the DELETE process, and the usage method thereof will be described later. Further, the search key (LOOKUP process), a new entry to be added (INSERT process), or an existing entry to be deleted (DELETE process) is stored in the latter half of the in-device command. The configuration example of the in-device command is not limited to this. In particular, by using a larger bit width of internal processing data such as an end flag and a result flag, it becomes possible to flexibly grasp the internal processing status.

  Here, the entry (rule) such as the new entry and the deleted entry can take various expression forms in consideration of Prefix Match, Range Match, and Wildcard Match. For example, data strings A and B having the same length as the search key length are prepared, and in the case of Prefix Match or Wildcard Match, target data is assigned to A, and mask bit data is assigned to B. In the case of Range Match, A A method of assigning a lower limit value to B and an upper limit value to B can be considered. In this case, the entry length of the rule is twice the search key length. Considering these, in the second half of the in-device command, it is allowed that the search key at the time of LOOKUP processing and the length of the addition / deletion entry at the time of INSERT and DELETE processing are different. In the case of an additional entry, its priority is also specified.

  Next, the operation of the packet classifier 1 according to the present embodiment will be described in detail.

<LOOKUP processing>
First, the LOOKUP process will be described. FIG. 15 is a flowchart showing the LOOKUP process in the present embodiment.

Step A1:
Input data 6 is input to the packet classifier 1. The input data 6 includes type data indicating the LOOKUP process and a search key extracted from the search target packet. The command input block 4 receives the input data 6. The command input block 4 determines the selection rule comparison block 2 based on the input data 6 as described above, and generates an in-device command (here, a search command). Then, the command input block 4 outputs the generated in-device command to the selection rule comparison block 2 all at once.

Step A2:
When the search command is received from the command input block 4, the rule comparison block 2 executes a rule match comparison process. Specifically, when the rule comparison block 2 is a decision tree processing block 2 realized by a decision tree, the rule match comparison process shown in FIG. 16 is performed. FIG. 16 is a flowchart showing the process of step A2 in the decision tree processing block 2.

Step B1:
The decision tree processing block 2 executes a process for tracing its own decision tree using the designated search key as the rule matching comparison process. FIG. 17 is a flowchart showing the process of step B1.

Step C1:
The process of tracing the decision tree starts from the root node of the decision tree. Therefore, first, the current processing node is set as the root node of the decision tree. Specifically, an insertion command is input to the decision tree node processing block 200-1 at the first stage of the decision tree pipeline block 20.

Step C2:
The child node determination block 2000 reads the node information from the node information storage block 2001 after confirming that the processing type is LOOKUP.

FIG. 18 is a conceptual diagram illustrating a configuration example of node information. The node information is area division information in the node. As shown in FIG. 18, the node information includes C pairs of a field identifier (field ID) and the number of divisions (k), and a base address. Here, C is the maximum number of fields that can be used for region division in one node of the decision tree. The field ID is determined in advance for each field constituting the search key and rule. In addition, the range of each field is divided into ^2k (k is a natural number), and the divided number k represents the index. For example, when the ranges of the fields X and Y are divided into two as in the examples of FIGS. 1 to 3 described above, the division number k of the field X is 1, and the division number k of the field Y is also 1. is there. The maximum number of k is determined in advance. The base address indicates the minimum address value of the storage area in which the node information of the child node of the node is stored. More specifically, the base address is the minimum address value in the node information storage block 2001 of the next decision tree node processing block 200 in which the node information of the child node of the node is stored, and all the children of the node The node information of the node is stored in a storage area continuous from this base address.

Step C3:
Based on the read node information, the bit string of each field of the search key, and the effective bit length, the child node determination block 2000 calculates the address value of the storage area in which the node information of the child node at the next stage is stored. Specifically, the next stage address value is calculated as follows (see also FIG. 19).

  For example, it is assumed that division information (field ID, number of divisions) = (0001, 01), (0100, 11) and base address = 00001000 are set as node information. In the search key, it is assumed that the field value of field ID = 0001 is “0101”, the field value of field ID = 0100 is “0110”, and the effective bit lengths are 3 and 4, respectively. Here, the effective bit length corresponds to the length from the lower bit used for region division for the bit string of each field. That is, the bit string from the lower bits having the length specified by the effective bit length is referred to in the field value. The field ID = 0001 will be described. Since the effective bit length is 3, the lower 3 bits “101” of the field value are referred to. Since the division number k = 1, the upper 1 bit of the valid bits is referred to obtain “1” (see FIG. 19). Similarly, for field ID = 0100, since the effective bit length is 4 and the division number k is 3, “011” is obtained. The base address “00001000” is added to “1011” obtained by connecting these. “00010011” obtained as a result is the address value of the storage area in which the node information of the child node of the next stage is stored.

Step C4:
Subsequently, the child node determination block 2000 updates the effective bit length by subtracting the division number k from the input effective bit length. In the above example, the effective bit length of the field ID = 0001 is updated to 3-1 = 2, and the effective bit length of the field ID = 0100 is updated to 4-3 = 1. Note that the effective bit length is not input to the decision tree node processing block 200-1, but the effective bit length in this case is assumed to be set in advance as the field length of each field. For the subsequent decision tree node processing block 200, the effective bit length is input from the preceding decision tree node processing block 200.

Steps C5 and C6:
Next, it is determined whether the child node is a leaf node. Specifically, since the child node of the node processed by the decision tree node processing block 200-H is a leaf node (see FIG. 7), the decision tree node processing block 200 to be processed may automatically determine.

  The case where the next node is not a leaf node (step C5; No) corresponds to the case of the decision tree node processing block 200-i (i = 1, 2,..., H-1). The decision tree node processing block 200-i outputs the output data 2003 to the next decision tree node processing block 200- (i + 1) (step C6). The output data 2003 includes the command included in the input data 2002, the calculated new address value, and the updated effective bit length. Then, the process returns to step C2, and the next node becomes a processing node.

  The case where the next node is a leaf node (step C5; Yes) corresponds to the case of the decision tree node processing block 200-H. In this case, step B1 ends.

Step B2:
When step B1 ends, the decision tree node processing block 200-H outputs the output data 2003 including the calculated address value and command to the rule processing block 220-1 of the rule pipeline block 22.

Step B3:
Subsequently, the rule pipeline block 22 performs a comparison (matching process) between the search key and each rule in the rule list. FIG. 20 is a flowchart showing the process of step B3.

Step D1:
The matching process starts from the first rule in the rule list. Specifically, the processing is started from the first-stage rule processing block 220-1.

Step D2:
The comparison update processing block 2200 reads the entry information from the entry storage block 2201 using the input address value after confirming that the processing type is LOOKUP. Then, the comparative update processing block 2200 confirms the valid flag.

  FIG. 21 is a conceptual diagram illustrating a configuration example of entry information. The entry information includes a valid flag indicating whether the rule is valid, a rule ID, a rule, and a priority. An action may be added when actions corresponding to a rule are stored simultaneously. Here, it is assumed that the action is managed at a location different from that of the packet classifier 1, and the search is performed by the packet classifier 1, and then the action is acquired by using the rule ID. In the configuration example of the entry information in FIG. 21, the rule ID is included, but this is not included in the entry information. For example, the ID of the decision tree processing block that has performed the process, the ID of the leaf node, the rule list A rule ID may be generated from the order or the like. More specifically, i is the i of the decision tree processing block 2-i (i = 1, 2,..., N) that has been processed, and the ID of the leaf node reached in the decision tree processing block 2-i. j, a rule processing block 220-k (k = 1, 2,..., B) concatenated with binary numbers can be referred to as a rule ID.

Steps D3 and D4:
If the rule is valid (step D3; Yes), the comparison / update processing block 2200 compares the search key with the read rule. This comparison method is disclosed in Non-Patent Document 2, for example.

Steps D5 and D6:
When the search key matches the rule (step D5; Yes), the comparison update processing block 2200 compares the priority of the rule with the priority of the current match rule. Here, the current matching rule means a rule having the highest priority among the rules matched up to the previous rule processing block 220. On the other hand, the rule used for comparison in the current rule processing block 220 is referred to as a comparison rule.

Steps D7 and D8:
When the priority of the comparison rule is higher (step D7; Yes), the comparison update processing block 2200 sets the comparison rule as a new current match rule. Thereafter, the processing proceeds to step D9.

Steps D9, D10, D11:
It is determined whether the current rule is the last rule in the rule list. Specifically, when the rule processing block 220-i (i = 1, 2,..., B-1) is executing a process, it is not the last rule (step D9; No). In this case, the rule processing block 220-i outputs the output data 2204 including the address value and the command to the next-stage rule processing block 220- (i + 1) (step D10). Then, the process returns to step D2, and the matching process for the next rule in the rule list is executed.

  If the read rule is not valid (step D3; No) and the search key does not match the rule (step D5; No), the priority of the comparison rule is lower than the priority of the match rule. In the case (step D7; No), the process proceeds to step D9.

  When the current rule is the last rule in the rule list, that is, when the processing is performed in the rule processing block 220-B (step D9; Yes), the rule processing block 220-B displays the rule ID of the match rule. The priority and the command are output to the result output block 5 (step D11). Then, step B3 ends. If there is no match rule, a signal indicating that there is no match rule is output. For example, by outputting a special value in which the bit values of the rule ID are all 1, It can also indicate that the rule did not exist.

Step A3:
The result output block 5 receives search results from the plurality of decision tree processing blocks 2-1 to 2-N. The result output block 5 compares the priority levels of the match rules and selects the match rule with the highest priority. Then, the result output block 5 outputs, for example, the rule ID of the match rule having the highest priority as the final result of the LOOKUP process as the output data 7 indicating the selection result. At this time, if there is no match rule, the rule ID having the above-described special value can be output to indicate that no match rule exists.

<INSERT processing>
Next, the INSERT process will be described. FIG. 22 is a flowchart showing INSERT processing in the present embodiment.

Step A1:
Input data 6 is input to the packet classifier 1. The input data 6 includes type data indicating INSERT processing and a new rule to be added. The command input block 4 receives the input data 6. The command input block 4 determines the selection rule comparison block 2 based on the input data 6 as described above, and generates an in-device command (here, a search command). Then, the command input block 4 outputs the generated in-device command to the selection rule comparison block 2 all at once.

Step A4:
When a search command is received from the command input block 4, the rule comparison block 2 confirms whether rule duplication occurs in the block. Specifically, when the rule comparison block 2 is a decision tree processing block 2 realized by a decision tree, a rule duplication presence / absence confirmation process shown in FIG. 23 is performed. FIG. 23 is a flowchart showing the process of step A4 in the decision tree processing block 2.

Step B4:
When an insertion command is received from the command input block 4, the decision tree processing block 2 executes a process of tracing its own decision tree using the designated new rule. FIG. 24 is a flowchart showing the process of step B4.

Step C1:
First, as in the case of the LOOKUP process, the current processing node is set as the root node of the decision tree.

Step C7:
The child node determination block 2000 refers to the end flag in the command after confirming that the processing type is INSERT. When the end flag is “1” (step C7; Yes), the process proceeds to step C5. On the other hand, when the end flag is “0” (step C7; No), the process proceeds to step C2.

Step C2:
As in the case of the LOOKUP process, the child node determination block 2000 reads node information from the node information storage block 2001.

Step C8:
The child node determination block 2000 determines whether or not rule duplication occurs based on the read node information, the bit string of each field of the new rule, and the effective bit length. Whether or not rule duplication occurs can be determined by whether or not a wild card is included when calculating an address value.

  For example, it is assumed that area division information (field ID, number of divisions) = (0001, 01), (0100, 11) and base address = 00001000 are set as node information. In the addition target rule, for each field ID = 0001 and field ID = 0100, (field value, mask bit string) is (“0101”, “1111”), (“0110”, “1111”). And the effective bit lengths are 3 and 4, respectively. The mask bit string is valid if each bit is ‘1’, and invalid if ‘0’, that is, it is treated as a wild card. In this case, since both fields do not contain a wild card, it can be seen that rule duplication does not occur, and the address value of the next child node can be calculated in the same manner as in step C3 at the time of LOOKUP. On the other hand, for the same node information and effective bit length, (field value, mask bit string) of each field of field ID = 0001 and field ID = 0100 in the addition target rule is (“0101”, “1111”), Consider the case where the setting is made as (“0110”, “1100”). In this case, considering the mask bit string, the field values are “0101” and “01 **”, respectively. When trying to calculate the address value of the child node based on the node information, since the effective bit lengths are 3 and 4, the upper 1 bit of the lower 3 bits “101” is referred to for the field ID = 0001. And get '1'. On the other hand, for the field with field ID = 0100, the effective bit length is 4 and the number of divisions is 3, so that “01 *” is obtained. As a result, a wild card is included in the bit string indicating the divided area of the child node, which means that rule duplication occurs. When the field value is set as Range Match, it can be determined whether or not the bit strings referred to are the same value for the bit string corresponding to the effective bit length of the lower limit value and the upper limit value. For example, in the above example, it is assumed that the field ID = 0001 is set as the lower limit value 0000 and the upper limit value 0011. Since the effective bit length is 3, the lower 3 bits “000” and “011” of the lower limit value and the upper limit value are referred to. Since the number of divisions is 1, the first bit of each effective bit length is referred to, and since both are '0', it can be determined that rule duplication does not occur even if region division is performed. On the other hand, when the field ID = 0001 is set to the lower limit value 0000 and the upper limit value 0111, since the reference bits are ‘0’ and ‘1’, it can be determined that duplication of the rule occurs.

Steps C9 and C10:
When rule duplication occurs (step C9; Yes), the decision tree processing block 2 is not an entry addition target candidate. In this case, the child node determination block 2000 sets the command end flag to “1”. Thereafter, the processing proceeds to step C5.

Steps C3 and C4:
On the other hand, if no rule duplication occurs (step C9; No), the next-stage address value is calculated (step C3) and the effective bit length is updated (step C4), as in the case of the LOOKUP process. Thereafter, the processing proceeds to step C5.

Steps C5 and C6:
As in the case of the LOOKUP process, steps C5 and C6 are performed. That is, when the next node is not a leaf node (step C5; No), the decision tree node processing block 200-i (i = 1, 2,..., H-1) Output data 2003 is output to the block 200- (i + 1) (step C6). Then, the process returns to step C7, and the next node becomes a processing node. On the other hand, if the next node is a leaf node (step C5; Yes), step B4 ends.

Step B5:
When step B4 ends, the decision tree node processing block 200-H outputs the output data 2004 including the calculated address value and command to the entry count block 21.

Step B6:
The count processing block 210 of the entry count block 21 receives the input data 212 (= the output data 2004 described above) from the decision tree node processing block 200-H. The count processing block 210 refers to the end flag after confirming that the processing type is INSERT. When the end flag is “0”, the decision tree processing block 2 is an entry addition target candidate. In this case, the count processing block 210 reads the entry number information (valid entry number) related to the addition target leaf node from the entry number storage block 211 using the input address value. Then, the count processing block 210 outputs output data 216 indicating the number of read valid entries to the entry addition target determination block 3.

  On the other hand, when the end flag is “1”, the decision tree processing block 2 is not an entry addition target candidate. In this case, the count processing block 210 outputs a processing end signal to the entry addition target determination block 3. Alternatively, the count processing block 210 may set the number of valid entries to the maximum value and notify the entry addition target determination block 3 of the number of valid entries.

Step A5:
The entry addition target determination block 3 recognizes an entry addition target candidate based on the information notified from the decision tree processing block 2 and selects an entry addition target from the entry addition target candidates. FIG. 25 is a flowchart showing the process of step A5.

Steps E1, E2, E3:
The entry addition target determination block 3 receives information indicating the number of valid entries from the entry addition target candidate (step E1). Next, the entry addition target determination block 3 checks whether or not there is one in which the number of valid entries is less than the maximum number B (list size) of the rule list (step E2). When there is no valid entry number less than the list size (step E2; No), the entry addition target determination block 3 determines that there is no entry addition target (step E3).

Steps E4 and E5:
On the other hand, if there is one in which the number of valid entries is smaller than the list size (step E2; Yes), the entry addition target determination block 3 selects the entry addition target candidate having the minimum number of valid entries as the entry addition target. (Step E4). Thereafter, the entry addition target determination block 3 notifies each decision tree processing block 2 of whether or not an entry can be added (step E5). For example, the entry addition target determination block 3 instructs the entry addition target to add a new rule, and instructs the other decision tree processing block 2 not to execute the rule addition process. Although the entry addition target candidate having the minimum number of valid entries is selected as the entry addition target here, the entry addition target may be selected according to other policies.

Step A6:
The entry count block 21 of the decision tree processing block 2 that is the entry addition target adds “1” to the number of valid entries related to the addition target leaf node, and writes it to the entry count storage block 211. As a result, the entry number storage block 211 is updated to the latest state. The other entry count block 21 of the decision tree processing block 2 sets the command end flag to “1”.

Step A7:
Subsequently, the rule pipeline block 22 performs rule addition processing. FIG. 26 is a flowchart showing the process of step A7.

Step D12:
The entry count block 21 of each decision tree processing block 2 outputs the output data 214 including the address value and the insertion command to the rule processing block 220-1 of the rule pipeline block 22.

Step D13:
The rule addition process starts from the first rule in the rule list. Specifically, the processing is started from the first-stage rule processing block 220-1.

Step D14:
The comparative update processing block 2200 refers to the end flag in the command after confirming that the processing type is INSERT. If the end flag is “1” (step D14; Yes), the process proceeds to step D9. On the other hand, when the end flag is “0” (step D14; No), the process proceeds to step D2.

Step D2:
As in the case of the LOOKUP process, the comparison / update processing block 2200 reads entry information from the entry storage block 2201 using the input address value. Then, the comparative update processing block 2200 confirms the valid flag.

Steps D3 and D15:
If the rule is not valid (step D3; No), a new rule can be written in the entry (that is, an empty entry). In this case, the comparison update processing block 2200 rewrites the rule information in the entry information to that of the new rule, sets the valid flag to “1”, and writes it in the entry storage block 2201. Further, the comparison update processing block 2200 sets the end flag in the command to “1”, and sets the result flag to “1” (addition success). Thereafter, the processing proceeds to step D9.

Step D16:
If the rule is valid (step D3; Yes), writing a new rule to the entry is not permitted. In this case, the rule processing block 220-i outputs output data 2204 including an address value and a command to the next-stage rule processing block 220- (i + 1). Then, the process returns to step D14, and the process for the next rule in the rule list is executed.

Step D9:
As in the case of the LOOKUP process, it is determined whether or not the current rule is the last rule in the rule list. If the current rule is not the last rule (step D9; No), the process proceeds to step D16. On the other hand, in the case of the last rule (step D9; Yes), the rule processing block 220-B outputs the current command to the result output block 5 (step D17). Then, step A7 ends.

Step A8:
The result output block 5 receives commands from the plurality of decision tree processing blocks 2-1 to 2-N. The result output block 5 refers to the result flag in the received command and confirms whether a new rule has been added or not added. Then, the result output block 5 outputs output data 7 indicating the result as the final result of the INSERT process.

  Here, as the final result of the INSERT processing, an entry ID indicating the location where the new rule is added may be output. The entry ID is generated from the ID of the decision tree processing block that is the entry addition target, the ID of the leaf node, the rule list order, etc., as in the rule ID generation method when the rule ID is not included in the entry information described above can do. At this time, if there is no free space where a new rule can be added and a new rule could not be added, it can indicate that the rule could not be added by outputting a signal indicating that, for example, By outputting as a special value with all entry IDs set to “1”, a signal indicating that a rule could not be added can be omitted. In INSERT processing, processing was performed using an end flag and a result flag each consisting of 1 bit, but the bit width of the end flag was increased, for example, the processing was terminated due to the occurrence of rule duplication. Alternatively, it is possible to express a factor that terminated the processing, such as the termination of the processing due to the fact that there is no space in the rule list of the leaf node. By referring to such an end flag, when a new rule cannot be added as the final result of the INSERT processing, the factor can also be output as the final result.

<DELETE processing>
Next, the DELETE process will be described. FIG. 27 is a flowchart showing DELETE processing in the present embodiment.

Step A1:
Input data 6 is input to the packet classifier 1. The input data 6 includes type data indicating DELETE processing and an existing rule to be deleted. The command input block 4 receives the input data 6. The command input block 4 determines the selection rule comparison block 2 based on the input data 6 as described above, and generates an in-device command (here, a search command). Then, the command input block 4 outputs the generated in-device command to the selection rule comparison block 2 all at once.

Step A9:
When a delete command is received from the command input block 4, each rule comparison block 2 checks whether or not duplication of the rule occurs in that block. Specifically, when the rule comparison block 2 is the decision tree processing block 2 realized by a decision tree, the rule duplication presence / absence confirmation processing shown in FIG. 28 is performed. FIG. 28 is a flowchart showing the process of step A9 in the decision tree processing block 2.

Step B4:
As in the case of the INSERT process, when a delete command is received from the command input block 4, the decision tree processing block 2 executes a process for tracing its own decision tree using the designated deletion rule.

Step B7:
When step B4 ends, the decision tree node processing block 200-H outputs the output data 2003 including the calculated address value and command to the rule processing block 220-1 of the rule pipeline block 22, and ends step A9. .

Step A10:
The rule pipeline block 22 performs rule deletion processing. FIG. 29 is a flowchart showing the process of step A10.

Step B8:
The rule pipeline block 22 deletes the target entry as a rule deletion process. FIG. 30 is a flowchart showing the process of step B8.

Step D1:
Step B8 starts with the first rule in the rule list. Specifically, the processing is started from the first-stage rule processing block 220-1.

Step D18:
The comparative update processing block 2200 refers to the end flag in the command after confirming that the processing type is DELETE. If the end flag is “1” (step D18; Yes), the process proceeds to step D9. On the other hand, when the end flag is “0” (step D18; No), the process proceeds to step D2.

Steps D2 and D3:
As in the case of the LOOKUP process, the comparison / update processing block 2200 reads entry information from the entry storage block 2201 using the input address value. Then, the comparative update processing block 2200 confirms the valid flag. If the rule is invalid (step D3: No), the entry is not a deletion target. In this case, the process proceeds to step D9. On the other hand, when the rule is valid (step D3; Yes), the process proceeds to step D19.

Step D19:
The comparison update processing block 2200 compares the read rule with the rule designated as the deletion target. That is, the comparison update processing block 2200 determines whether or not the rule designated as the deletion target matches the read rule. Here, it is determined whether or not both match completely. If they do not match (step D5; No), the process proceeds to step D9. On the other hand, if it is a complete match (step D5; Yes), the process proceeds to step D20.

Step D20:
The comparison update processing block 2200 sets the valid flag in the entry information to “0” and writes it in the entry storage block 2201. Thereby, the entry (rule) is invalidated. This process corresponds to deletion of an existing rule. Further, the comparison update processing block 2200 sets the end flag in the command to “1”, and sets the result flag to “1” (successful deletion). Thereafter, the processing proceeds to step D9.

Steps D9 and D16:
As in the case of the LOOKUP process, it is determined whether or not the current rule is the last rule in the rule list. When the current rule is not the last rule (step D9; No), the rule processing block 220-i outputs output data 2204 including an address value and a command to the next rule processing block 220- (i + 1). (Step D16). Then, the process returns to step D18, and the process for the next rule in the rule list is executed. On the other hand, when the current rule is the last rule in the rule list (step D9; Yes), step B8 ends.

Step B9:
When step B8 is completed, the rule processing block 220-B outputs the output data 2205 including the address value and the command to the entry count block 21.

Step B10:
The count processing block 210 of the entry count block 21 receives the input data 213 (= the output data 2005 described above) from the rule processing block 220-B. The count processing block 210 refers to the end flag and the result flag after confirming that the processing type is DELETE. When both the end flag and the result flag are “1”, the count processing block 210 reads the entry number information (valid entry number) related to the deletion target leaf node from the entry number storage block 211 using the input address value. . Then, the count processing block 210 subtracts 1 from the number of valid entries and writes it in the entry number storage block 211. As a result, the entry number storage block 211 is updated to the latest state.

Step A11:
Finally, the count processing block 210 outputs output data 215 including a command to the result output block 5. The result output block 5 refers to the result flag in the command received from each of the decision tree processing blocks 2-1 to 2-N and confirms whether the rule is deleted or not deleted. Then, the result output block 5 outputs the output data 7 indicating the result as the final result of the DELETE process.

  Here, the final result of the DELETE process is to output an entry ID indicating the location where the deletion rule is added, as with the entry ID of the new rule addition location during the INSERT processing. At this time, if the deletion rule does not exist in the management rule for some reason, a signal indicating that the deletion rule does not exist, or a special value with all entry IDs set to '1', It can be shown that the delete rule did not exist.

1-3. Second Configuration Example Next, a second configuration example of the packet classifier 1 according to the present embodiment will be described. In the second configuration example, each rule comparison block 2 manages rules in a list format instead of a decision tree. Other configurations are the same as those of the first configuration example, and redundant description is omitted as appropriate.

  FIG. 31 is a block diagram showing a configuration of each rule comparison block 2 in the second configuration example. Hereinafter, the rule comparison block 2 in this case is also referred to as a linear search block. As shown in FIG. 31, the linear search block 2 includes an entry count block 21 and a rule pipeline block 22. That is, the linear search block 2 has a configuration in which the decision tree pipeline block 20 is omitted from the decision tree processing block 2 shown in FIG. Data input from the command input block 4 to the linear search block 2 is input data 23. Data output from the linear search block 2 to the result output block 5 is output data 24. Data exchanged between the linear search block 2 and the entry addition target determination block 3 is input / output data 25.

  The configuration of the entry count block 21 is the same as that shown in FIG. However, the entry count storage block 211 holds the number of valid rule entries managed by the linear search block 2, not the number of valid rule entries managed by each leaf node of the decision tree. Yes. Here, as will be described later, each rule processing block 220 in the rule pipeline block 22 of the linear search block 2 holds one rule. Therefore, the rule list has a configuration in which B rules are connected by a list (rule processing block 220). Therefore, it is only necessary to hold one value as the number of valid rule entries included in the rule list. In each rule processing block 220, a plurality of rules can be managed to make it appear that a single linear search block 2 manages a plurality of rule lists, but they manage a single rule list. This is no different from the case where there are a plurality of linear search blocks 2 to be performed. Therefore, hereinafter, it is assumed that each linear search block 2 manages only one rule list.

  The configuration of the rule pipeline block 22 and the configuration of the rule processing block 220 are the same as those in the first configuration example. However, as described above, in the entry storage block 2201, only one rule is managed.

  As described above, the entry number storage block 211 of the entry count block 21 and the entry storage block 2201 of the rule processing block 220 differ from the first configuration example in that only one valid entry number and only one rule are stored. It only has to be managed. For this reason, it can be realized by a memory, but when a storage medium is wasted due to restrictions such as the number of words, it is preferably realized by a register.

  In the case of this configuration, as in the first configuration example, for example, the output destination of the in-device command is determined by the value of the Type field of the MAC header.

  Next, the operation of the packet classifier 1 in this configuration will be described. However, in the following, only points different from the operation in the first configuration example will be described, and detailed description of the same operation will be omitted.

<LOOKUP processing>
First, the LOOKUP process will be described. FIG. 32 is a flowchart showing the LOOKUP process in the second configuration example. Referring to FIG. 32, the LOOKUP process in the second configuration example is obtained by replacing step A2 in the operation of the first configuration example with step A12. Since all other operations are the same as those in the first configuration example, detailed description thereof is omitted.

Step A12:
When a search command is received from the command input block 4, the rule comparison block 2 executes a rule match comparison process. FIG. 33 is a flowchart showing the process of step A12 in the linear search block 2.

  Referring to FIG. 33, it can be seen that step A12 executes step B3 in the first configuration example. In this configuration example, the rule comparison block 2 is composed of a single rule list. Therefore, when performing the LOOKUP process, the comparison process between the search key and the rule should be executed in order from the first rule processing block 220-1. good. Further, unlike the operation in the first configuration example, it is not necessary to calculate an address when tracing the decision tree. At the time of LOOKUP processing in this configuration example, the address can be explicitly specified.

<INSERT processing>
Next, the INSERT process will be described. FIG. 34 is a flowchart showing INSERT processing in the second configuration example. Referring to FIG. 34, the INSERT process in the second configuration example is obtained by replacing step A4 in the operation of the first configuration example with step A13. Since all other operations are the same as those in the first configuration example, detailed description thereof is omitted.

Step A13:
When the INSERT command is received from the command input block 4, the rule comparison block 2 checks whether or not duplication of the rule occurs in the block. In the case of this configuration example, the rule comparison block is not configured with a decision tree, and therefore, rule replication does not occur. Therefore, a rule duplication presence / absence confirmation process shown in FIG. FIG. 35 is a flowchart showing the process of step A13 in the linear search block 2.

Step B11:
The count processing block 210 of the entry count block 21 receives a command from the command input block 4. The count processing block 210 reads the number of valid entries of the linear search block 2 from the entry number storage block 211. Then, the count processing block 210 outputs output data 216 indicating the number of read valid entries to the entry addition target determination block 3.

  Since the operation after this step is the same as that of the first configuration example, detailed description thereof is omitted.

<DELETE processing>
Next, the DELETE process will be described. FIG. 36 is a flowchart showing DELETE processing in the second configuration example. Referring to FIG. 36, the DELETE process in the second configuration example is obtained by removing step A9 in the operation of the first configuration example. Since all other operations are the same as those in the first configuration example, detailed description thereof is omitted.

1-4. Third Configuration Example Next, a third configuration example of the packet classifier 1 according to the present embodiment will be described. In the third configuration example, the rule comparison block 2 (decision tree processing block 2) in the first configuration example and the rule comparison block 2 (linear search block 2) in the second configuration example are mixed. In this case, M in the rule comparison blocks 2-1 to 2-N are the rule comparison block 2 (decision tree processing block 2) in the first configuration example, and the remaining NM are the rules in the second configuration example. This is a comparison block 2 (linear search block 2).

  However, the packet classifier 1 according to the present embodiment assumes hardware implementation by pipeline processing. Therefore, it is more efficient to combine the number of pipeline stages of the rule comparison block 2 in the first configuration with the number of pipeline stages of the rule comparison block 2 in the second configuration. The rule comparison block 2 in the first configuration includes H decision tree node processing blocks 200, one entry count block 21, and B rule processing blocks 220. On the other hand, the rule comparison block 2 in the second configuration includes one entry count block 21 and B rule processing blocks 220. For example, in the case of LOOKUP processing, the number of pipeline stages in the rule comparison block 2 in the first configuration is H + B, whereas the number of pipeline stages in the rule comparison block 2 in the second configuration is B. In order to prevent this inconsistency, in the third configuration, when using the rule comparison block 2 in the second configuration, it is desirable to include H + B rule processing blocks 220. As a result, when the LOOKUP process is considered as a reference, the number of pipeline stages matches, and more efficient processing is possible.

  Since the configuration other than the above is the same as the first and second configuration examples, detailed description thereof is omitted.

  Next, the operation of the packet classifier 1 in this configuration will be described. However, the LOOKUP process and the DELETE process will not be described in detail because it is only necessary to execute the operation in the first configuration or the operation in the second configuration in each rule processing block 2. Hereinafter, an operation in the INSERT process will be described so that more efficient rule management can be performed.

<INSERT processing>
The INSERT processing in the third configuration example is substantially the same as the operations in the first and second configuration examples. Since the blocks other than the rule comparison block 2 and the entry addition target determination block 3 are not changed at all, a detailed description thereof will be omitted.

  When the configuration is the rule comparison block 2 in the first configuration example, the rule comparison block 2 executes the operation in the first configuration example. When the configuration is the rule comparison block 2 in the second configuration example, the rule comparison block 2 executes the operation in the second configuration example.

  In the INSERT processing in the third configuration example, step A5 (processing for determining the rule comparison block 2 to be added to the entry) in the first and second configuration examples described above is replaced with step A14 described next. .

Step A14:
The entry addition target determination block 3 recognizes the entry addition target candidate based on the information notified from the rule comparison block 2, and selects the entry addition target from the entry addition target candidates. FIG. 37 is a flowchart showing the process of step A14.

Step E1, E6:
The entry addition target determination block 3 receives information indicating the number of valid entries from the entry addition target candidate (step E1). Next, the entry addition target determination block 3 checks whether there is any rule comparison block 2 in the first configuration example in which the number of valid entries is less than the maximum number B (list size) of the rule list. (Step E6). If there is no valid entry number less than the list size (step E6; No), the process proceeds to step E8. On the other hand, if there is one in which the number of valid entries is smaller than the list size (step E6; Yes), the process proceeds to step E7.

Step E7:
The entry addition target determination block 3 selects an entry addition target candidate having the smallest number of valid entries as the entry addition target from the rule comparison block 2 of the first configuration example. Thereafter, the processing proceeds to step E5.

Step E8:
The entry addition target determination block 3 checks whether any of the rule comparison blocks 2 using the second configuration example has a number of valid entries below the maximum number H + B (list size) of the rule list. . If there is no valid entry number less than the list size (step E8; No), the process proceeds to step E3. On the other hand, if there is one in which the number of valid entries is smaller than the list size (step E8; Yes), the process proceeds to step E9.

Step E3:
The entry addition target determination block 3 determines that there is no rule comparison block 2 to which an entry can be added. Thereafter, the processing proceeds to step E5.

Step E9:
The entry addition target determination block 3 selects an entry addition target candidate having the minimum number of valid entries as the entry addition target from the rule comparison block 2 of the second configuration example. Thereafter, the processing proceeds to step E5.

Step E5:
The entry addition target determination block 3 notifies each rule comparison block 2 of whether or not an entry can be added. For example, the entry addition target determination block 3 instructs the entry addition target to add a new rule, and instructs the other rule comparison block 2 not to execute the rule addition process. Although the entry addition target candidate having the minimum number of valid entries is selected as the entry addition target here, the entry addition target may be selected according to other policies.

  Since the operation after this step is the same as that of the first and second configuration examples, detailed description thereof is omitted.

  As can be seen from the above operation, in the case of the INSERT processing, the rule comparison block 2 of the second configuration example is in a state where the pipeline is stopped until Step A14 is executed, and Step A14 is executed. The pipeline will resume later. Since the rule comparison block 2 of the first configuration example has already executed the H stage as the number of pipeline stages before executing step A14, the pipeline processing in each rule comparison block 2 is performed only during the INSERT process. The timing will be different. However, when a rule is added to the rule comparison block 2 of the first configuration example, no rule is added to the rule comparison block 2 of the second configuration example. Operations after step A14 may be ignored. On the other hand, when adding a rule to the rule comparison block 2 of the second configuration example, the operations after step A14 in the rule comparison block 2 of the first configuration example may be ignored. Which operation can be ignored can be determined when the processing result from each rule comparison block 2 is input to the result output block 5.

  Further, in the INSERT processing in this configuration example, priority is given to adding a rule to the rule comparison block 2 of the first configuration example. This is because the rule comparison block of the second configuration example is a simple rule list, and therefore, it is possible to always add a rule when the number of valid entries is less than the rule list. On the other hand, since the rule comparison block 2 of the first configuration example uses a decision tree, there is a possibility that duplication of rules will occur. Therefore, efficient rule management is realized by giving priority to adding rules to the rule comparison block 2 of the first configuration example as much as possible.

2. Second Embodiment FIG. 38 is a block diagram showing a configuration of a packet classifier 8 according to a second embodiment of the present invention. Referring to FIG. 38, the packet classifier 8 in the second embodiment is configured such that the command input block 4 in the packet classifier 1 in the first embodiment is the command input block 9 and the input data 6 is the input data 10. It is a replacement. The other configuration is the same as that of the packet classifier 1 in the first embodiment, and thus detailed description thereof is omitted.

  FIG. 39 is a block diagram showing the configuration of the command input block 9. Referring to FIG. 39, in the command input block 9, the output destination analysis block 40 in the command input block 4 in the first embodiment is set as the output destination analysis block 44, and the command output information storage block 41 is set in the command output information storage block 45. It has been replaced with. Input data 10 to the packet classifier 8 is input to the output destination analysis block 44 from the outside. In the case of this configuration, in each rule comparison block 2, the output destination of the in-device command is determined according to the type of the header field including the wild card.

  FIG. 40 is a conceptual diagram showing command output information stored in the command output information storage block 45. According to the present embodiment, “identification information” is field analysis data. More specifically, the field analysis data has a bit width equal to the number of header fields constituting the rule, and each bit is associated with each field. When a wild card is included in the field, the bit associated with the field is '0'. On the other hand, when the field does not include a wild card, the bit associated with the field is “1”. That is, in the present embodiment, “identification information” is information indicating whether or not each of the plurality of fields includes a wild card. The output destination data is the same as that in the first embodiment.

  The output destination analysis block 44 receives the input data 10 input to the packet classifier 1 from the outside. The output destination analysis block 44 extracts the “identification information” from a search key in the case of LOOKUP, a new rule in the case of INSERT, and a deletion rule in the case of DELETE. Then, the output destination analysis block 44 recognizes the selection rule comparison block 2 by referring to the extracted identification information and command output information. Others are the same as those in the first embodiment.

  Here, it is possible to determine whether each field includes a wild card by expressing the new rule and the deletion rule in the same expression format as in the first embodiment. On the other hand, in the case of a search key at the time of LOOKUP, there may be a case where the field defined by the rule does not exist depending on the arrival packet. To cope with this, as the input data 10, a 1-bit signal is used to indicate that each field of the search key is not defined, that is, that the field value does not exist in the arrival packet. That is, it is the same as the field analysis data in the command output information, and is generated by an external control block or the like.

  Alternatively, the search key may be defined using mask bits as in the rule expression format. In this case, when receiving the search key as the input data 10, the output destination analysis block 44 generates the same as the field analysis data based on the mask bits.

  Since other configurations are the same as those of the command input block 4 in the first embodiment, detailed description thereof is omitted.

  Note that three types of configuration examples of the rule comparison block 2 of the packet classifier 1 in the first embodiment can be applied to the second embodiment.

  According to the present embodiment, the same effect as in the first embodiment can be obtained.

3. Third Embodiment FIG. 41 is a block diagram showing a configuration of a packet classifier 11 according to a third embodiment of the present invention. Referring to FIG. 41, the packet classifier 11 in the third embodiment includes the entry addition target determination block 3 in the packet classifier 1 in the first embodiment, the entry addition target block 12, and the result output block 5 in the result. The output block 13 is replaced, and an output signal is further added from the entry addition target block 12 to the result output block 13. The other configuration is the same as that of the packet classifier 1 in the first embodiment, and thus detailed description thereof is omitted.

  Note that three types of configuration examples of the rule comparison block 2 of the packet classifier 1 in the first embodiment can be applied to the third embodiment.

  Next, the operation of the packet classifier 11 according to this embodiment will be described.

  The operation of the packet classifier 11 in the present embodiment is different from that of the first embodiment only in the operation at the time of INSERT. For this reason, only the difference from the first embodiment in the operation at the time of INSERT will be described below, and detailed description of the other will be omitted. Note that the operation at the time of LOOKUP and the operation at the time of DELETE are the same as the operations in the first embodiment, and thus detailed description thereof is also omitted here.

  FIG. 42 is a flowchart showing processing at the time of INSERT in the present embodiment. Referring to FIG. 42, the processing at the time of INSERT in the present embodiment is the same as the processing at the time of INSERT (FIG. 22) in the first embodiment (step A5), step A8 is replaced by step A17, and step A15 is performed. The difference is that step A16 is added between step A6 and step A6. Since all other operations are the same as the processing at the time of INSERT in the first embodiment, the operations of Step A15, Step A16, and Step A17 will be described below.

Step A15:
The entry addition target determination block 12 recognizes an entry addition target candidate based on the information notified from the rule processing block 2 and selects an entry addition target from the entry addition target candidates. FIG. 43 is a flowchart showing the process of step A15.

Steps E1, E2:
The entry addition target determination block 12 receives information indicating the number of valid entries from the entry addition target candidate (step E1). Next, the entry addition target determination block 12 confirms whether there is any entry addition target candidate whose number of valid entries is less than the maximum number B (list size) of the rule list (step E2). If there is no valid entry number less than the list size (step E2; No), the process proceeds to step E3. On the other hand, if there is one in which the number of valid entries is less than the list size (step E2; Yes), the process proceeds to step E4.

Steps E3 and E10:
The entry addition target determination block 12 determines that there is no rule comparison block 2 to which an entry can be added (step E3). In this case, the entry addition target determination block 12 notifies the result output block 13 of a signal that means that the rule comparison block 2 that is the target of entry addition does not exist (step E10). And the process of step A15 is complete | finished.

Steps E4 and E11:
The entry addition target determination block 12 determines the entry addition target rule comparison block having the minimum number of valid entries from among the number of valid entries less than the list size (step E4). Thereafter, the entry addition target determination block 12 outputs entry addition permission only to the entry addition target rule comparison block (step E11). At this time, no signal is output to the rule comparison block 2 other than the entry addition target. And the process of step A15 is complete | finished.

Step A16:
In step A15, the subsequent processing differs depending on whether or not the rule comparison block 2 to which an entry is to be added exists. If there is a rule comparison block 2 to which an entry is to be added (step A16; Yes), the rule comparison block 2 to which an entry is to be added that has received entry addition permission is similar to the operation at the time of INSERT in the first embodiment. Steps A6 and A7 are executed. Thereafter, the processing proceeds to step A17. On the other hand, if there is no entry comparison target rule comparison block 2 (step A16; No), the process proceeds directly to step A17.

Step A17:
When the result output block 13 receives a command from the rule comparison block 2 to which an entry is added, the result output block 13 refers to the result flag in the received command, and whether a new rule has been added or has not been added. Confirm. Then, the result output block 13 outputs the output data 7 indicating the result as the final result of the INSERT process.

  On the other hand, the result output block 13 may receive a signal from the entry addition target determination block 12 indicating that there is no entry comparison target rule comparison block 2 (step E10). In this case, the result output block 13 outputs the output data 7 indicating that the addition of the new rule has failed as the final result of the INSERT process.

  Similar to the operation at the time of the INSERT processing in the first embodiment, the final result when a new rule can be added is to output an entry ID indicating the location where the rule is added. The method of outputting the entry ID and other information as the final result is the same as the operation at the time of the INSERT processing in the first embodiment, and thus the description is omitted.

  In the above, the entry addition target candidate having the minimum number of valid entries is selected as the entry addition target. However, the entry addition target may be selected according to other policies.

  In the above, the change with respect to the INSERT processing of the 1st structural example in 1st Embodiment was demonstrated. However, this embodiment can also be applied to the INSERT processing of the second configuration example in the first embodiment. Specifically, in the INSERT processing of the second configuration example shown in FIG. 34, step A5 is replaced with step A15, step A8 is replaced with step A17, and step A16 is added between step A15 and step A6.

  Similarly, the present embodiment can be applied to the INSERT processing of the third configuration example in the first embodiment. In this case, step A14 is replaced with step A18, step A8 is replaced with step A17, and step A16 is added between step A18 and step A6. FIG. 44 is a flowchart showing the process of step A18. Similarly to the above, when there is no entry comparison target rule comparison block 2, step E10 is executed after step E3. On the other hand, when the rule comparison block 2 of the first or second configuration example is selected as the entry comparison target rule comparison block 2, step E11 is executed.

  A combination of the present embodiment and the second embodiment is also possible.

  According to the present embodiment, the same effect as the above-described embodiment can be obtained. Further, the following effects can be obtained.

  In the first and second embodiments, the entry addition target determination block 12 also sends a reply indicating that the entry cannot be added even for a block that is not the rule comparison block 2 to be added. In this case, memory access is not performed, but only commands are sequentially delivered to the pipeline. That is, since the pipeline register is activated, this power is consumed. However, in this embodiment, no command is returned to any block other than the rule comparison block 2 to be added. Accordingly, the pipeline registers of the rule comparison block 2 other than the entry addition target are not activated. Therefore, power consumption can be reduced by that amount.

4). Fourth Embodiment Next, the best mode for carrying out the fourth invention of the present invention will be described in detail with reference to the drawings.

  FIG. 45 is a block diagram showing a configuration of a packet classifier according to the fourth exemplary embodiment of the present invention. In the fourth embodiment, packet classification processing is realized by a computer executing a software program. Specifically, the packet classifier according to the present embodiment includes a program processing device 14 and a packet classification program 15. The program processing device 14 is realized by a CPU of a host such as a server or a PC. The packet classification program 15 is a computer program executed by the program processing device 14 and controls the operation of the program processing device 14. The program processing device 14 can have the functions of the packet classifier 1, the packet classifier 8, or the packet classifier 11 described in the foregoing embodiment by executing the packet classification program 15. .

  Note that the packet classification program 15 may be recorded on a computer-readable recording medium.

  As the program processing device 14, a multi-core processor having a plurality of CPU cores (and a many-core processor having more CPU cores) may be used. In this case, each CPU core includes a command input block 4, rule comparison blocks 2-1 to 2 -N, an entry addition target determination block 3, a result output block 5, and further each decision tree constituting the rule comparison block 2. By executing processing such as the node processing block 200, the entry number counting block 21, and the rule processing block 220, higher-speed processing is possible.

  According to the present embodiment, the same effect as the above-described embodiment can be obtained.

  The embodiments of the present invention have been described above with reference to the accompanying drawings. However, the present invention is not limited to the above-described embodiments, and can be appropriately changed by those skilled in the art without departing from the scope of the invention.

  A part or all of the above-described embodiment can be described as in the following supplementary notes, but is not limited thereto.

(Appendix 1)
A packet classifier for managing rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classifier
A command input block that creates a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule as an input command;
A plurality of rule comparison blocks each configured to manage one or more rules and execute processing according to the input command;
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
The command input block inputs the input command only to the selection rule comparison block by referring to the search key, the new rule, or the existing rule.

(Appendix 2)
The packet classifier according to appendix 1,
The selected group is identifiable based on identification information extracted from the search key and rule,
The command input block holds command output information indicating a correspondence relationship between the identification information and the selection rule comparison block,
The command input block identifies the selection rule comparison block by extracting the identification information from the search key, the new rule, or the existing rule, and referring to the extracted identification information and the command output information. Yes Packet classifier.

(Appendix 3)
The packet classifier according to attachment 2, wherein
The identification information is a value of a predetermined field included in the search key and rule.

(Appendix 4)
The packet classifier according to attachment 2, wherein
The search key and rule include a plurality of fields,
The identification information is information indicating whether or not each of the plurality of fields includes a wild card.

(Appendix 5)
The packet classifier according to any one of appendices 1 to 4,
An entry addition target determination block connected to the plurality of rule comparison blocks;
A single rule is managed by any one of the plurality of rule comparison blocks so that duplication does not occur,
If the input command is the insert command, each of the selection rule comparison blocks determines whether the new rule can be managed by itself;
When the new rule can be managed by itself, the selected rule comparison block is an entry addition target candidate,
The entry addition target determination block selects an entry addition target to which the new rule is to be added from the entry addition target candidates,
The selected entry addition target is a packet classifier that adds the new rule to a rule list managed by itself.

(Appendix 6)
The packet classifier according to appendix 5, wherein
The plurality of rule comparison blocks constitute each of a plurality of decision trees used for packet classification,
A single rule is managed by a single leaf node in any one of the plurality of decision trees,
If the input command is the insert command, each of the selection rule comparison blocks determines whether the new rule can be managed by a single leaf node in its decision tree;
When the new rule can be managed by a single leaf node, the selection rule comparison block is the entry addition target candidate, the single leaf node is an addition target leaf node,
The entry addition target is a packet classifier that adds the new rule to a rule list managed by the addition target leaf node in its own decision tree.

(Appendix 7)
The packet classifier according to appendix 6, wherein
The entry addition target candidate notifies the entry addition target determination block of the number of valid rule entries managed by the addition target leaf node,
The entry addition target determination block is a packet classifier that selects the entry addition target based on the number of entries.

(Appendix 8)
The packet classifier according to appendix 5, wherein
Each of the plurality of rule comparison blocks is a packet classifier that manages rules in a list format.

(Appendix 9)
A packet classification method by a packet classifier that manages rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classification method includes:
(A) the packet classifier providing a plurality of rule comparison blocks;
here,
Each of the plurality of rule comparison blocks is configured to manage one or more rules and execute a process according to an input command,
The input command is a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule,
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
(B) outputting the input command only to the selected rule comparison block by referring to the search key, the new rule, or the existing rule;
(C) In the selection rule comparison block, a step of executing processing according to the input command.

(Appendix 10)
A packet classification program that is executed by a computer and causes the computer to function as a packet classifier that manages rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classifier
A command input block that creates a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule as an input command;
A plurality of rule comparison blocks each configured to manage one or more rules and execute processing according to the input command;
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
A packet classification program in which the command input block inputs the input command only to the selection rule comparison block by referring to the search key, the new rule, or the existing rule.

DESCRIPTION OF SYMBOLS 1 Packet classifier 2 Rule comparison block 3 Entry addition object decision block 4 Command input block 5 Result output block 8 Packet classifier 9 Command input block 11 Packet classifier 12 Entry addition object decision block 13 Result output block 14 Program processor 15 Packet Classification program 20 Decision tree pipeline block 21 Entry count block 22 Rule pipeline block 40 Output destination analysis block 41 Command output information storage block 42 Command output block 44 Output destination analysis block 45 Command output information storage block 200 Decision tree node processing block 210 Count processing block 211 Entry number storage block 220 Rule processing block 2000 Child node determination block 2001 node Information storage block 2200 Comparison update processing block 2201 Entry storage block

Claims (10)

A packet classifier for managing rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classifier
A command input block that creates a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule as an input command;
A plurality of rule comparison blocks each configured to manage one or more rules and execute processing according to the input command;
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
The command input block inputs the input command only to the selection rule comparison block by referring to the search key, the new rule, or the existing rule. The packet classifier according to claim 1, wherein
The selected group is identifiable based on identification information extracted from the search key and rule,
The command input block holds command output information indicating a correspondence relationship between the identification information and the selection rule comparison block,
The command input block identifies the selection rule comparison block by extracting the identification information from the search key, the new rule, or the existing rule, and referring to the extracted identification information and the command output information. Yes Packet classifier. The packet classifier according to claim 2, wherein
The identification information is a value of a predetermined field included in the search key and rule. The packet classifier according to claim 2, wherein
The search key and rule include a plurality of fields,
The identification information is information indicating whether or not each of the plurality of fields includes a wild card. The packet classifier according to any one of claims 1 to 4,
An entry addition target determination block connected to the plurality of rule comparison blocks;
A single rule is managed by any one of the plurality of rule comparison blocks so that duplication does not occur,
If the input command is the insert command, each of the selection rule comparison blocks determines whether the new rule can be managed by itself;
When the new rule can be managed by itself, the selected rule comparison block is an entry addition target candidate,
The entry addition target determination block selects an entry addition target to which the new rule is to be added from the entry addition target candidates,
The selected entry addition target is a packet classifier that adds the new rule to a rule list managed by itself. The packet classifier according to claim 5, wherein
The plurality of rule comparison blocks constitute each of a plurality of decision trees used for packet classification,
A single rule is managed by a single leaf node in any one of the plurality of decision trees,
If the input command is the insert command, each of the selection rule comparison blocks determines whether the new rule can be managed by a single leaf node in its decision tree;
When the new rule can be managed by a single leaf node, the selection rule comparison block is the entry addition target candidate, the single leaf node is an addition target leaf node,
The entry addition target is a packet classifier that adds the new rule to a rule list managed by the addition target leaf node in its own decision tree. The packet classifier according to claim 6, comprising:
The entry addition target candidate notifies the entry addition target determination block of the number of valid rule entries managed by the addition target leaf node,
The entry addition target determination block is a packet classifier that selects the entry addition target based on the number of entries. The packet classifier according to claim 5, wherein
Each of the plurality of rule comparison blocks is a packet classifier that manages rules in a list format. A packet classification method by a packet classifier that manages rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classification method includes:
(A) the packet classifier providing a plurality of rule comparison blocks;
here,
Each of the plurality of rule comparison blocks is configured to manage one or more rules and execute a process according to an input command,
The input command is a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule,
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
(B) outputting the input command only to the selected rule comparison block by referring to the search key, the new rule, or the existing rule;
(C) In the selection rule comparison block, a step of executing processing according to the input command. A packet classification program that is executed by a computer and causes the computer to function as a packet classifier that manages rules used for packet classification,
Each rule is defined by a combination of one or more fields included in the packet header,
The packet classifier
A command input block that creates a search command that instructs to search for a rule that matches the search key, an insert command that instructs to add a new rule, or a delete command that instructs to delete an existing rule as an input command;
A plurality of rule comparison blocks each configured to manage one or more rules and execute processing according to the input command;
The plurality of rule comparison blocks are grouped into a plurality of groups, focusing on a combination type of the one or more fields in a managed rule.
Among the plurality of groups, a rule that matches the search key, the new rule, or a group that may manage the existing rule is a selection group,
The rule comparison block belonging to the selection group is a selection rule comparison block,
A packet classification program in which the command input block inputs the input command only to the selection rule comparison block by referring to the search key, the new rule, or the existing rule.

Images