Longest prefix match using a binary search tree with compressed hash tables

Packet processing apparatus, comprising:

• a plurality of interfaces configured to receive and transmit data packets from and to a network;
• a memory, which is configured to store a representation of a routing table for the network as a binary search tree of address prefixes ordered by prefix lengths, such that each node j in the binary search tree corresponds to a respective prefix length Lj, and to store for each node j in the binary search tree, a respective hash table comprising entries representing the address prefixes of length Lj, each address prefix comprising Lj−c most significant bits (MSB) and c least significant bits (LSB), and each entry in the respective hash table comprising a matching value corresponding to the Lj−c MSB of one or more of the address prefixes and one or more action codes indexed by the c LSB of the one or more of the address prefixes;
• and
• packet processing circuitry, which is configured, upon receiving through one of the interfaces a data packet having a destination address, to traverse the binary search tree to find a longest prefix match between the destination address and the address prefixes by extracting, at each node j that is traversed, a key of length Lj from the destination address, performing a hash lookup in the respective hash table over the Lj−c MSB of the key to find a matching entry, and selecting from the matching entry an action code indicated by the c LSB of the key, and to process the data packet in accordance with the action code indicated by the matching entry that corresponds to the longest prefix match.

A computer software product, comprising a non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a programmable processor, cause the processor to store, in a memory, a representation of a routing table for a network as a binary search tree of address prefixes ordered by prefix lengths, such that each node j in the binary search tree corresponds to a respective prefix length Lj, and to store for each node j in the binary search tree, a respective hash table comprising entries representing the address prefixes of length Lj, each address prefix comprising Lj−c most significant bits (MSB) and c least significant bits (LSB), and each entry in the respective hash table comprising a matching value corresponding to the Lj−c MSB of one or more of the address prefixes and one or more action codes indexed by the c LSB of the one or more of the address prefixes,

• wherein the instructions cause the processor, upon receiving from the network a data packet having a destination address, to traverse the binary search tree to find a longest prefix match between the destination address and the address prefixes by extracting, at each node j that is traversed, a key of length Lj from the destination address, performing a hash lookup in the respective hash table over the Lj−c MSB of the key to find a matching entry, and selecting from the matching entry an action code indicated by the c LSB of the key, and to process the data packet in accordance with the action code indicated by the matching entry that corresponds to the longest prefix match.