Scope In Decision Trees

摘要

A root node of a decision tree data structure may cover all values of a search space used for packet classification. The search space may include a plurality of rules, the plurality of rules having at least one field. The decision tree data structure may include a plurality of nodes, the plurality of nodes including a subset of the plurality of rules. Scope in the decision tree data structure may be based on comparing a portion of the search space covered by a node to a portion of the search space covered by the node's rules. Scope in the decision tree data structure may be used to identify whether or not a compilation operation may be unproductive. By identifying an unproductive compilation operation it may be avoided, thereby improving compiler efficiency as the unproductive compilation operation may be time-consuming.

主权项

1. A method comprising:
compiling a decision tree data structure including a plurality of nodes using a classifier table having a plurality of rules representing a search space for packet classification, the plurality of rules having at least one field, the plurality of nodes each covering a portion of the search space by representing subsets of the plurality of rules; for each node of the decision tree data structure, computing a scope factor for the node based on a rule portion of the search space covered by each rule intersecting the node; and using the scope factor computed for at least one node of the plurality of nodes as an input parameter to a decision for performing a compiler operation at the at least one node.