Back to results
US 11,770,463 B2Granted
Packet filtering using binary search trees
AssigneeViavi Solutions Inc.
InventorSherwood Johnson
Life of this patent
Estimating the term…
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.
Claims18
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 the received data packets for packet filtering;
- a second memory to store 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 incoming data packets of the received data packets in the first half and the second half of the second memory, and, at a same time, alternate processing stored data packets of the received data packets in the second half and the first half of the second memory,
- wherein the processing circuit is to store a first data packet of the received data packets in the first half of the second memory and, at the same time, process a second data packet of the received data packets previously stored in the second half of the second memory, and
- wherein to process the second data packet, the processing circuit is to compare the second data packet to the node values of the binary search trees in the first memory.
4 more elements
A non-transitory computer-readable storage medium storing instructions, which when executed by a processor, cause the processor to:
- receive data packets from a data packet communication stream;
- store, in a first memory, binary search trees comprising node values for comparison to the received data packets for packet filtering;
- partition a second memory into a first half and a second half;
- and
- alternate storing incoming data packets of the received data packets in the first half and the second half of the second memory and, at a same time, alternate processing stored data packets of the received data packets in the second half and the first half of the second memory, including causing the processor to:
- store a first data packet of the received data packets in the first half of the second memory and, at the same time, process a second data packet of the received data packets previously stored in the second half of the second memory,
- wherein to process the second data packet, the instructions cause the processor to compare the second data packet to the node values of the binary search trees in the first memory.
4 more elements
A method for packet filtering, comprising:
- receiving, by a processor, data packets from a data packet communication stream;
- storing, in a first memory, binary search trees comprising node values for comparison to the received data packets for packet filtering;
- partitioning, by the processor, a second memory into a first half and a second half;
- and
- alternating, by the processor, storing incoming data packets of the received data packets in the first half and the second half of the second memory and, at a same time, alternating, by the processor, processing stored data packets of the received data packets in the second half and the first half of the second memory, including:
- storing a first data packet of the received data packets in the first half of the second memory and, at the same time, processing, by the processor, a second data packet of the received data packets previously stored in the second half of the second memory,
- wherein the processing of the second data packet comprises comparing the second data packet to the node values of the binary search trees in the first memory.
4 more elements
Dependencies are inferred from the claim text.