Avoiding markers for longest prefix match based on binary search tree algorithm
In one embodiment, a packet processing apparatus includes interfaces, a memory to store a representation of a routing table as a binary search tree of address prefixes, and store a marker with an embedded prefix including k marker bits providing a marker for an address prefix of a node corresponding to a prefix length greater than k, and n additional bits, such that the k marker bits concatenated with the n additional bits provide another address prefix, packet processing circuitry configured upon receiving a data packet having a destination address, to traverse the binary search tree to find a longest prefix match, compare a key with the k marker bits, extract an additional n bits from the destination address, and compare the extracted n bits with the n additional bits, and process the data packet in accordance with a forwarding action indicated by the longest prefix match.
1. 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, the binary search tree being ordered by prefix lengths and having nodes, such that each node j of the nodes in the binary search tree corresponds to a respective prefix length Lj;
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 most significant bits (MSB), and each entry in the respective hash table comprising a matching value corresponding to a forwarding action; and
store a marker with an embedded prefix as one of the entries in the respective hash table of a first one of the nodes, corresponding to a prefix length k, the marker with the embedded prefix including: (a) k marker bits providing a marker for a first address prefix in the respective hash table of a second one of the nodes corresponding to a prefix length greater than k; (b) n additional bits, such that the k marker bits concatenated with the n additional bits provide a second one of the address prefixes in the respective hash table of the first node instead of in the respective hash table of a third one of the nodes corresponding to a prefix length k plus n; (c) a forwarding action; and
packet processing circuitry 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, extract, at each node j that is traversed, a key of length Lj from the destination address, and perform a hash lookup in the respective hash table with the key to find a matching entry;
for the first node: compare the key with the k marker bits of the marker with the embedded prefix; upon a match of the key with the k marker bits, extract an additional n bits from the destination address; and compare the extracted n bits of the destination address with the n additional bits of the marker with the embedded prefix; and
process the data packet in accordance with the forwarding action indicated by the matching entry that corresponds to the longest prefix match.
2. The apparatus according to claim 1 , wherein:
the marker with the embedded prefix includes an action field to check the n additional bits; and
the packet processing circuitry is configured to compare the extracted n bits of the destination address with the n additional bits of the marker with the embedded prefix responsively to the action field to check the n additional bits.
3. The apparatus according to claim 1 , wherein the packet processing circuitry is configured to process the data packet in accordance with the forwarding action of the marker with the embedded prefix responsively to the extracted n bits of the destination address matching the n additional bits of the marker with the embedded prefix.
4. The apparatus according to claim 1 , wherein the binary search tree does not include any marker without an embedded prefix.
5. The apparatus according to claim 1 , further comprising a controller configured to: generate the marker with the embedded prefix responsively to the second address prefix in the respective hash table of the third node; and remove the second address prefix from the respective hash table of the third node.
6. The apparatus according to claim 5 , wherein the controller is configured to select the second address prefix from a selection of the address prefixes responsively to the second address prefix having a longest prefix from among the selection of the address prefixes.
7. The apparatus according to claim 6 , wherein the binary search tree includes at least one marker without an embedded prefix.
8. The apparatus according to claim 7 , wherein the controller is configured to remove the n additional bits from the marker with the embedded prefix such that the marker with the embedded prefix becomes a marker without an embedded prefix.
9. The apparatus according to claim 7 , wherein the controller is configured to update the marker with the embedded prefix to refer to a third one of the address prefixes instead of referring to the second address prefix.
10. A packet processing method, comprising:
receiving and transmitting data packets from and to a network;
storing a representation of a routing table for the network as a binary search tree of address prefixes, the binary search tree being ordered by prefix lengths and having nodes, such that each node j of the nodes in the binary search tree corresponds to a respective prefix length Lj;
storing 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 most significant bits (MSB), and each entry in the respective hash table comprising a matching value corresponding to a forwarding action;
storing a marker with an embedded prefix as one of the entries in the respective hash table of a first one of the nodes, corresponding to a prefix length k, the marker with the embedded prefix including: (a) k marker bits providing a marker for a first address prefix in the respective hash table of a second one of the nodes corresponding to a prefix length greater than k; (b) n additional bits, such that the k marker bits concatenated with the n additional bits provide a second one of the address prefixes in the respective hash table of the first node instead of in the respective hash table of a third one of the nodes corresponding to a prefix length k plus n; (c) a forwarding action; and
upon receiving a data packet having a destination address:
traversing the binary search tree to find a longest prefix match between the destination address and the address prefixes;
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 with the key to find a matching entry;
for the first node: comparing the key with the k marker bits of the marker with the embedded prefix; upon a match of the key with the k marker bits, extracting an additional n bits from the destination address; and comparing the extracted n bits of the destination address with the n additional bits of the marker with the embedded prefix; and
processing the data packet in accordance with the forwarding action indicated by the matching entry that corresponds to the longest prefix match.
11. The method according to claim 10 , wherein the marker with the embedded prefix includes an action field to check the n additional bits, the method further comprising comparing the extracted n bits of the destination address with the n additional bits of the marker with the embedded prefix responsively to the action field to check the n additional bits.
12. The method according to claim 10 , wherein processing includes processing the data packet in accordance with the forwarding action of the marker with the embedded prefix responsively to the extracted n bits of the destination address matching the n additional bits of the marker with the embedded prefix.
13. The method according to claim 10 , wherein the binary search tree does not include any marker without an embedded prefix.
14. The method according to claim 10 , further comprising:
generating the marker with the embedded prefix responsively to the second address prefix in the respective hash table of the third node; and
removing the second address prefix from the respective hash table of the third node.
15. The method according to claim 14 , further comprising selecting the second address prefix from a selection of the address prefixes responsively to the second address prefix having a longest prefix from among the selection of the address prefixes.
16. The method according to claim 15 , wherein the binary search tree includes at least one marker without an embedded prefix.
17. The method according to claim 16 , further comprising removing the n additional bits from the marker with the embedded prefix such that the marker with the embedded prefix becomes a marker without an embedded prefix.
18. The method according to claim 16 , further comprising updating the marker with the embedded prefix to refer to a third one of the address prefixes instead of referring to the second address prefix.