Hierarchical hash method for performing forward route lookup
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 15, 16, 17)
-
-
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. - View Dependent Claims (9, 10, 12, 13, 14, 18)
-
-
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. - View Dependent Claims (19)
-
Specification