# US 2021/0243282 A1 · Packet filtering using binary search trees > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0243282 A1 - Document ID: US20210243282A1 - Status: Published application - Kind: A1 - Application number: 17/236,830 - Filed: 2021-04-21 - Published: 2021-08-05 - Earliest claimed: 2016-08-31 - Assignees: Viavi Solutions Inc. - Applicants: Viavi Solutions Inc. - Inventors: Sherwood JOHNSON - Web page: https://patentgrep.com/patent/US20210243282A1 ## CPC - H04L 12/44: Star or tree networks - H04L 45/745: Address table lookup; Address filtering - H04L 49/3018: {Input queuing} - H04L 49/9036: {Common buffer combined with individual queues} - H04L 49/9047: including multiple buffers, e.g. buffer pools - H04L 69/22: Parsing or analysis of headers - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A packet filtering system uses linked zero-based binary search trees to filter received packets. The binary search trees may be generated from filter conditions defining filter parameters for filtering packets. ## Claims ### Claim at position 1 1-13. (canceled) ### Claim 14 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. ### Claim 15 (depends on 14) The packet filtering system of claim 14, wherein the binary search trees comprise linked zero-based binary search trees including root nodes each having a single subtree comprised of greater than nodes. ### Claim 16 (depends on 15) The packet filtering system of claim 15, wherein the linked zero-based binary search trees comprise addresses of a next linked zero-based binary search tree to traverse to filter the packet in response to a hit on a previous linked zero-based binary search tree. ### Claim 17 (depends on 14) The packet filtering system of claim 14, wherein a node in at least one of the binary search trees is a range node including a range of key values. ### Claim 18 (depends on 17) The packet filtering system of claim 17, wherein the range node specifies an upper end of the range of key values for comparison to the packet data for the received data packets. ### Claim 19 (depends on 14) The packet filtering system of claim 14, wherein a root node in one of the binary search trees is a don't care node that is linked to a second one of the binary search trees in response to a miss on the don't care node. ### Claim 20 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. ### Claim 21 (depends on 20) The computer-implemented method of claim 20, wherein the binary search trees comprise linked zero-based binary search trees including root nodes each having a single subtree comprised of greater than nodes. ### Claim 22 (depends on 21) The computer-implemented method of claim 21, wherein the linked zero-based binary search trees comprise addresses of a next linked zero-based binary search tree to traverse to filter the packet in response to a hit on a previous linked zero-based binary search tree. ### Claim 23 (depends on 20) The computer-implemented method of claim 20, wherein a node in at least one of the binary search trees is a range node including a range of key values. ### Claim 24 (depends on 23) The computer-implemented method of claim 23, wherein the range node specifies an upper end of the range of key values for comparison to the packet data for the received data packets. ### Claim 25 (depends on 20) The computer-implemented method of claim 20, wherein a root node in one of the binary search trees is a don't care node that is linked to a second one of the binary search trees in response to a miss on the don't care node. ### Claim 26 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. ### Claim 27 (depends on 26) The non-transitory computer-readable medium of claim 26, wherein the binary search trees comprise linked zero-based binary search trees including root nodes each having a single subtree comprised of greater than nodes. ### Claim 28 (depends on 27) The non-transitory computer-readable medium of claim 27, wherein the linked zero-based binary search trees comprise addresses of a next linked zero-based binary search tree to traverse to filter the packet in response to a hit on a previous linked zero-based binary search tree. ### Claim 29 (depends on 26) The non-transitory computer-readable medium of claim 26, wherein a node in at least one of the binary search trees is a range node including a range of key values. ### Claim 30 (depends on 29) The computer-implemented method of claim 29, wherein the range node specifies an upper end of the range of key values for comparison to the packet data for the received data packets. ### Claim 31 (depends on 26) The non-transitory computer-readable medium of claim 26, wherein a root node in one of the binary search trees is a don't care node that is linked to a second one of the binary search trees in response to a miss on the don't care node.