Distributed lookup based on packet contents

• US 7,096,277 B2
• Filed: 08/07/2002
• Issued: 08/22/2006
• Est. Priority Date: 08/07/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hooper, Donald F.
• Primary Examiner(s): Tran, Philip B.
• Application Number:
  US10/214,984
• Publication Number:
  US 20040052254A1
• Time in Patent Office: 1,476 Days
• Field of Search: 709/238, 709/245, 709/213, 709/216, 709223-224, 370/389, 370/392, 370/395.32, 707/6, 707/10, 711/216
• US Class Current: 709/238
• CPC Class Codes: H04L 69/12 Protocol engines
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The disclosure includes description of a technique for use in looking-up data based on content of a packet received over a network. The technique includes receiving a lookup value based on the received packet, searching a first memory using at least a portion of the lookup value, and if the searching the first memory fails, searching a second memory, having a lower latency than the first memory, using at least a portion of the lookup value.

Claims

1. A method for use in looking-up data based on content of a packet received over a network, the method comprising:

receiving a lookup value based on the received packet;

searching a first memory using at least a portion of the lookup value;

if the searching the first memory fails, searching a second memory using at least a portion of the lookup value, the second memory having a lower latency than the first memory;

wherein the searching of the first memory and the second memory comprises searching a trie having different tiers; and

wherein the first memory stores index information corresponding to a first set of trie tiers and the second memory stores index information corresponding to a second set of trie tiers.

2. The method of claim 1, wherein the second memory comprises a memory provided by a different chip than the first memory.

3. The method of claim 2, wherein the second memory comprises a memory provided by a network processor.

4. The method of claim 3, wherein the network processor comprises more than one programmable packet processor.

5. The method of claim 4, wherein at least one of the more than one programmable packet processors comprise a processor having registers corresponding to different threads.

6. The method of claim 4, wherein the packet processor comprises a packet processor having an instruction set that does not feature floating point operation instructions.

7. The method of claim 1, further comprising, determining the lookup value.

8. The method of claim 7, wherein determining the lookup value comprises hashing at least a portion of data included in the packet'"'"'s header(s).

9. The method of claim 8, wherein the at least a portion of the packet header comprises the source address, destination address, source port, and destination port.

10. The method of claim 1, further comprising, retrieving data associated with the lookup value.

11. The method of claim 10, wherein the retrieving data comprises retrieving connection information for the packet.

12. The method of claim 11, wherein the connection information comprises at least an outgoing interface.

13. The method of claim 1, further comprising, distributing lookup information across the first and second memories.

14. The method of claim 1, wherein the searching the first memory comprises searching performed by a first processor and wherein the searching the second memory comprises searching performed by a second processor.

15. A computer program product, disposed on a computer readable storage medium, for use in looking-up data based on content of a packet received over a network, the program comprising instructions for causing a processor to:

receive a lookup value based on the received packet;

search a first memory using at least a portion of the lookup value;

if the search of the first memory fails, search a second memory using at least a portion of the lookup value, the second memory having a lower latency than the first memory; and

wherein the instructions for causing the processor to search the first and second memories comprise instructions for causing the processor to search a trie having different tiers, the first memory storing index information corresponding to a first set of trie tiers and the second memory storing index information corresponding to a second set of trie tiers.

16. The program of claim 15, wherein the second memory comprises a memory provided by a different chip than the first memory.

17. The program of claim 16, wherein the second memory comprises a memory provided by a network processor having more than one programmable packet processors.

18. The program of claim 15, wherein the lookup value comprises a hash of at least a portion of data included in the packet'"'"'s header(s).

19. The program of claim 15, further comprising, instructions for causing the processor to retrieve data associated with the lookup value.

20. The program of claim 19, wherein the instructions for causing the processor to retrieve data comprise instructions for causing the processor to retrieve connection information for the packet.

21. A system for looking-up data based on content of a packet received over a network, the system comprising:

at least one communication port;

at least one Ethernet MAC (Medium Access Control) device coupled to at least one of the at least one communication ports;

at least one processor having access to the at least one Ethernet MAC device and access to a first memory and a second memory, the second memory having a lower latency than the first memory;

instructions, disposed on a computer readable storage medium, for causing at least one of the at least one of the processors to;

receive a lookup value based on the received packet;

search the first memory using at least a portion of the lookup value;

if the search of the first memory fails, search a second memory using at least a portion of the lookup value;

wherein the instructions that cause the at least one processor to search comprise instructions that cause the at least one programmable packet processor to search a trie having different tiers; and

wherein the first memory stores index information corresponding to a first set of trie tiers and the second memory stores index information corresponding to a second set of trie tiers.

22. The system of claim 21, wherein the second memory comprises a memory provided by a different chip than the first memory and wherein the second memory comprises a memory provided by the same chip having the more than one programmable packet processors.

23. The system of claim 21, wherein the lookup value comprises a hash of at least a portion of data included in the packet'"'"'s header(s).

24. The system of claim 21, further comprising, instructions for causing the at least one processor to retrieve data associated with the lookup value.

25. The system of claim 24, wherein the data comprises connection information for the packet.