Method for IP longest prefix match using prefix length sorting

摘要

Prefix length memory tables are used to enable fast IPv4 LPM lookups using a single memory access for a first range of IP prefixes, and using two memory accesses for larger IP prefixes. Each of the prefix length memory tables is used to hold a set of forwarding rules associated with a different prefix length range. IP LPM operations are then performed in parallel in each of the prefix length memory tables of the set, and the forwarding rule matching the longest prefix is returned from each of the memory tables. A priority encoder is used to select between positive results from the multiple prefix length memory tables to enable the forwarding rule with the largest matching prefix to be used to key into the next hop forwarding table. The method utilizes low cost DDR SDRAM rather than TCAM, and also exhibits low overhead.

主权项

1. A non-transitory tangible computer readable storage medium having stored thereon a computer program for implementing a method of Internet Protocol (IP) longest prefix match, the computer program comprising a set of instructions which, when executed by a computer, cause the computer to perform a method comprising the steps of:
implementing a set of prefix length memory tables, each of the prefix length memory tables storing forwarding rules associated with a unique range of prefix lengths; performing an IP longest prefix match on an IP address in each of the set of prefix length memory tables in parallel to return a set of prefix matches; and selecting the IP longest prefix match from the set of prefix matches; wherein the step of performing the IP longest prefix match on the IP address is implemented in each of the set of prefix length memory tables in parallel in a single memory access operation.