Hierarchical hash method for performing forward route lookup

• US 7,483,430 B1
• Filed: 02/28/2003
• Issued: 01/27/2009
• Est. Priority Date: 02/28/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yuan, Felix, Li, Jian
• Primary Examiner(s): Moe; Aung S
• Assistant Examiner(s): Mered; Habte
• Application Number:
  US10/377,841
• Time in Patent Office: 2,160 Days
• Field of Search: 370/351, 370/395.31, 370/395.32, 370/389, 370/392, 370/395.7, 370/397, 370/399, 370/409, 370/475, 370/254, 370/255, 370/256, 711/216, 711/217, 711/200, 711/213, 711/211, 709/242
• US Class Current: 370/395.2
• 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

Abstract

A method for performing a lookup to support forwarding of IP packets in a router comprising a network processor and a route processor is disclosed. The method includes receiving a packet having an IP address containing a network prefix and dividing available network prefixes into groups. The longest prefix is identified and a lookup is performed using hash tables. The packet is forwarded if a match is found.

Claims

1. A method for performing a lookup to support forwarding of IP packets in a router comprising a network processor and a route processor, the method comprising:

receiving a packet containing a destination IP address at a device comprising a base hash table containing IP prefixes divided into prefix groups according to prefix length and quick hash tables each comprising the IP prefixes from two or more of said prefix groups and configured to identify one or more of said prefix groups to search in the base hash table;

performing a lookup for the IP address in the base hash table, said lookup comprising searching the prefix group containing the longest prefix, wherein performing said lookup comprises searching a first prefix group in the base hash table and if a match is not found in said first prefix group, searching one of the quick hash tables for the IP address to determine the next prefix group to search in the base hash table by identifying one or more prefix groups that do not need to be searched in the base hash table;

performing adjacency processing at the network processor if a match is found in one of the prefix groups; and

forwarding the packet from the network processor performing said lookup to a route processor for further processing if no match is found;

wherein the network processor comprises a plurality of microprocessors arranged to process data packets in parallel pipelines, and performing a lookup for the IP address comprises processing a data packet at one or more of said parallel pipelines and wherein the hash tables are located on two or more memory controllers and subsequent hash accesses are interleaved between memory controllers.

2. The method of claim 1 wherein an ICMP message is generated if no match is found.

3. The method of claim 1 further comprising converting odd length prefixes into even length prefixes.

4. The method of claim 1 wherein the prefix groups comprise only a 128-bit address group and 64-but and shorter address groups.

5. The method of claim 1 further comprising providing different hash seeds in hash computation.

6. The method of claim 5 further comprising selecting a hash seed from a plurality of hash seeds to minimize hash collision.

7. The method of claim 5 further comprising selecting a hash function from a plurality of hash functions to minimize hash collisions.

15. The method of claim 1 wherein the base hash table and the quick hash tables are arranged in a two-level hierarchy.

16. The method of claim 1 wherein the base hash table comprises prefixes hashed into one of said prefix groups.

17. The method of claim 1 wherein said first prefix group comprises longer prefixes than said next prefix group.

8. A system for performing a lookup to support forwarding of IP packets, the system comprising:

a route processor;

memory for storing a base hash table comprising IP prefixes divided into prefix groups according to prefix length and quick hash tables each comprising the IP prefixes from two or more of said prefix groups and configured to identify one or more of said prefix groups to search in the base hash table; and

a network processor operable to receive a packet containing a destination IP address, perform a lookup for the longest matching prefix in the base hash table by searching the prefix group containing the longest prefix, and forward the packet if a match is found in one of the prefix groups; and

wherein said lookup comprises searching a first prefix group in the base hash table and if a match is not found in said first prefix group, searching one of the quick hash tables to determine the next prefix group to search in the base hash table by identifying one or more prefix groups that do not need to be searched in the base hash table; and

wherein the network processor comprises a plurality of microprocessors arranged to process data packets in parallel pipelines, and said lookup for the IP address comprises processing a data packet at one or more of said parallel pipelines and wherein the hash tables are located on two or more memory controllers and subsequent hash accesses are interleaved between memory controllers.

9. The system of claim 8 wherein the memory comprises two hash tables, each table located on a separate memory controller.

10. The system of claim 8 wherein the packet received has a 128 bit address.

12. The system of claim 8 further comprising overflow buffers corresponding to hash lines in the base hash table and located in faster memory than the base hash table.

13. The system of claim 8 wherein the packet is an IPv6 packet.

14. The system of claim 8 wherein each of said prefix groups comprises a range of 4 bits.

18. The system of claim 8 wherein the microprocessors located in different parallel pipelines share memory resources.

11. An apparatus comprising:

a network processor configured for receiving a packet containing a destination IP address;

a base hash table containing IP prefixes divided into prefix groups according to prefix length and quick hash tables each comprising the IP prefixes from two or more of said prefix groups and configured to identify one or more of said prefix groups to search in the base hash table;

a computer-readable medium comprising instructions which, when executed by the network processor, cause the network processor to perform a lookup for a matching prefix in the base hash table, said lookup comprising searching the prefix group containing the longest prefix;

wherein said lookup comprises searching a first prefix group in the base hash table and if a match is not found in said first prefix group, searching one of the quick hash tables for the IP address to determine the next prefix group to search in the base hash table by identifying one or more prefix groups that do not need to be searched in the base hash table; and

forwarding the packet if a match is found in one of the prefix groups; and

a route processor configured to forward the packet if a match is not found by the network processor;

wherein the network processor comprises a plurality of microprocessors arranged to process data packets in parallel pipelines, and said lookup for the IP address comprises processing a data packet at one or more of said parallel pipelines and wherein the hash tables are located on two or more memory controllers and subsequent hash accesses are interleaved between memory controllers.

19. The apparatus of claim 11 wherein the prefix groups are four-bit groups.