Optimized trie-based address lookup

A router, comprising:

• a storage storing, in a data structure corresponding to a rich prefix node associated with a trie, a plurality of network address prefixes represented by a subtrie of the trie;
• a forwarding table management mechanism configured to express the network address prefixes using:
• a chunk vector indicating a presence of a network address prefix in a chunk of the subtrie, wherein the chunk represents a sub-tree of the subtrie;
• and
• an encoded representation of a node in the chunk;
• and
• a longest prefix matching mechanism configured to match a network address with a longest prefix from the network address prefixes stored in the data structure corresponding to the rich prefix node.

A method, comprising:

• storing, in a data structure corresponding to a rich prefix node associated with a trie, a plurality of network address prefixes represented by the trie;
• expressing a respective network address prefix using one or more of:
• a traversal path on the trie from a root node to a subtrie of the trie;
• and
• an encoded representation of a node in the subtrie;
• and
• matching a network address with a longest prefix from the network address prefixes stored in the data structure corresponding to the rich prefix node.

A method, comprising:

• storing, in a data structure corresponding to a rich prefix node associated with a trie, a plurality of network address prefixes represented by a subtrie of the trie;
• expressing the network address prefixes using:
• a chunk vector indicating a presence of a network address prefix in a chunk of the subtrie, wherein the chunk represents a sub-tree of the subtrie;
• and
• an encoded representation of a node in the chunk;
• and
• matching a network address with a longest prefix from the network address prefixes stored in the data structure corresponding to the rich prefix node.