# US 2023/0275979 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 2023/0275979 A1
- Document ID: US20230275979A1
- Status: Published application
- Kind: A1
- Application number: 18/142,101
- Filed: 2023-05-02
- Published: 2023-08-31
- Earliest claimed: 2016-08-31
- Assignees: Viavi Solutions Inc.
- Applicants: Viavi Solutions Inc.
- Inventors: Sherwood JOHNSON
- Web page: https://patentgrep.com/patent/US20230275979A1

## 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-19. (canceled)

### 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 incoming data packets 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 incoming 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 storing instructions for creating binary search trees, wherein the instructions, when executed, cause a processor to:
receive packet filtering conditions;
store the packet filtering conditions in a flow table;
sort 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
create 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 incoming data packets 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 non-transitory computer-readable medium of claim 29, wherein the range node specifies an upper end of the range of key values for comparison to incoming 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.

### Claim 32

A system comprising:
a processor; and
a memory storing instructions for creating binary search trees, wherein the instructions, when executed by the processor, cause the processor to:
receive packet filtering conditions;
store the packet filtering conditions in a flow table;
sort 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
create the binary search trees from the sorted flow table.

### Claim 33 (depends on 32)

The system of claim 32, 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 34 (depends on 33)

The system of claim 33, wherein the linked zero-based binary search trees comprise addresses of a next linked zero-based binary search tree to traverse to filter incoming data packets in response to a hit on a previous linked zero-based binary search tree.

### Claim 35 (depends on 32)

The system of claim 32, wherein a node in at least one of the binary search trees is a range node including a range of key values.

### Claim 36 (depends on 35)

The system of claim 35, wherein the range node specifies an upper end of the range of key values for comparison to incoming data packets.

### Claim 37 (depends on 32)

The system of claim 32, 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.
