Packet classification using multi-dimensional splitting

A device, comprising:

• a memory storage comprising instructions;
• and
• one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:
• receive a plurality of packets, each of the packets including header information;
• receive a rule-set having a plurality of rules that indicate actions to perform on the packets;
• construct a geometric representation of the rule-set wherein the geometric representation has a plurality of dimensions and a plurality of rule boundaries;
• split the geometric representation along each of the rule boundaries to form a search structure having a plurality of nodes;
• split multi-dimensions of the geometric representation to form the search structure, wherein the splitting each of the rule boundaries and the splitting the multi-dimensions includes having k-splits and n-dimensions for each node;
• constrain a node in the plurality of nodes to a predetermined memory threshold;
• and
• search the search structure by using the header information to obtain a rule to perform on the packet, wherein the rule is stored in a leaf node in the plurality of nodes.

A non-transitory computer-readable medium storing computer instructions, that when executed by one or more processors, cause the one or more processors to perform the steps of:

• receive a packet having header information from a plurality of packets;
• receive rule-set that indicates a plurality of actions to perform on the packet;
• construct a decision tree structure having a plurality of nodes by splitting a geometric representation into k-splits on n-dimensions of each node in the plurality of nodes based on the rules rule set, wherein the plurality of nodes include a plurality of leaf nodes to store the plurality of rules;
• split the geometric representation along each of the rule boundaries to form the decision tree:
• constrain an access to each node in the plurality of nodes to a memory access time;
• and
• search the decision tree structure using the header information to obtain a rule in the rules rule set stored in the plurality of leaf nodes that indicates an action to take on the packet.