Tagging packets with a lookup key to facilitate usage of a unified packet forwarding cache

• US 7,269,663 B2
• Filed: 09/28/2001
• Issued: 09/11/2007
• Est. Priority Date: 09/28/2001
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Christensen, Jacob M., Beier, Niels, Egevang, Kjeld B.
• Primary Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US09/967,084
• Publication Number:
  US 20030065812A1
• Time in Patent Office: 2,174 Days
• Field of Search: 709/104, 709/212, 709/238, 709/214, 709/215, 709/245, 709/242, 711/113, 711/118, 711/3, 711/147, 711/213, 711/216, 711/221, 707/205
• US Class Current: 709/238
• 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/741 Routing in networks with a plurality of addressing schemes, e.g. with both IPv4 and IPv6
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/2503 Translation of Internet protocol [IP] addresses
• CPC Class Codes: H04L 67/288 Distributed intermediate devices, i.e. intermediate devices for interaction with other intermediate devices on the same level
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

Apparatus and methods are provided for a Network Address Translation (NAT)-aware unified cache. According to one embodiment, multiple packet-processing applications distributed among one or more processors of a network device share one or more unified caches without requiring a cache synchronization protocol. When a packet is received at the network device, a first packet-processing application, such as NAT or another application that modifies part of the packet header upon which a cache lookup key is based, tags the packet with a cache lookup key based upon the original contents of the packet header. Then, other packet-processing applications attempting to access the cache entry from the unified cache subsequent to the tagging by the first packet-processing application use the tag (the cache lookup key generated by the first packet-processing application) rather than determining the cache lookup key based upon the current contents of the packet header.

Claims

1. A method comprising:

receiving a packet at a network device, the packet including a header and a payload;

tagging the packet, by a first packet-processing application, with a cache lookup key based upon original contents of the header, the cache lookup key indicating where in a unified cache a cache entry corresponding to the packet will be stored, the cache lookup key being stored in a field of the unified cache, and the cache lookup key being part of a packet descriptor of the packet;

translating the header of the packet from the original contents by an address translation packet-processing application after tagging the packet;

forwarding the packet descriptor and the packet to a second packet processing application after translating the header; and

the second packet-processing application accessing the cache entry from the unified cache using the cache lookup key from the packet descriptor added by the first packet processing application, wherein the unified cache is shared by multiple packet forwarding processes and allows a flow to be classified once and then subsequent packets can be processed with a single lookup in the unified cache.

2. The method of claim 1, wherein said tagging the packet with a cache lookup key comprises populating a lookup key field of an internal packet descriptor corresponding to the packet with a hash value.

3. The method of claim 2, wherein the packet comprises an Internet Protocol (IP) packet and the cache lookup key is based upon a source IP address of the header, a destination IP address of the header, a source port of the header, a destination port of the header, and a protocol value in the header.

4. The method of claim 1, wherein the packet-processing applications includes applying one or more of Network Address Translation (NAT), packet filtering, and packet routing.

5. The method of claim 4, wherein the packet-processing applications are distributed among two or more processors of the network device.

6. The method of claim 1, wherein the first packet-processing application comprises a NAT process.

7. The method of claim 6, further comprising the second packet-processing application updating the cache entry with information specific to the second packet-processing application by using the cache lookup key to access the cache entry.

8. A method comprising the steps of:

a step for determining whether a cache lookup key is present in a packet descriptor associated with a received packet;

a step for performing a lookup in a unified cache with the cache lookup key if it is determined that the cache lookup key is present in the packet descriptor;

a step for creating a new cache entry in the unified cache based upon information in a header of the received packet and tagging the packet with a new cache lookup key if it is determined that the cache lookup key is not present in the packet descriptor or the lookup does not locate an appropriate existing cache entry, the new cache lookup key being based upon contents of the header of the packet;

a step for storing the new cache lookup key in a field of the unified cache;

a step for conveying the cache lookup key from a NAT packet-processing task to a packet filtering packet-processing task;

a step for updating an existing cache entry with module-specific information by the NAT packet processing task, the updating including translating the header of the packet; and

a step for accessing the new cache entry from the unified cache by the packet-filtering packet processing task using the cache lookup key, after translating the header, wherein the unified cache is shared by multiple packet forwarding processes and allows a flow to be classified once and then subsequent packets can be processed with a single lookup in the unified cache.

9. The method of claim 8, wherein the unified cache is implemented as a hash table and tagging the packet comprises generating a hash value based upon at least a source address and a destination address in the header and storing the hash value in the packet descriptor.

10. The method of claim 8, wherein the unified cache is utilized by a plurality of distributed packet-processing tasks including Network Address Translation (NAT), packet filtering, and packet forwarding.

11. A machine-readable medium having stored thereon data representing instructions that, if executed by one or more processors of a network device, cause the one or more processors to:

receive a packet including a header and a payload;

tag the packet, by a first packet-processing application of a plurality of packet-processing applications, with a cache lookup key based upon original contents of the header, the cache lookup key indicating where in a unified cache a cache entry corresponding to the packet will be stored;

the cache lookup key being stored in a field of the unified cache, and the cache lookup key being part of a packet descriptor of the packet;

translate the header of the packet from the original contents by an address translation packet-processing application after tagging the packet;

forward the packet descriptor and the packet to a second packet processing application after translating the header; and

use the cache lookup key from the packet descriptor rather than generating a new cache lookup key based upon current contents of the header by a second application accessing the cache entry from the unified cache subsequent to the tagging by the first packet-processing application, wherein the unified cache is shared by multiple packet forwarding processes and allows a flow to be classified once and then subsequent packets can be processed with a single lookup in the unified cache.

12. The machine-readable medium of claim 11, wherein tagging the packet with a cache lookup key comprises populating a lookup key field of an internal packet descriptor corresponding to the packet with a hash value.

13. The machine-readable medium of claim 11, wherein the packet comprises an Internet Protocol (IP) packet and the cache lookup key is based upon a source IP address of the header, a destination IP address of the header, a source port of the header, a destination port of the header, and a protocol value in the header.

14. The machine-readable medium of claim 11, wherein the plurality of packet-processing applications includes applying one or more of Network Address Translation (NAT), packet filtering, and packet routing.

15. The machine-readable medium of claim 11, wherein the plurality of packet-processing applications are distributed among at least two processors of the network device.

16. The machine-readable medium of claim 15, wherein the plurality of packet-processing applications include Network Address Translation (NAT), packet filtering, and packet forwarding.

17. The machine-readable medium of claim 11, wherein the first packet-processing application comprises a NAT process initiate the second packet-processing application of the plurality of packet-processing applications subsequent to the NAT process.

18. The machine-readable medium of claim 17, wherein the first packet-processing application comprises a NAT process that modifies the header of the packet, wherein the instructions further cause the one or more processors to:

access the cache entry, from the second packet-processing application, by using the cache lookup key; and

update the cache entry, by the second packet-processing application, with information specific to the second packet-processing application.

19. The machine-readable medium of claim 11, wherein the unified cache is implemented as a hash table and tagging the packet comprises generating a hash value based upon at least a source address and a destination address in the header and storing the hash value in the packet descriptor.

20. The machine-readable medium of claim 11, wherein the network device comprises a router.

21. The machine-readable medium of claim 11, wherein the network device comprises a switch.