Method for IP longest prefix match using prefix length sorting
View Patent ↗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.
2. The non-transitory tangible computer readable storage medium of claim 1 , wherein each forwarding rule is inserted into at most one of the prefix length memory tables associated with the unique range of prefix lengths encompassing a prefix length of the forwarding rule.
3. The non-transitory tangible computer readable storage medium of claim 1 , wherein the IP address is a 32 bit Internet Protocol version 4 (IPv4) address.
4. The non-transitory tangible computer readable storage medium of claim 1 , wherein the set of prefix length memory tables includes six prefix length memory tables, each of the six prefix length memory tables storing forwarding rules with a disjoint range of prefix lengths.
5. The non-transitory tangible computer readable storage medium of claim 1 , wherein the set of prefix length memory tables includes a first prefix length memory table to hold forwarding rules associated with prefixes up to a first number of bits, a second prefix length memory table to hold forwarding rules associated with prefixes from the first number of bits plus 1 to a second number of bits, a third prefix length memory table to hold forwarding rules associated with prefixes from the second number of bits plus 1 to a third number of bits, and a fourth prefix length memory table to hold forwarding rules associated with prefixes from the third number of bits plus 1 to a fourth number of bits.
6. 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 an IP longest prefix match on an IP address in parallel in each of the set of prefix length memory tables comprises passing a corresponding number of most significant bits of the IP address to each of the prefix length memory tables, the corresponding number for each of the prefix length memory table depending on the highest range of prefix lengths handled by that prefix length memory table.
7. 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 selecting the IP longest prefix match from the set of prefix matches comprises receiving an indication of a longest prefix match with a valid bit set from at least two of the set of prefix length memory tables, and selecting the longest prefix match from one of the at least two of the set of prefix length memory tables configured to store forwarding rules with longer prefixes.
8. 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;
selecting the IP longest prefix match from the set of prefix matches; and
implementing a set of secondary prefix length memory tables containing entries associated with forwarding rules having prefix lengths exceeding a maximum prefix length range of the set of prefix length memory tables.
9. The non-transitory tangible computer readable storage medium of claim 8 , wherein the maximum prefix length range of the set of prefix length memory tables is 24 bits.
10. The non-transitory tangible computer readable storage medium of claim 8 , the method further comprising the step of performing an IP longest prefix match on the IP address in a selected one of the set of secondary prefix length memory tables.
11. The non-transitory tangible computer readable storage medium of claim 10 , 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, and wherein the step of performing the IP longest prefix match on the IP address in a selected one of the set of secondary prefix length memory tables is implemented in a separate memory access operation.
12. The non-transitory tangible computer readable storage medium of claim 11 , wherein the separate memory access operation is a subsequent memory access operation.
13. The non-transitory tangible computer readable storage medium of claim 1 , the method further comprising the step of using a value associated with the selected IP longest prefix match to key into an IP next hop forwarding table.
14. The non-transitory tangible computer readable storage medium of claim 7 , 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.
15. A network element, comprising:
an input interface, a forwarding function, a memory, and an output interface, the forwarding function interacting with the memory to make forwarding decisions in connection with receipt of packets on the input interface and forwarding of the packets on the output interface;
wherein the memory contains a set of data structures, the set of data structures comprising:
a first data structure containing a first set of forwarding rules associated with a first range of prefix lengths, the first range of prefix lengths being associated with forwarding rules of up to a first number of bits;
a second data structure containing a second set of forwarding rules associated with a second range of prefix lengths, the second range of prefix lengths being disjoint from the first range and encompassing prefix lengths being associated with forwarding rules of the first number of bits plus 1 to a second number of bits; and
a third data structure containing a third set of forwarding rules associated with a third range of prefix lengths, the third range of prefix lengths being disjoint from the first and second ranges and encompassing prefix lengths being associated with forwarding rules of the second number of bits plus 1 to a third number of bits;
wherein the memory is configured to implement an IP longest prefix match on the IP address is implemented in each of the first, second, and third data structures in parallel in a single memory access operation.
16. The network element of claim 15 , wherein the set of data structures further comprises:
a fourth data structure containing a fourth set of forwarding rules associated with a fourth range of prefix lengths, the fourth range of prefix lengths being disjoint from the first through third ranges and encompassing prefix lengths being associated with forwarding rules of the third number of bits plus 1 to a fourth number of bits;
a fifth data structure containing a fifth set of forwarding rules associated with a fifth range of prefix lengths, the fifth range of prefix lengths being disjoint from the first through fourth ranges and encompassing prefix lengths being associated with forwarding rules of the fourth number of bits plus 1 to a fifth number of bits.
17. The network element of claim 16 , further comprising a set of secondary prefix length memory tables containing entries associated with forwarding rules having prefix lengths exceeding the fifth number of bits.
18. The network element of claim 1 , wherein the first number of bits is 8, the second number of bits is 12, the third number of bits is 16, the fourth number of bits is 20, and the fifth number of bits is 24.
19. The network element of claim 15 , further comprising a multiplexer configured to receive inputs from each of the data structures in connection with performance of an Internet Protocol version 4 (IPv4) Longest Prefix Match operation, and output an address to a data structure implementing a next hop forwarding table.
20. The network element of claim 19 , wherein the multiplexer is under the control of a priority encoder, the priority encoder being configured to preference selection of a valid entry from a data structure containing longer prefix lengths.