Systems and methods for optimizing a packet classification algorithm for implementation by a packet processing pipeline

Abstract

Interval binary tree definitions and binary tree definitions can be stored in the memory of a networking device. The interval binary trees can map IP address ranges and port ranges to class identifiers. A networking device receives an IP packet that has a layer 3 header that includes an IP address and a port number. The networking device can use the IP address, the port number, and the interval binary trees to determine a first class identifier and a second class identifier. The first class identifier can indicate a binary tree definition that is searched for the second class identifier. The search identifies yet another class identifier that the networking device uses to determine a networking rule to apply to the IP packet. This technique uses far less memory than the RFC algorithm commonly used to determine a networking rule to apply to the IP packet.