Longest prefix matching (LPM) using a fixed comparison hash table

• US 20040085953A1
• Filed: 10/30/2002
• Published: 05/06/2004
• Est. Priority Date: 10/30/2002
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Davis, Andrew
• Granted Patent: US 7,443,841 B2
• Time in Patent Office: Days
• US Class Current: 370/356
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]

Abstract

Described are an apparatus and method of forwarding Internet Protocol (IP) packets. At least one fixed-length key having a predetermined number of bits is produced in response to an IP address in an IP packet. At least a portion of the fixed-length key is hashed to obtain a hash value. The fixed-length key is compared with a key value stored in each data-item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

Claims

1. A method of forwarding Internet Protocol (IP) packets, comprising:

producing at least one fixed-length key having a predetermined number of bits in response to an IP address in an IP packet;

hashing at least a portion of the fixed-length key to obtain a hash value; and

comparing the fixed-length key with a key value stored in each data item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

2. The method of claim 1, wherein each comparison of the fixed-length key with a key value occurs as a single comparison without masking.

3. The method of claim 1, wherein the step of producing a fixed-length key includes appending at least one fill bit and at least one prefix length bit to a predetermined number of IP address bits.

4. The method of claim 3, wherein the at least one fill bit has a predetermined value.

5. The method of claim 1, wherein the hashed portion of the fixed-length key is the entire fixed-length key.

6. The method of claim 1, further comprising constructing a length table based on an IP address prefix tree.

7. The method of claim 6, further comprising defining a predetermined number of prefix bits of the IP address to be an index to the length table.

8. The method of claim 7, further comprising associating at least one prefix length with each index to the length table.

9. The method of claim 8, wherein the step of producing at least one fixed-length key produces a fixed-length key for each prefix length that is listed in the length table as being associated with the index defined by the prefix bits of the IP address.

10. An apparatus for forwarding IP packets, comprising:

a key generator producing a fixed-length key having a predetermined number of bits in response to an IP address;

a hash value generator hashing a portion of the key to produce a hash value; and

a comparator comparing the fixed-length key with a key value stored in each data item in a hash bucket associated with the hash value to find the data item that has the key value that matches the fixed-sized key and to obtain from that data item routing information that is used to forward the IP packet.

11. The apparatus of claim 10, wherein each comparison performed by the comparator occurs as a single comparison without masking.

12. The apparatus of claim 10, wherein at least one of the key generator, hash value generator, and comparator is implemented in hardware.

13. The apparatus of claim 10 wherein at least one of the key generator, hash value generator, and comparator is implemented in software.

14. The apparatus of claim 10, wherein the fixed-length key includes at least one IP address prefix bit, at least one length bit to indicate a number of prefix bits in the fixed-length key, and a sufficient number of fill bits such that the fixed-length key has the predetermined number of bits.

15. The apparatus of claim 14, wherein each fill bit has a predetermined bit value.

16. The apparatus of claim 10, wherein the portion of the fixed-length key that is hashed by the hash value generator is the entire fixed-length key

17. The apparatus of claim 10, further comprising a length table constructed in response to an IP address prefix tree.

18. The apparatus of claim 10, wherein the length table includes a plurality of entries, each entry having an index value and at least one prefix length value.

19. The apparatus of claim 18 wherein a predetermined number of prefix bits of the IP address provide an index to the length table.

20. The apparatus of claim 19, wherein the key generator produces a fixed-length key for each prefix length value that is listed in the length table as being associated with the index defined by the prefix bits of the IP address.