Bounded index extensible hash-based IPv6 address lookup method

• US 7,325,059 B2
• Filed: 05/15/2003
• Issued: 01/29/2008
• Est. Priority Date: 05/15/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Batacharia, Bobby, Barach, David Richard
• Primary Examiner(s): Vaughn; William
• Assistant Examiner(s): Ibrahim; Mohamed
• Application Number:
  US10/439,022
• Publication Number:
  US 20040230696A1
• Time in Patent Office: 1,720 Days
• Field of Search: 709/238, 709/245, 709/225, 709/228, 711205-206, 370351-356, 370/389, 370/392, 370/408
• US Class Current: 709/225
• 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/742 Route cache; Operation thereof
• 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: H04L 69/22 Parsing or analysis of headers

Abstract

The present invention provides a technique for efficiently looking up address-routing information in an intermediate network node, such as a router. To that end, the node locates routing information stored in its memory using one or more “lookup” tables (LUT) which can be searched using a small, bounded number of dependent lookups, thereby reducing the number of dependent lookups conventionally performed. The LUTs are arranged so each table provides routing information for network addresses whose subnet mask lengths are within a different range (“stride”) of mask lengths. According to the technique, the node locates a network address'"'"'s routing information by searching the LUTs, in order of decreasing prefix lengths, until the routing information is found. Preferably, several tables are searched in parallel. A match in a LUT may further point to a small MTRIE that enables the final bits of a prefix to be matched. That final MTRIE is searched using a relatively small, bounded number of dependent lookups.

Claims

1. A method for an intermediate network node to efficiently lookup routing information associated with a network address, the method comprising:

selecting a lookup table from a set of one or more lookup tables in the intermediate network node, each lookup table being associated with a different range of subnet mask lengths, wherein the selected lookup table is associated with the largest subnet mask lengths not yet searched;

searching the selected lookup table based on the value of the network address using a bounded number of dependent lookups to locate a memory location of the network address'"'"'s routing information;

if the network address is found in the selected lookup table, providing the memory location of the network address'"'"'s routing information from the selected lookup table;

if the network address is not found in the selected lookup table, then repeating the steps of selecting and searching the selected lookup table, until the memory location of the network address'"'"'s routing information is found or until all the lookup tables have been searched;

if the network address is found in any of the lookup tables, providing the memory location of the network address'"'"'s routing information from one of the lookup tables; and

if the network address is not found in any of the lookup tables, searching an MTRIE for the memory location of the network address'"'"'s routing information and providing the memory location of the network address'"'"'s routing information from the MTRIE.

2. The method according to claim 1, further comprising organizing each lookup table in the set of one or more lookup tables as a first-level hash table having a plurality of indexed hash lines, each indexed hash line associated with a corresponding second-level table configured to store a memory location of routing information for at least one network address.

3. The method according to claim 2, further comprising indexing a hash line in a first-level hash table based on the result of applying a first hash function to a first set of prefix bits in the network address.

4. The method according to claim 3, further comprising indexing a page in a second-level table based on the result of applying a second hash function to a second set of prefix bits in the network address.

5. The method according to claim 4, wherein the first and second hash functions are CRC32 hash functions.

6. The method according to claim 4, wherein the first and second set of prefix bits in the network address are the same prefix bits.

7. The method according to claim 2, further comprising storing, in the second-level tables, the location of routing information for network addresses in order of decreasing prefix length.

8. The method according to claim 2, wherein each hash line in a first-level hash table includes a valid bit, a hash-function identifier, a pointer to the hash line'"'"'s corresponding second-level table and a value indicating a number of pages which may be indexed in the hash line'"'"'s corresponding second-level table.

9. The method according to claim 1, further comprising:

receiving a data packet containing the network address at the intermediate network node; and

extracting the network address from the received data packet.

10. The method according to claim 1, wherein the step of searching the selected lookup table comprises searching selected lookup table in order of decreasing prefix lengths.

11. The method according to claim 1, wherein the network address is an IPv6 address.

12. An apparatus adapted to lookup routing information associated with a network address using a bounded number of dependent lookups, the apparatus comprising:

means for selecting a lookup table from a set of one or more lookup tables in the intermediate network node, each lookup table being associated with a different range of subnet mask lengths, wherein the selected lookup table is associated with the largest subnet mask lengths not yet searched;

means for searching the selected lookup table based on the value of the network address to locate a memory location of the network address'"'"'s routing information;

means for searching an MTRIE for the memory location of the network address'"'"'s routing information only if the network address is not found in any of the lookup tables; and

means for providing the memory location of the network address'"'"'s routing information.

13. The apparatus according to claim 12, further comprising:

means for receiving a data packet containing the network address at the intermediate network node; and

means for extracting the network address from the received data packet.

14. The apparatus according to claim 12, wherein the means for searching the selected lookup table further comprises means for searching the selected lookup table in order of decreasing prefix lengths.

15. A computer-readable media including instructions for execution by a processor, the instructions for a method of efficiently lookup routing information associated with a network address, the method comprising the steps:

selecting a lookup table from a set of one or more lookup tables in the intermediate network node, each lookup table being associated with a different range of subnet mask lengths, wherein the selected lookup table is associated with the largest subnet mask lengths not yet searched;

searching the selected lookup table based on the value of the network address using a bounded number of dependent lookups to locate a memory location of the network address'"'"'s routing information;

if the network address is found in the selected lookup table, providing the memory II location of the network address'"'"'s routing information from the selected lookup table;

if the network address is not found in the selected lookup table, then repeating the steps of selecting and searching the selected lookup table, until the memory location of 14 the network address'"'"'s routing information is found or until all the lookup tables have been searched;

if the network address is found in any of the lookup tables, providing the memory location of the network address'"'"'s routing information from one of the lookup tables; and

if the network address is not found in any of the lookup tables, searching an MTRIE for the memory location location of the network address'"'"'s routing information and providing the memory location of the network address'"'"'s routing information from the MTRIE.

16. An intermediate network node adapted to lookup routing information associated with a network address using a bounded number of dependent lookups, the node comprising:

a network interface for receiving a packet containing the network address;

a memory configured to store;

(a) at least one first-level hash table having a plurality of indexed hash lines, each indexed hash line associated with a corresponding second-level table configured to store a memory location of routing information for at least one network address, and

(b) at least one MTRIE configured to store a memory location of routing information for at least one network address; and

,

a forwarding engine including one or more processing elements configured to lookup the location of the network address'"'"'s associated routing information in the at least one first-level hash table, and only if the location of the network address'"'"'s associated routing information is not found, to lookup the location of the network address'"'"'s associated routing information in the at least one MTRIE.

17. The intermediate node according to claim 16, wherein a hash line in a first-level hash table is indexed based on the result of applying a first hash function to a first set of prefix bits in the network address.

18. The intermediate node according to claim 17, wherein a page in a second-level table is indexed based on the result of applying a second hash function to a second set of prefix bits in the network address.

19. The method according to claim 18, wherein the first and second set of prefix bits in the network address are the same prefix bits.

20. The intermediate node according to claim 16, wherein the second-level tables store the location of routing information for network addresses in order of decreasing prefix length.

21. The intermediate node according to claim 16, wherein each hash line in a first-level hash table includes a valid bit, a hash-function identifier, a pointer to the hash line'"'"'s corresponding second-level table and a value indicating a number of pages which may be indexed in the hash line'"'"'s corresponding second-level table.

22. The intermediate node according to claim 16, wherein the network address is an IPv6 address.