Packet filtering using binary search trees

A packet filter system comprising:

• an interface to receive data packets from a data packet communication stream;
• a first memory to store binary search trees comprising node values to compare to packet data from the receive data packets for packet filtering;
• and
• a second memory to store the packet data from the received data packets, wherein the second memory is partitioned into a first half of memory addresses and a second half of memory addresses;
• and
• a processing circuit to alternate storing the packet data for the received data packets in the first half and the second half, and
• the processing circuit is to process the packet data for a first data packet of the received data packets stored in the first half while the packet data for a second packet of the received data packets is stored in the second half, wherein to process the packet data for the first data packet comprises comparing the packet data for the first data packet to the node values of the binary search trees.

A computer-implemented method for creating binary search trees for packet filtering comprising:

• receiving packet filtering conditions;
• storing the packet filtering conditions in a flow table;
• sorting the flow table, wherein node values are ordered in the flow table to facilitate searching the flow table from a root node value to a leaf node value;
• and
• creating the binary search trees from the sorted flow table.

A non-transitory computer-readable medium comprising instructions, which when executed by a processor, performs the following:

• receiving, by a processor, packet filtering conditions;
• storing the packet filtering conditions in a flow table;
• sorting the flow table, wherein node values are ordered in the flow table to facilitate searching the flow table from a root node value to a leaf node value;
• and
• creating the binary search trees from the sorted flow table.