Filter based longest prefix match algorithm

• US 20050175010A1
• Filed: 02/09/2004
• Published: 08/11/2005
• Est. Priority Date: 02/09/2004
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Bou-Diab, Bashar Said, Wilson, David James
• Granted Patent: US 7,433,355 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Methods directed to longest prefix matching and systems directed to IP address lookups are presented. The methods and systems relate in particular to IPv6 and comprise finding the longest prefix match (LPM) for an IP address. The method of the invention results in the use of filters to perform LPM. In embodiments of the invention, partial address filtering is used to further reduce filtering requirements. Reducing the number of filtering operations has the advantage of making the LPM algorithm faster and less costly to implement than prior art approaches. Also described is an “ideal offset filter” that extracts a fixed sized sliding window of bits from the IP address being processed.

Claims

1. A method of performing a longest prefix match comprising the steps of:

a) filtering a key into a plurality of filter fields, each of which is associated with a respective filter table;

b) performing a longest prefix match (LPM) operation on each of the filter fields in their respective filter tables, wherein each LPM operation yields a result indicating lengths of prefixes potentially matching the key;

c) intersecting the results to obtain a set of potential prefix lengths; and

d) performing a series of hash lookups, based on the previously indicated potential prefix lengths, beginning with the longest potential prefix length and progressing to successively shorter potential prefix lengths until a matching prefix is found, which is the longest prefix matching the key.

2. The method as defined in claim 1 wherein each filter may use a different method for filter field extraction.

3. The method as defined in claim 1 wherein the key is an IP address.

4. The method as defined in claim 3 wherein the hash lookups are used for routing decisions.

5. The method as defined in claim 3 wherein the plurality of filter fields are created by extracting bits from the IP address.

6. The method as defined in claim 5 wherein the extracted bits are concatenated into filter fields, each filter field being a key for said associated filter table.

7. The method as defined in claim 1 wherein the longest prefix match operation on each filter field and associated filter table is performed in parallel.

8. The method as defined in claim 7 wherein a lookup table is used to perform the LPM operation.

9. The method as defined in claim 7 wherein a tree lookup is used to perform the LPM operation.

10. The method as defined in claim 1 applied to performing a new route insertion into a hash table.

11. The method as defined in claim 1 applied to the deletion of a route from a hash table.

12. The method as defined in claim 11 wherein the hash table is updated to delete the route.

13. The method as defined in claim 3 wherein only a portion of the IP address is filtered into filter fields.

14. The method as defined in claim 3 wherein the IP address is 128 bits long.

15. The method as defined in claim 3 wherein the IP address is 32 bits long.

16. The method as defined in claim 3 wherein an ideal offset filter is used.

17. A system for performing a longest prefix match, comprising:

a plurality of filter fields each created by filtering a key, each filter field being associated with a respecting filter table;

means to perform a longest prefix match (LPM) operation on each of the filter fields in their respective filter tables, wherein each LPM operation yields a result indicating potential prefix lengths of a longest prefix matching the key;

means to intersect the results to obtain a set of potential prefix lengths; and

means to search multiple logical hash tables, each associated with a specific prefix length, for a longest prefix match, in a linear fashion, wherein the search is performed using the set of potential prefix lengths starting at the longest potential prefix length and progressing to successively shorter potential prefix lengths until a matching prefix is found.

18. The system as defined in claim 17 wherein the filter fields are bit interleaved filters.

19. The system as defined in claim 17 wherein the key is an IP address.

20. The system as defined in claim 17 wherein the LPM operation is performed in a lookup table.

21. The system as defined in claim 19 wherein the IP address is 128 bits long consistent with IPv6.

22. The system as defined in claim 19 wherein the IP address is 32 bits long consistent with IPv4.