Apparatus and method for processing alternately configured longest prefix match tables

摘要

A network switch includes a memory configurable to store alternate table representations of an individual trie in a hierarchy of tries. A prefix table processor accesses in parallel, using an input network address, the alternate table representations of the individual trie and searches for a longest prefix match in each alternate table representation to obtain local prefix matches. The longest prefix match from the local prefix matches is selected. The longest prefix match has an associated next hop index base address and offset value. A next hop index processor accesses a next hop index table in the memory utilizing the next hop index base address and offset value to obtain a next hop table pointer. A next hop processor accesses a next hop table in the memory using the next hop table pointer to obtain a destination network address.

主权项

1. A network switch, comprising:
a memory configurable to store alternate table representations of an individual trie in a hierarchy of tries, wherein the alternate table representations are optimized for different longest prefix match search strategies and memory optimization strategies; a hardware prefix table processor to
access in parallel, using an input network address, the alternate table representations of the individual trie and search for a longest prefix match in each alternate table representation to obtain local prefix matches,select the longest prefix match from the local prefix matches, wherein the longest prefix match has an associated next hop index base address and offset value; a next hop index processor to access a next hop index table in the memory utilizing the next hop index base address and offset value to obtain a next hop table pointer; and a next bop processor to access a next hop table in the memory using the next hop table pointer to obtain a destination network address.