Patent attributes
Approaches, techniques, and mechanisms are disclosed for maintaining efficient representations of prefix tables for utilization by network switches and other devices. In an embodiment, the performance of a network device is greatly enhanced using a working representation of a prefix table that includes multiple stages of prefix entries. Higher-stage prefixes are stored in slotted pools. Mapping logic, such as a hash function, determines the slots in which a given higher-stage prefix may be stored. When trying to find a longest-matching higher-stage prefix for an input key, only the slots that map to that input key need be read. Higher-stage prefixes may further point to arrays of lower-stage prefixes. Hence, once a longest-matching higher-stage prefix is found for an input key, the longest prefix match in the table may be found simply by comparing the input key to lower-stage prefixes in the array that the longest-matching higher-stage prefix points to.
