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

• US 20030065812A1
• Filed: 09/28/2001
• Published: 04/03/2003
• Est. Priority Date: 09/28/2001
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Christensen, Jacob M., Beier, Niels, Egevang, Kjeld B.
• Granted Patent: US 7,269,663 B2
• Time in Patent Office: Days
• US Class Current: 709/236
• 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 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; and

those of the plurality of packet-processing applications attempting to access the cache entry from the unified cache subsequent to the tagging by the first packet-processing application using the cache lookup key rather than generating a new cache lookup key based upon current contents of the header.

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 plurality of 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 plurality of 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 that modifies the header of the packet, and wherein the method further comprises the NAT process initiating a second packet-processing application of the plurality of packet-processing applications and providing the tagged packet to the second packet-processing application.

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 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; and

a step for updating an existing cache entry with module-specific information.

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. The method of claim 8, a step for conveying the cache lookup key from the NAT packet-processing task to the packet filtering packet-processing task.

12. A network device comprising:

a plurality of incoming interfaces upon which Internet Protocol (IP) packets are received;

a plurality of unified caches, each unified cache of the plurality of unified caches associated with a corresponding incoming interface of the plurality of incoming interfaces;

a Network Address Translation (NAT) module coupled to each of the plurality of interfaces and to each of the plurality of unified caches to translate one or more addresses in headers of received IP packets in accordance with a plurality of NAT rules stored in a NAT rule table, tag the received IP packets with cache lookup keys for the unified cache associated with the incoming interface upon which they are received, and insert new cache entries into the unified caches as new packet flows are detected;

a filtering module coupled to each of the plurality of unified caches and to the NAT module to receive tagged IP packets from the NAT module, perform packet filtering in accordance with a plurality of filtering rules stored in a filter rule table, and to access and update existing cache entries in the unified caches using the cache lookup keys added by the NAT module; and

a forwarding module coupled to each of the plurality of unified caches and to the filtering module to receive tagged IP packets from the filtering module, perform packet forwarding in accordance with a plurality of forwarding rules stored in a routing table, and to access and update existing cache entries in the unified caches using the cache lookup keys added by the NAT module.

13. The network device of claim 12, wherein the network device is a router.

14. The network device of claim 12, wherein the network device is a switch.

15. The network device of claim 12, wherein the NAT module, the filtering module, and the forwarding module are distributed among a plurality of processors.

16. The network device of claim 15, wherein the NAT module, the filtering module, and the forwarding module operate in the absence of a cache synchronization protocol by performing lookups in the plurality of unified caches using cache lookup keys stored within internal packet descriptors associated with the received IP packets.

17. A network device comprising:

a plurality of incoming interface means upon which Internet Protocol (IP) packets are received;

a plurality of unified cache means, each associated with a corresponding incoming interface of the plurality of incoming interfaces, for storing recently used packet forwarding information;

a Network Address Translation (NAT) means, coupled to each of the plurality of interface means and to each of the plurality of unified cache means, for translating one or more addresses in headers of received IP packets in accordance with a plurality of NAT rules stored in a NAT rule table, tagging the received IP packets with cache lookup keys for the unified cache means associated with the incoming interface means upon which they are received, and inserting new cache entries into the unified cache means as new packet flows are detected;

a packet filtering means, coupled to each of the plurality of unified cache means and to the NAT means, for receiving tagged IP packets from the NAT means, performing packet filtering in accordance with a plurality of filtering rules stored in a filter rule table, and for accessing and updating existing cache entries in the unified cache means using the cache lookup keys added by the NAT means; and

a packet forwarding means, coupled to each of the plurality of unified cache means and to the packet filtering means, for receiving tagged IP packets from the packet filtering means, performing packet forwarding in accordance with a plurality of forwarding rules stored in a routing table, and for accessing and updating existing cache entries in the unified cache means using the cache lookup keys added by the NAT means.

18. The network device of claim 17, wherein the network device is a router.

19. The network device of claim 17, wherein the network device is a switch.

20. The network device of claim 17, wherein the NAT means, the packet filtering means, and the packet forwarding means are distributed among a plurality of processors.

21. The network device of claim 20, wherein the NAT means, the packet filtering means, and the packet forwarding means operate in the absence of a cache synchronization protocol by performing lookups in the plurality of unified cache means using cache lookup keys stored within internal packet descriptors associated with the received IP packets.

22. 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; and

use the cache lookup key rather than generating a new cache lookup key based upon current contents of the header by those of the plurality of packet-processing applications attempting to access the cache entry from the unified cache subsequent to the tagging by the first packet-processing application.

23. The machine-readable medium of claim 22, 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.

24. The machine-readable medium of claim 22, 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.

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

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

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

28. The machine-readable medium of claim 22, 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:

provide the tagged packet to a second packet-processing application of the plurality of packet-processing applications; and

initiate the second packet-processing application of the plurality of packet-processing applications subsequent to the NAT process.

29. The machine-readable medium of claim 28, 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.

30. The machine-readable medium of claim 22, 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.

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

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