Algorithmic longest prefix matching in programmable switch
View Patent ↗Some embodiments provide a method for configuring unit memories (e.g., unit static random access memories (SRAMs) and ternary content addressable memories (TCAMs) of a network forwarding IC to implement a set of longest prefix matching (LPM) tables. Two different methods of providing a longest prefix match (LPM) operation that minimize the use of ternary content addressable memory (TCAM) are presented. Each method takes advantage of the use of match-action stages and the programmability of the unit memories. An algorithmic LPM embodiment is presented which uses a TCAM index with pointers to SRAM partitions that store subtrees of a routing tree (routing trie structure) and performs subtree rearrangements in the partitions upon the addition of certain routing entries. A chained LPM embodiment, allocates separate exact-match tables for a set of address prefix lengths in, for example, SRAMS, as well as a set of non-exact match tables in, for example, TCAMs.
1. A forwarding element that comprises:
a data plane circuit comprising a plurality of data processing stages to process data tuples associated with data messages received by the forwarding element in order to forward data messages in a network, the data plane circuit comprising a first memory type to store a tree data structure as separate sub-trees in a plurality of partitions of the first memory type, and a second memory type to store pointers to the plurality of partitions of the first memory type; and
a control plane circuit to detect that a sub-tree data structure in a first partition must be divided, identify a root node for a sub-tree of the tree data structure to be stored in a second memory partition in the plurality of memory partitions, and configure the data plane circuit to store the identified sub-tree in the second memory partition.
2. The forwarding element of claim 1 , where the control plane circuit is to receive a request to add an additional entry to the sub-tree data structure stored in the first partition and, based on the received request, detect that the sub-tree data structure must be divided.
3. The forwarding element of claim 2 , wherein detect that the sub-tree data structure must be divided comprises detect that the first partition cannot store the additional routing entry.
4. The forwarding element of claim 1 , wherein detect that the sub-tree data structure must be divided comprises detect that the first partition has room for less than a threshold number of additional entries in the tree data structure.
5. The forwarding element of claim 1 , wherein identify a root node comprises identify a root node for a sub-tree of the sub-tree that must be divided that contains a number of entries between a minimum and a maximum number of entries, the minimum and maximum number of entries depending on the size of each of the plurality of memory partitions.
6. The forwarding element of claim 5 , wherein the partitions in the first type of memory are of a same size.
7. The forwarding element of claim 6 , wherein the minimum number of entries is one half of the size of a memory partition in the plurality of memory partitions.
8. The forwarding element of claim 6 , wherein the maximum number of entries is the size of a memory partition in the plurality of memory partitions.
9. The forwarding element of claim 1 , wherein, after the identified sub-tree is stored in the second partition, the control plane circuit is to further configure the second memory type to store a pointer to the second partition for the identified sub-tree.
10. The forwarding element of claim 9 , wherein, after the pointer for the identified sub-tree is stored, the control plane circuit is to configure the first memory type to delete the identified sub-tree from the first partition.
11. The forwarding element of claim 10 , wherein,
before configuration of the second memory type to store the pointer, the control plane circuit receives a confirmation that the first memory type stores the identified sub-tree in the second partition, and
before configuration of the first memory type to delete the identified sub-tree, the control plane circuit receives a confirmation that the second memory type stores the pointer for the identified sub-tree.
12. The forwarding element of claim 1 , wherein the number of sub-trees that can be stored in a partition of the first memory type is limited by the control plane circuit.
13. The forwarding element of claim 1 , wherein the data plane circuit is to use the first and second type of memories to perform a longest prefix matching operation for a data message received by the forwarding element and comprising:
search the second type of memory for a pointer associated with a root node identifier with a longest matching prefix to identify a partition in the first type of memory that stores a longest prefix match for a received data message;
search the identified partition of the first memory type to identify a longest matching prefix.
14. The forwarding element of claim 1 , wherein the tree structure is a trie structure identifying a prefix in an address space.
15. The forwarding element of claim 1 , wherein each partition is to store at least one of a rule, action, or pointer associated with each valid node of each sub-tree stored in the partition, a valid node being a node for which a rule, action, or pointer is defined.
16. The forwarding element of claim 15 , wherein each partition is to store a sub-tree rooted at an invalid node stores at least one of a rule, action, or pointer associated with a covering node of a sub-tree rooted at an invalid node, a covering node being a most-recent ancestor in the larger tree structure that is valid.
17. The forwarding element of claim 1 , wherein the second memory type is a ternary content addressable memory (TCAM).
18. The forwarding element of claim 1 , wherein the first memory type is a static random-access memory.
19. The forwarding element of claim 1 , wherein the sub-tree rooted at the identified root node is a first sub-tree, wherein the control plane circuit further is to identify a second, smaller sub-tree, stored in the second memory partition, the second memory partition having enough space to store the first sub-tree if the second sub-tree is removed from the second memory partition, wherein configure the data plane circuit to store the first sub-tree in the second memory partition is part of a swapping operation performed by the control plane circuit that swaps the first and second sub-trees between the first and second memory partitions.
20. The forwarding element of claim 18 , wherein the swapping operation of the first and second sub-trees comprises configuration of the first memory type to: store the second sub-tree to a third memory partition; store, after deleting the second sub-tree from the second memory partition, the first sub-tree to the second memory partition in order to store the first sub-tree in the second memory partition; and store the second sub-tree to the first memory partition, wherein the second sub-tree is deleted from the third partition to maintain the third partition as an empty partition that participates in further swapping operations.
21. The forwarding element of claim 19 , wherein the swapping operation of the first and second sub-trees further comprises configuration of the second memory type to: update, after storage of the second sub-tree to the third memory partition, the pointers stored in the second memory type to reflect the second sub-tree's new location in the third memory partition; update, after storage of the first sub-tree to the second memory partition, the pointers stored in the second memory type to reflect the first sub-tree's new location in the second memory partition; and update, after storage of the second sub-tree to the first memory partition, the pointers stored in the second memory type to reflect the second sub-tree's new location in the first memory partition.