US Patent 11588734 Systems for providing an LPM implementation for a programmable data plane through a distributed algorithm

Described are programmable input output (IO) devices comprising: an match processing unit (MPU) and a memory unit. The MPU comprising at least one arithmetic logic unit (ALU). The memory unit having instructions stored thereon which, when executed by the respective programmable IO device, cause the programmable IO device to perform operations. These operations comprise: receiving, from an inbound interface, a packet comprising packet data for at least one range-based element; determining, via the MPU, a lookup result by performing a modified binary search on an interval binary search tree with the packet data to determine a longest prefix match (LPM), wherein the interval binary search tree maps the at least one range-based element to an associated data element; and classifying the packet based on the lookup result.