| 摘要 |
A trie comprising a plurality of subtries may be balanced by storing, in a first memory stage, a first root that identifies a first subtrie of a trie and a second root that identifies a second subtrie, which is a direct or indirect child of the first subtrie. A plurality of network address prefixes representing vertexes in the plurality of subtries may be stored in at least one additional memory stage. As the first subtrie is located on a top subtrie level which may contain relatively fewer network address prefixes, promoting the second subtrie to the top subtrie level may help improve memory utilization. Further, looking up any received network address may have less memory access latency. |
| 主权项 |
1. In a network router comprising a plurality of memory stages including a first memory stage and at least one additional memory stage coupled to the first memory stage, a method for trie-based network address lookup, the method comprising:
storing, in the first memory stage, a first root that identifies a first subtrie of a trie, wherein the trie comprises a plurality of subtries including the first subtrie and a second subtrie that is a direct or indirect child of the first subtrie; storing, in the first memory stage, a second root that identifies the second subtrie; storing, in the at least one additional memory stage, a plurality of network address prefixes representing vertexes in the plurality of subtries; receiving a packet comprising a network address; looking up the first memory stage to identify a matched root, which is one of the first root and the second root, as having the most bits and fully matching with a number of most significant bits (MSBs) in the network address; and looking up the at least one additional memory stage to identify a longest prefix match (LPM) among the plurality of network address prefixes, wherein bits of the LPM have the longest match with a second number of bits in the network address, wherein the second number of bits immediately trails the MSBs, wherein the LPM is a direct or indirect child of the matched root, wherein identifying the LPM comprises looking up one, but not both, of the first subtrie and the second subtrie, wherein the plurality of subtries are divided into a number of subtrie levels, each of which corresponds to one of the at least one additional memory stage, wherein the at least one additional memory stage comprises one or more rich trie node stages each comprising one or more rich trie nodes, wherein each rich trie node stores one or more traversal paths, wherein each of the one or more traversal paths represents a path key from a top vertex of a subtrie to a top vertex of a direct or indirect child subtrie, and wherein the second subtrie has been promoted from a later subtrie level to a first subtrie level. |
