Method and apparatus for performing network routing with use of power efficient TCAM-based forwarding engine architectures
A multi-stage (e.g., two-stage) packet-based lookup process using a Ternary Content Addressable Memory (TCAM) divided into partitions. The result of a first stage lookup is used to selectively search one of a plurality of TCAM partitions during the second stage. A subset of destination address bits may be used in the first stage to hash to a selected partition for the second stage. Alternatively, a partitioning algorithm segments a routing trie into partitions, and then, either a separate, small TCAM or one of the partitions is used in the first stage to map a prefix of the destination address to one of the TCAM partitions for use in the second stage. The “trie-based” algorithms may advantageously partition the trie such that each second stage partition comprises a substantially contiguous sequence of routing prefixes in a post-order traversal of the routing trie, together with one or more covering prefixes thereof.
1. A method for processing data packets at a network node of a packet-based communications network, the method making use of one or more Ternary Content Addressable Memory, TCAM, devices which have been subdivided into a plurality of sub-tables, the method comprising the steps of:
receiving a data packet having packet header information associated therewith;
performing a first analysis of said packet header information to determine an identifier specifying one or more of said sub-tables of said one or more TCAM devices, wherein said one or more specified sub-tables comprise less than all of said plurality of sub-tables of said one or more TCAM devices; and
performing a lookup in said one or more TCAM devices based on said identifier to retrieve categorization information associated with said packet header information, said lookup being limited to said one or more specified sub-tables of said one or more TCAM devices,
wherein said step of performing a first analysis of said packet header information comprises performing a first-level lookup in a first-level TCAM device for use in said determination of said identifier, and
wherein said categorization information has been derived based on a trie containing packet categorization information, wherein said trie has been partitioned into a first-level trie portion and a plurality of second-level trie portions, wherein said first-level TCAM device contains said first-level trie portion, wherein said one or more TCAM devices which have been subdivided into a plurality of sub-tables have been partitioned into a plurality of sub-table groups, each sub-table group comprising one or more of said sub-tables, and wherein each of said sub-table groups contains one of said second-level trie portions.
2. The method of claim 1 , wherein said packet header information comprises a packet destination, and wherein said categorization information comprises packet routing information.
3. The method of claim 2 , wherein said destination comprises a sequence of a plurality of bits, and wherein said step of performing a first analysis of said destination comprises performing a hash function based on a subset of said plurality of bits.
4. The method of claim 1 , wherein said one or more TCAM devices which have been subdivided into a plurality of sub-tables do not include said first-level TCAM device used in said first-level lookup.
5. The method of claim 1 , wherein said first-level TCAM device comprises one or more of said sub-tables of said one or more TCAM devices which have been subdivided into a plurality of sub-tables.
6. The method of claim 1 , wherein said trie has been partitioned by performing a post-order traversal of said trie, and wherein each of said sub-table groups containing one of said second-level trie portions comprises:
(i) one or more prefixes associated with one or more corresponding trie nodes encountered during said post-order traversal; and
(ii) one or more covering prefixes of said one or more corresponding trie nodes, wherein said covering prefixes of said trie nodes comprise lowest common ancestors thereof.
7. The method of claim 6 , wherein said trie has been partitioned such that each of said second-level portions consists of substantially one complete subtree of said trie, and wherein each of said sub-table groups containing one of said second-level trie portions comprises a number of said prefixes associated with said corresponding trie nodes included in said one complete subtree, said number being between a predetermined lower bound and a predetermined upper bound.
8. The method of claim 6 , wherein said trie has been partitioned such that each of said sub-table groups containing one of said second-level trie portions consists of a substantially fixed, predetermined number of said prefixes.
9. A lookup engine for processing data packets at a network node of a packet-based communications network, the lookup engine comprising:
an input port for receiving a data packet having packet header information associated therewith;
a first circuit for determining an identifier based on said packet header information; and
one or more Ternary Content Addressable Memory, TCAM, devices which have been subdivided into a plurality of sub-tables,
wherein said identifier specifics one or more of said sub-tables of said one or more TCAM devices, wherein said one or more specified sub-tables comprise less than all of said plurality of sub-tables of said one or more TCAM devices, and wherein said one or more TCAM devices contain categorization information associated with said packet header information, said categorization information retrieved from said one or more TCAM devices by performing a lookup therein based on said identifier, said lookup being limited to said one or more specified sub-tables of said one or more TCAM devices,
wherein said first circuit comprises a first-level TCAM device for use in a first-level lookup to determine said identifier, and
wherein said categorization information has been derived based on a trie comprising packet categorization information, wherein said trie has been partitioned into a first-level trie portion and a plurality of second-level tie portions, wherein said first-level TCAM device contains said first-level trie portion, wherein said one or more TCAM devices which have been subdivided into a plurality of sub-tables have been partitioned into a plurality of sub-table groups, each sub-table group comprising one or more of said sub-tables, and wherein each of said sub-table groups contains one of said second-level trie portions.
10. The lookup engine of claim 9 , wherein said packet header information comprises a packet destination and wherein said categorization information comprises packet routing information.
11. The lookup engine of claim 10 , wherein said destination comprises a sequence of a plurality of bits, and wherein said first circuit comprises means for performing a hash function based on a subset of said plurality of bits.
12. The lookup engine of claim 9 , wherein said one or more TCAM devices which have been subdivided into a plurality of sub-tables do not include said first-level TCAM device used in said first-level lookup.
13. The lookup engine of claim 9 , wherein said first-level TCAM device comprises one or more of said sub-tables of said one or more TCAM devices which have been subdivided into a plurality of sub-tables.
14. The lookup engine of claim 9 , wherein said trie has been partitioned by performing a post-order traversal of said trie, and wherein each of said sub-table groups containing one of said second-level trie portions comprises:
(i) one or more prefixes associated with one or more corresponding trie nodes encountered during said post-order traversal; and
(ii) one or more covering prefixes of said one or more corresponding trie nodes, wherein said covering prefixes of said trie nodes comprise lowest common ancestors thereof.
15. The lookup engine of claim 14 , wherein said trie has been partitioned such that each of said second-level portions consists of substantially one complete subtree of said trie, and wherein each of said sub-table groups containing one of said second-level trie portions comprises a number of said prefixes associated with trie nodes included in said one complete subtree, said number being between a predetermined lower bound and a predetermined upper bound.
16. The lookup engine of claim 14 , wherein said trie has been partitioned such that each of said sub-table groups containing one of said second-level trie portions consists of a substantially fixed, predetermined number of said prefixes.