Flow redirection employing state information

• US 8,218,561 B2
• Filed: 04/27/2009
• Issued: 07/10/2012
• Est. Priority Date: 04/27/2009
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Akhter, Aamer Saeed, Ramasamy, Arivu Mani, Aitken, Paul J., Gillott, Mark
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): HAMPTON, TARELL A
• Application Number:
  US12/430,312
• Publication Number:
  US 20100271964A1
• Time in Patent Office: 1,170 Days
• Field of Search: 370/419
• US Class Current: 370/419
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 67/563 Data redirection of data network streams

Abstract

In an example embodiment, there is disclosed an apparatus comprising a first interface configured to receive a packet from a client, a second interface configured to transmit the packet to a server, a third interface configured to communicate with at least one processing device, redirection module in communication with the first interface, the second interface and the third interface, and flow monitoring and state information module in communication with the first interface, the second interface, the third interface and the redirection module. Responsive to receipt of the packet on the first interface, the redirection module is operable to communicate with the flow monitoring and state information module whether state information exists for the packet, the state information comprising an address for a processing device. The redirection module is operable to route the packet to the processing device responsive to determining state information exists for the packet.

Claims

1. An apparatus, comprising:

a first interface configured to receive a packet associated with a first flow from a client in communication with the first interface;

a second interface configured to transmit the packet to a server in communication with the second interface;

a module configured to communicate with at least one processing device;

a redirection module in communication with the first interface, the second interface and the module configured to communicate with at least one processing device; and

a flow monitoring and state information module in communication with the first interface, the second interface, the module configured to communicate with at least one processing device, and the redirection module;

wherein responsive to receipt of the packet on the first interface, the redirection module is operable to communicate with the flow monitoring and state information module to determine whether state information exists for the packet, the state information comprising an address for a processing device;

wherein the redirection module is operable to employ a hashing algorithm employing a predetermined number of hash buckets, wherein the predetermined number of hash buckets are distributed among the at least one processing device;

wherein the redirection module employs the hashing algorithm to associate the first flow with a first hash bucket that is associated with a first of the at least one processing device;

wherein the redirection module reallocates the predetermined number of hash buckets responsive to determining a new processing device has been added to at the least one processing device, the first hash bucket being associated with the second of the at least one processing device responsive to the redirection module reallocating the predetermined number of hash buckets;

wherein the redirection module employs the hashing algorithm to associate a second flow with the first hash bucket after the first hash bucket has been reallocated to the second processing device; and

wherein the redirection module continues to associate the first flow with the first processing device, and the second flow is associated with the second processing device.

2. The apparatus set forth in claim 1, wherein the redirection module is operable to determine from a hash table an assigned processing device selected from the at least one processing device for the packet;

wherein the redirection module is operable to update the flow monitoring and state information module with the address for first processing device; and

wherein the redirection module is operable to route the packet to the first processing device.

3. The apparatus set forth in claim 2, wherein the address for the first processing device is a Media Access Control (MAC) address.

4. The apparatus set forth in claim 2, wherein the address for the first processing device is an Internet Protocol (IP) address.

5. The apparatus set forth in claim 1,

wherein the redirection module is operable to update the flow monitoring and state information module with the address for the first processing device;

and

wherein the redirection module is operable to route the packet to the first processing device.

6. The apparatus set forth in claim 1, wherein the redirection module is operable to update the flow monitoring and state information module responsive to reassigning an existing flow.

7. The apparatus set forth in claim 1, wherein the packet comprises data representative of a flow comprising a source address, a source port, a destination address and a destination port;

and

wherein the redirection module is operable to determine whether state information exists for the packet based on the data representative of the flow.

8. A method, comprising:

receiving a packet from a client belonging to a first flow;

determining whether state information exists for the first flow, the state information comprises an address for a processing device for the flow;

selecting a selected hash bucket for the first flow response to determining state information does not exist for the first flow, selecting the first flow comprises employing a hashing algorithm employing a predetermined number of hash buckets, wherein the predetermined number of hash buckets are distributed among a plurality of processing devices;

reallocating the predetermined number of hash buckets responsive to determining a processing device has been removed from the plurality of processing devices, wherein the selected hash bucket is associated with a second processing device responsive to reallocating the predetermined number of hash buckets;

associating a second flow with the second processing device associated with selected hash bucket after the selected hash bucket has been reallocated to the second processing device; and

wherein the first flow continues to be associated with the first processing device, and the second flow is associated with the second processing device.

9. The method according to claim 8, further comprising:

determining an address for a first processing device for the first flow,

storing the address with flow information for the first flow, and

routing the first packet to the processing device;

further comprising

receiving a subsequent packet for the first flow after determining an address for a processing device for the flow, the determining whether state information exists for the flow further comprises retrieving the previously determined address of the processing device responsive to determining state information exists for the flow, and the subsequent packet is redirected to the to the address of the first processing device.

10. The method according to claim 9, wherein the address for the first processing device is selected from the group consisting of a media access control (MAC) address and an internet protocol (IP) address.

11. An apparatus, comprising:

a first interface configured to receive a packet from a client;

a second interface configured to communicate with a server and at least one processing device;

a redirection module configured to communicate with the first interface; and

a flow monitoring and state information module configured to communicate with the first interface, and the redirection module;

wherein responsive to receipt of the packet associated with a first flow on the first interface, the redirection module is operable to communicate with the flow monitoring and state information module to determine whether state information exists for the packet, the state information comprising an address for a processing device; and

wherein the redirection module is operable to employ a hashing algorithm employing a predetermined number of hash buckets wherein the predetermined number of hash buckets are distributed among the at least one processing device;

wherein the redirection module employs the hashing algorithm to associate the first flow with a first hash bucket that is associated with a first of the at least one processing device;

wherein the redirection module reallocates the predetermined number of hash buckets responsive to determining a second processing device has been added to at the least one processing device, the first hash bucket being associated with the second of the at least one processing device responsive to the redirection module reallocating the predetermined number of hash buckets;

wherein the redirection module employs the hashing algorithm to associate a second flow with the first hash bucket after the first hash bucket has been reallocated to the second processing device; and

wherein the redirection module continues to associate the first flow with the first processing device, and the second flow is associated with the second processing device.

12. An apparatus, comprising:

a first interface configured to receive a packet from a client in communication with the first interface and is further configured to communicate with a plurality of processing devices in communication with the first interface;

a second interface configured to communicate with a server;

redirection module in communication with the first interface and the second interface; and

flow monitoring and state information module in communication with the first interface, the second interface, and the redirection module;

wherein responsive to receipt of a first packet associated with a first on the first interface, the redirection module is operable to communicate with the flow monitoring and state information module to determine whether state information exists for the first flow, the state information comprising an address for a processing device; and

wherein the redirection module is operable to employ a hashing algorithm a hashing algorithm employing a predetermined number of hash buckets, wherein the predetermined number of hash buckets are distributed among the plurality of processing devices responsive to determining state information does not exist for the first flow;

wherein the redirection module employs the hashing algorithm to associate the first flow with a first hash bucket that is associated with a first of the at least one processing device;

wherein the redirection module reallocates the predetermined number of hash buckets responsive to determining a processing device has been removed from the plurality of processing devices, the first hash bucket being associated with a second of the plurality of processing devices responsive to the redirection module reallocating the predetermined number of hash buckets;

wherein the redirection module employs the hashing algorithm to associate a second flow with the first hash bucket after the first hash bucket has been reallocated to the second processing device; and

wherein the redirection module continues to associate the first flow with the first processing device, and the second flow is associated with the second processing device.

13. Logic encoded in at least one non-transitory tangible media, and when executed operable to:

receive a first packet belonging to a first flow;

determine that state information does not exist for the flow responsive to receiving the first packet;

determine an address for selecting a first processing device from a plurality of processing devices for the flow, wherein determining the address employs a hashing algorithm that employs a predetermined number of hash buckets distributed among the plurality of processing devices, the first processing device being associated with a selected bucket selected from the predetermined number of hash buckets;

storing the address of the first processing device with the flow information, and routing the first packet to the processing device;

reallocate the predetermined number of hash buckets responsive to determining a second processing device has been added to at the plurality of processing devices, the selected hash bucket being associated with the second processing device responsive to reallocating the predetermined number of hash buckets;

receive a second packet for a first flow, the second packet being received after the first hash bucket has been reallocated;

determine that state information exists for the flow responsive to receiving the second packet;

redirect the second packet to the first packet processing device responsive to determining state information exists for the flow;

receive a packet associated with a second flow, after the first hash bucket has been reallocated to the second processing device, the second flow is not assigned a processing device; and

assign the second flow to the second processing device responsive to the hashing algorithm associating the second flow with the selected hash bucket.