Efficient IP load-balancing traffic distribution using ternary CAMs

• US 7,062,571 B1
• Filed: 06/30/2000
• Issued: 06/13/2006
• Est. Priority Date: 06/30/2000
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cieslak, Martin, Dale, Lincoln
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Assistant Examiner(s): STRANGE, AARON N
• Application Number:
  US09/608,548
• Time in Patent Office: 2,174 Days
• Field of Search: 709238-242, 709226-229, 709/105, 709/219, 711/108, 718/105
• US Class Current: 709/239
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1012 based on compliance of requirements or conditions with available server resources
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1036 Load balancing of requests to servers for services different from user content provisioning, e.g. load balancing across domain name servers
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context
• CPC Class Codes: H04L 69/12 Protocol engines

Abstract

Disclosed is an apparatus and method for distributing traffic to one or more selected cache systems or servers. In general terms, a content addressable memory (e.g., a TCAM) is utilized to distribute traffic among a plurality of cache systems or servers. The content addressable memory is populated with a plurality of entries. Each entry within the content addressable memory generally indicates an action to be performed on a packet, such as to redirect the packet or to forward the packet to its original destination. When the action indicated by the content addressable memory is to redirect the packet, the content addressable memory also indicates where (e.g., to which cache system) to redirect the packet.

Claims

1. A method of distributing packets among a plurality of cache systems, the method comprising:

configuring a content addressable memory (CAM) to indicate distribution of received packets based on a load balancing technique to a plurality of cache systems that each spoof a destination indicated by the received packets;

receiving a packet;

inputting at least a portion of the packet into CAM; and

obtaining a result from the CAM to indicate whether to redirect the received packet to a selected cache system and to indicate to which cache system selected from among the plurality of cache systems the received packet is to be redirected if the CAM also indicates that the received packet is to be redirected;

redirecting the received packet to the selected cache system when the CAM indicates to redirect the received packet; and

sending the received packet to a destination indicated by the received packet when the CAM does not indicate to redirect the received packet.

2. A method as recited in claim 1, wherein the result indicates to redirect the packet from being sent to a destination specified in the received packet.

3. A method as recited in claim 2, wherein the result includes a cache system device identification corresponding to the selected device to which the received packet is to be sent.

4. A method as recited in claim 1, wherein the content addressable memory is a ternary content addressable memory.

5. A method as recited in claim 1, wherein the portion(s) of the received packet input into the content addressable memory is selected from a group consisting of a destination address, a destination port, a source address, a source port, and a protocol.

6. A method as recited in claim 1, wherein the TCAM includes a plurality of entries, and each entry includes a bits-to-match field, an action field, and a redirection destination field.

7. A method as recited in claim 6, wherein the redirection destination field identifies a cache system.

8. A method as recited in claim 7, wherein the action field indicates whether the received packet is to be redirected.

9. A method for facilitating traffic distribution among a plurality of devices, the method comprising generating a plurality of entries within a content addressable memory, each entry including a set of bit values that correspond to at least a portion of a packet and each entry including one or more destination fields indicating where to send a packet that matches the entry'"'"'s set of bit values and indicating whether to redirect the packet from a destination indicated by the packet, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique.

10. A method as recited in claim 9, wherein the destination fields include an action field indicating whether to redirect the packet from a destination indicated by the packet itself.

11. A method as recited in claim 10, wherein the destination fields include a destination identifier indicating a device to which the packet is to be redirected.

12. A method as recited in claim 9, wherein the set of bits values include at least a 1 or a 0 value and a “

don'"'"'t care”

value.

13. A method as recited in claim 9, wherein the content addressable memory is ternary.

14. A computer system operable to distribute packets among a plurality of cache systems, comprising:

a first memory;

a content addressable memory; and

a processor coupled to the first memory and the content addressable memory,

wherein at least one of the first memory and the processor are adapted to provide;

configuring a content addressable memory (CAM) to indicate distribution of received packets based on a load balancing technique to a plurality of cache systems that each spoof a destination indicated by the received packets;

receiving a packet;

inputting at least a portion of the packet into the content addressable memory; and

obtaining result from the content addressable memory (CAM) to indicate whether to redirect the received packet to a selected cache system and to indicate to which cache system selected from among the plurality of cache systems the received packet is to be redirected if the CAM also indicates that the received packet is to be redirected, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique;

redirecting the received packet to the selected cache system when the CAM indicates to redirect the received packet; and

sending the received packet to a destination indicated by the received packet when the CAM does not indicate to redirect the received packet.

15. A computer system as recited in claim 14, wherein the result indicates to redirect the packet from being sent to a destination specified in the received packet.

16. A computer system as recited in claim 15, wherein the result includes a cache system identification corresponding to the selected cache system to which the received packet is to be sent.

17. A computer system as recited in claim 14, wherein the content addressable memory is a ternary content addressable memory.

18. A computer system as recited in claim 14, wherein the at least a portion of the received packet is selected from a group consist of a destination address, a destination port, a source address, a source port, and a protocol.

19. A computer system as recited in claim 14, wherein the content addressable memory includes a plurality of entries, and each entry includes a bits-to-match field, an action field, and a redirection destination field.

20. A computer system as recited in claim 19, wherein the redirection destination field identifies a cache system.

21. A computer system as recited in claim 20, wherein the action field indicates whether the received packet is to be redirected.

22. A computer system operable to facilitate traffic distribution among a plurality of cache systems, comprising:

a first memory;

a content addressable memory; and

a processor coupled to the first memory and the content addressable memory (CAM),

wherein at least one of the first memory and the processor are adapted to provide generating a plurality of entries within the content addressable memory, each entry including a set of bit values that correspond to at least a portion of a packet and each entry including one or more destination fields indicating where to send a packet that matches the entry'"'"'s set of bit values and indicating whether to redirect the packet from a destination indicated by the packet, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique.

23. A computer system as recited in claim 22, wherein the destination fields include an action field indicating whether to redirect the packet from a destination indicated by the packet itself.

24. A computer system as recited in claim 23, wherein the destination fields include a destination identifier indicating a cache system to which the packet is to be redirected.

25. A computer system as recited in claim 22, wherein the set of bits values include at least a 1 or a 0 value and a “

don'"'"'t care”

value.

26. A computer system as recited in claim 22, wherein the content addressable memory is ternary.

27. A computer program product for distributing traffic, the computer program product comprising:

at least one computer readable medium;

computer program instructions stored within the at least one computer readable product configured to cause a cache system to;

configure a content addressable memory (CAM) to indicate distribution of received packets based on a load balancing technique to a plurality of cache systems that each spoof a destination indicated by the received packets;

receive a packet;

input at least a portion of the packet into a content addressable memory; and

obtain a result from the content addressable memory (CAM) to indicate whether to redirect the received packet to a selected cache system and to indicate to which cache system selected from among the plurality of cache systems the received packet is to be redirected if the CAM also indicates that the received packet is to be redirected, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique;

redirect the received packet to the selected cache system when the CAM indicates to redirect the received packet; and

send the received packet to a destination indicated by the received packet when the CAM does not indicate to redirect the received packet.

31. A computer program as recited in claim 27, wherein the result indicates to redirect the packet from being sent to a destination specified in the received packet.

32. A computer program as recited in claim 31, wherein the result includes a cache system identification corresponding to the selected cache system to which the received packet is to be sent.

33. A computer program as recited in claim 27, wherein the content addressable memory is a ternary content addressable memory.

34. A computer program as recited in claim 27, wherein the portion(s) of the received packet input into the content addressable memory is selected from a group consisting of a destination address, a destination port, a source address, a source port, and a protocol.

35. A computer program as recited in claim 27, wherein the TCAM includes a plurality of entries, and each entry includes a bits-to-match field, an action field, and a redirection destination field.

36. A computer program as recited in claim 35, wherein the redirection destination field identifies a cache system.

37. A computer program as recited in claim 36, wherein the action field indicates whether the received packet is to be redirected.

28. A computer program product for distributing traffic, the computer program product comprising:

at least one computer readable medium;

computer program instructions stored within the at least one computer readable product configured to generate a plurality of entries within a content addressable memory, each entry including a set of bit values that correspond to at least a portion of a packet and each entry including one or more destination fields indicating where to send a packet that matches the entry'"'"'s set of bit values and indicating whether to redirect the packet from a destination indicated by the packet, wherein the CAM is configured to distribute received packets to a plurality of devices based on a load balancing technique.

29. An apparatus for distributing traffic comprising:

a means for configuring a content addressable memory (CAM) to indicate distribution of received packets based on a load balancing technique to a plurality of cache systems that each spoof a destination indicated by the received packets;

a means for receiving a packet;

a means for inputting at least a portion of the packet into a content addressable memory; and

a means for obtaining a result from the content addressable memory to indicate whether to redirect the received packet to a selected cache system or to forward the received packet to a destination specified by the received packet and to indicate to which cache system selected from among the plurality of cache systems the received packet is to be redirected if the CAM also indicates that the received packet is to be redirected, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique; and

a means for sending the received packet to the indicated cache system.

30. An apparatus for distributing traffic comprising a means for generating plurality of entries within a content addressable memory, each entry including a set of bit values that correspond to at least a portion of a packet and each entry including one or more destination fields indicating where to send a packet that matches the entry'"'"'s set of bit values and indicating whether to redirect the packet from a destination indicated by the packet, wherein the CAM is configured to distribute received packets to the plurality of cache systems based on a load balancing technique.