Packet classification
View Patent ↗An apparatus and method includes grouping filters to form a tree according to a bitmask. The bitmask includes entries indicating whether a value is assigned to an element of a filter. The method also includes receiving a packet that includes a particular bitmask, searching the tree to determine filters associated with the particular bitmask and the associated values, and returning a set of filters that are an intersection of the filters indicated by the associated values.
1. A method comprising:
receiving a packet that includes a set of values included in fields of a packet header;
associating a bitmask with the set of values included in the packet header;
for one or more of the bits in the associated bitmask:
selecting a search tree from a plurality of search trees based at least in part on a value of the associated bitmask and a value of the bit;
searching the selected search tree based on one or more of the values included in the packet header; and
returning filters for the packet based on the set of values included in the packet header; and
generating an intersected set of the returned filters.
2. The method of claim 1 further comprising grouping filters to form a tree according to the bitmask.
3. The method of claim 2 further comprising
determining if a bitmask entry is present in the bitmask list and
adding the bitmask entry for the bitmask if the bitmask entry is not present, to the bitmask list held by a node of the value tree.
4. The method of claim 2 further comprising adding a value node to a tree.
5. The method of claim 2 further comprising adding a filter to a filter tree held by a bitmask entry.
6. The method of claim 2 wherein grouping includes generating a balanced tree for the filters.
7. The method of claim 6 wherein the balanced tree is a red-black tree.
8. The method of claim 2 wherein grouping includes generating a balanced tree for the values.
9. The method of claim 8 wherein the balanced tree is a red-black tree.
10. The method of claim 1 wherein each tree includes a value tree and a node in the value tree includes a linked list of bitmask based filter trees.
11. The method of claim 10 wherein searching the tree includes determining filters based on the bitmask entries in the linked list held by the value nodes.
12. The method of claim 11 further comprising:
copying multiple filter sets to a memory; and
forming an intersection set of the multiple filter sets.
13. The method of claim 12 further comprising forming a union set of filters that is the union of the intersection sets to provide the union set of filters being used to process the packet.
14. The method of claim 6 further comprising providing a balanced tree for each filter element.
15. The method of claim 14 wherein the balanced tree is a red-black tree.
16. The method of claim 1 further comprising providing a balanced tree for each combination of bits in the bitmask.
17. The method of claim 16 wherein the balanced tree is a red-black tree.
18. A computer program product, tangibly embodied in a machine-readable storage device, for executing instruction on a processor, the computer program product being operable to cause a machine to:
receive a packet that includes a set of values included in fields of a packet header;
associate a bitmask with the set of values included in the packet header;
for one or more of the bits in the associated bitmask:
select a search tree from a plurality of search trees based at least in part on a value of the associated bitmask and a value of the bit;
search the selected tree based on one or more of the values included in the packet header; and
return filters for the packet based on the set of values included in the packet header; and
generate an intersected set of the returned filters.
19. The computer program product of claim 18 further comprising instructions to group filters to form a tree according to the bitmask.
20. The computer program product of claim 19 further comprising instructions to generate a balanced tree for the filters.
21. The computer program product of claim 19 further comprising instructions to generate a balanced tree for the values.
22. The computer program product of claim 18 further comprising instructions to copy multiple filter sets to a memory; and
form an intersection set of the multiple filter sets.
23. The computer program product of claim 18 further comprising instructions to form a union set of filters that is the union of the intersection sets to provide the union set of filters to process the packet.
24. The computer program product of claim 19 further comprising instructions to provide a balanced tree for each filter element.
25. The computer program product of claim 19 further comprising instructions to provide a balanced tree for each combination of bits in the bitmask.
26. A system comprising:
a networking appliance including a processor configured to:
receive a packet that includes a set of values included in fields of a packet header;
associate a bitmask with the set of values included in the packet header;
for one or more of the bits in the associated bitmask:
select a search tree from a plurality of search trees based at least in part on a value of the associated bitmask and a value of the bit;
search the selected tree, based on one or more of the values included in the packet header; and
return filters for the packet based on the set of values included in the packet header; and
generate an intersected set of the returned filters.
27. The system of claim 26 wherein the processor is farther configured to group filters to form a tree according to the bitmask.
28. The system of claim 26 wherein the processor is farther configured to copy multiple filter sets to a memory; and
form an intersection set of the multiple filter sets.
29. The system of claim 28 wherein the processor is further configured to form a union set of filters that is the union of the intersection sets to provide the union set of filters being used to process the packet.
30. Apparatus comprising:
a processor configured to:
receive a packet that includes a set of values included in fields of a packet header;
associate a bitmask with the set of values included in the packet header;
for one or more of the bits in the associated bitmask:
select a search tree from a plurality of search trees based at least in part on a value of the associated bitmask and a value of the bit;
search the selected search tree, based on one or more of the values included in the packet header; and
return filters for the packet based on the set of values included in the packet header; and
generate an intersected set of the returned filters.
31. The apparatus of claim 30 wherein the processor is further configured to group filters to form a tree according to the bitmask.
32. The apparatus of claim 30 wherein the processor is further configured to:
copy multiple filter sets to a memory; and
form an intersection set of the multiple filter sets.
33. The apparatus of claim 30 wherein the processor is further configured to form a union set of filters that is the union of the intersection sets to provide the union set of filters to process the packet.