Method providing server affinity and client stickiness in a server load balancing device without TCP termination and without keeping flow states

• US 7,047,315 B1
• Filed: 03/19/2002
• Issued: 05/16/2006
• Est. Priority Date: 03/19/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Srivastava, Sunil K.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): MADAMBA, GLENFORD J
• Application Number:
  US10/102,287
• Time in Patent Office: 1,519 Days
• Field of Search: 709/238, 709/236, 709/105, 709/201, 370/236
• US Class Current: 709/238
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1021 based on client or server locations

Abstract

A method of routing data from a client through one or more load-balancing routers to a selected load-balanced server among a plurality of servers in a network involves: receiving, at a load balancing node in a path from the client to the plurality of servers, a first packet of a request from a client; creating and storing a mapping of flow identifying information, associated with the first packet, to a client stickiness identifier; pushing the client stickiness label into a sending path list that is stored in association with the first packet; storing the client stickiness label in a mapping of client stickiness labels to server identifiers at a last load balancing node associated with the plurality of servers, wherein the mapping associates the client stickiness label with a server identifier that uniquely identifies a selected server that has been selected from among the plurality of servers to receive the client request; and forwarding all subsequent packets associated with the client request to the same selected server based on looking up the client stickiness label of such subsequent packets in the mapping. As a result, packet flows are rapidly routed from the same client to the same server without time-consuming hop-by-hop routing decisions or repeated load-balancing decisions.

Claims

1. A method of routing data from a client through one or more load-balancing routers to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

receiving, at a load balancing node in a path from the client to the plurality of servers, a first packet of a request from a client;

creating and storing a mapping of flow identifying information, associated with the first packet, to a client stickiness label;

pushing the client stickiness label into a sending path list that is stored in association with the first packet;

storing the client stickiness label in a mapping of client stickiness labels to server identifiers at a last load balancing node associated with the plurality of servers, wherein the mapping associates the client stickiness label with a server identifier that uniquely identifies a selected server that has been selected from among the plurality of servers to receive the client request; and

forwarding all subsequent packets associated with the client request to the same selected server based on looking up the client stickiness label of such subsequent packets in the mapping.

2. A method as recited in claim 1, further comprising the steps of storing one or more identifiers of egress interfaces on which the packet arrives, in the sending path list, as the first packet of the client request is routed to the plurality of servers using hop-by-hop decisions.

3. A method as recited in claim 1, further comprising the steps of:

pushing the client stickiness label into a sending path list at a last load-balancing node associated with the plurality of servers, in response to receiving a first packet of the client request at the last node,

receiving one or more packets of a server response to the client request;

popping the client stickiness label from the return path at the last node in response to receiving packets of the server response at the last node, and

forwarding the packets of the server response to the client based on the client stickiness label.

4. A method as recited in claim 1, further comprising the steps of:

storing one or more identifiers of ingress interfaces on which the packet arrives, in a return path list, as the first packet of the client request is routed to the plurality of servers using hop-by-hop decisions;

pushing a client stickiness label into the return path list at a last load-balancing node associated with the plurality of servers, in response to receiving a first packet of the client request at the last node,

receiving one or more packets of a server response to the client request;

popping the client stickiness label from the return path at the last node in response to receiving packets of the server response at the last node, and

forwarding the packets of the server response to the client based on the client stickiness label.

5. A method as recited in claim 1, further comprising the step of setting a first flag value in the first packet of the client content request.

6. A method as recited in claim 1, further comprising the step of setting a first flag value in the first packet of the client content request, wherein the first flag value signals that all nodes should update the return path list.

7. A method as recited in claim 1, further comprising the step of setting a second flag value in each of the subsequent packets.

8. A method as recited in claim 7, wherein the second flag value instructs nodes to use the sending path list for routing the subsequent packets for server load balancing.

9. A method as recited in claim 5, wherein the first flag value signals that the packet contains the sending path list and comprises an IP-RECORD-ROUTE-OPTION-FOR-SLB flag value in a header of the first packet.

10. A method as recited in claim 7, wherein the second flag value instructs nodes to use the sending path list for routing the subsequent packets and comprises an IP-STRICT-ROUTE-OPTION-FOR-SLB flag value in a header of the subsequent packets.

11. A method as recited in claim 1, further comprising the step of selecting one of the servers to respond to the client request in response to receiving a first packet of a client request at a first load-balancing node in the network associated with the client.

12. A method as recited in claim 1, wherein the client stickiness label uniquely identifies an association of the client to the selected server.

13. A method as recited in claim 1, further comprising storing the send path list in a mapping at the last load balancing node when the packet reaches the last node, wherein the mapping comprises an association of send path lists and client identifying information.

14. A method as recited in claim 1, further comprising storing the send path list in a mapping at the last load balancing node when the packet reaches the last node, wherein the mapping comprises an association of send path lists and packet flow identifying information.

15. A method as recited in claim 1, further comprising the steps of storing one or more identifiers of ingress interfaces on which the first packet of the client request arrives, in a return path list, as the first packet of the client request is routed from a first load balancing node to the last load balancing node using hop-by-hop decisions, based on setting an IP-RECORD-ROUTE-OPTION-FOR-SLB flag value in the first packet of the client request.

16. A method as recited in claim 15, further comprising the steps of:

receiving one or more subsequent packets of the server reply;

setting an IP-STRICT-ROUTE-OPTION-FOR-SLB flag value in each of the subsequent packets of the server reply; and

forwarding the subsequent packets of the server reply to the client on a route that is defined only by the return path list and without hop-by-hop routing decisions.

17. A method as recited in claim 15, further comprising storing the return path list in a mapping at the first node when the packet reaches the first node, wherein the mapping comprises an association of return path lists and server identifiers.

18. A method as recited in claim 17, further comprising the steps of popping a server identifier from the send path list and forwarding the packet to the server on an IP address contained in the server identifier.

19. A method as recited in claim 17, further comprising the steps of popping a server identifier from the send path list, performing network address translation on the server identifier to determine where to forward the packet, and forwarding the packet to the server on an IP address determined by the network address translation.

20. A method as recited in claim 1, wherein the first node and last node are load-balancing routers that participate in the network as multicast nodes.

21. A method of routing data from a client through one or more content routers to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

creating and storing a label value at each of the content routers that indicates how to forward packets associated with requests from the client;

receiving a first packet of a client request at a first content router in the network between the client and the plurality of servers;

mapping flow identifying information associated with the first packet to a client stickiness identifier in a persistent mapping that is stored at the first content router;

inserting the client stickiness identifier in the first packet and all subsequent packets;

mapping the client stickiness identifier to the label value; and

fast switching the client request to a selected server based on the label value.

22. A method as recited in claim 21, wherein the steps of mapping and fast switching the client request further comprises the steps of:

attempting to locate the client stickiness identifier in the first packet and all subsequent packets, at the last content router between the client and the plurality of servers; and

when the client stickiness identifier is not located, generating a new client stickiness identifier and returning the new client stickiness identifier to the client.

23. A method as recited in claim 21, wherein the step of returning the new client stickiness identifier to the client comprises the step of returning the new client stickiness label to the client in a TCP SYN ACK packet.

24. A method as recited in claim 21, wherein the steps of mapping and fast switching the client request further comprises the steps of:

attempting to locate the client stickiness identifier in the first packet and all subsequent packets, at the last content router between the client and the plurality of servers;

when the client stickiness identifier is not located, generating a new client stickiness identifier and returning the new client stickiness identifier to the client; and

when the client stickiness identifier is located, mapping the client stickiness identifier to the label value and fast switching the client request to a selected server based on the label value.

25. A method as recited in claim 21, wherein the first packet is a TCP SYN packet, and wherein the step of inserting the client stickiness identifier in the first packet and all subsequent packets comprises the step of inserting the client stickiness identifier in the TCP SYN packet of the client request.

26. A method of routing data from a client through one or more content routers to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

creating and storing a label value at each of the content routers that indicates how to forward packets associated with requests from the client;

receiving a first packet of a client request at a first content router in the network between the client and the plurality of servers;

mapping flow identifying information associated with the first packet to the label value in a persistent mapping that is stored at the first content router;

fast switching the client request to a selected server based on the label value receiving one or more subsequent packets of the client request;

creating a two-level stack frame in each of the subsequent packets;

pushing the label value into a first level of the stack frame;

pushing a second label value into a second level of the stack frame, wherein the second label value identifies a path from a last content router in the network to a selected server among the plurality of servers; and

forwarding the packet to the selected server through a next content router in the network.

27. A method as recited in claim 26, wherein the stack frame is created exclusively for load balancing.

28. A method as recited in claim 26, further comprising the steps of:

storing a time-to-live value in the mapping in association with each of the label values, and discarding a label value from the mapping when its time-to-live value has expired.

29. A method as recited in claim 26, further comprising the steps of receiving a client stickiness identifier from the client as part of the first packet of the client request, and storing the client stickiness identifier as the label value.

30. A method as recited in claim 26, wherein the two-level stack frame is created as a two-level MPLS stack.

31. A method as recited in claim 26, wherein the two-level stack frame is created using an IP tunneling encapsulation.

32. A method as recited in claim 26, further comprising the step of storing the second label in a cookie at the client.

33. A method as recited in claim 26, further comprising the step of storing the second label in a cookie at the client and in a mapping, stored at the first content router, of cookies to labels.

34. A method of routing data from a client through one or more load-balancing routers to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

receiving, at a load balancing node in a path from the client to the plurality of servers, a first IP packet of a request from a client;

creating and storing a mapping of flow identifying information, associated with the first IP packet, to a client stickiness identifier and a return path list, at a last load balancing node associated with the plurality of servers, wherein the return path list identifies a path in the network from a selected server to the client;

storing the client stickiness identifier in a field of an IP header of the first IP packet; and

forwarding all subsequent server reply packets associated with the client request to the same client based on obtaining the client stickiness identifier from the IP header of client request packets and looking up the client stickiness identifier in the mapping.

38. A method as recited in claim 34, further comprising the steps of:

receiving a server reply request packet at a first load-balancing node in the network on a path from the client to the server;

extracting the client stickiness identifier from an IP header of the subsequent server reply packet;

looking up the client stickiness identifier value in the mapping; and

forwarding the subsequent server reply packet on an egress interface that is determined based on a label in the mapping corresponding to the client stickiness identifier.

39. A method as recited in claim 38, further comprising the steps of performing network address translation on the subsequent server reply packet at one or more logical layers, and forwarding the subsequent server reply packet to a rewritten destination IP address specified in the subsequent server reply packet.

35. A method of routing data from a client through one or more load-balancing routers to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

receiving, at a load balancing node in a path from the client to the plurality of servers, a first IP packet of a request from a client;

creating and storing a mapping of flow identifying information, associated with the first IP packet, to a unique server identifier and a send path list, at a last load balancing node associated with the plurality of servers, wherein the send path list identifies a path in the network from the client to a selected server;

storing the server identifier in a field of an IP header of the first IP packet; and

forwarding all subsequent IP packets associated with the client request to the same selected server based on obtaining the server identifier from the IP header of such packets and looking up the server identifier in the mapping.

36. A method as recited in claim 35, further comprising the steps of:

receiving a subsequent client request packet at the last load-balancing node in the network on a path from the client to the server;

extracting the server identifier value from an IP header of the subsequent client request packet;

looking up the server identifier value in the mapping; and

forwarding the subsequent client request packet on an egress interface that is determined based on a label in the mapping corresponding to the server identifier value.

37. A method as recited in claim 36, further comprising the steps of performing network address translation on the client request packet at one or more logical layers, and forwarding the client request packet to a rewritten destination IP address specified in the client request packet.

40. A method of routing data from a client through one or more load-balancing nodes to a selected load-balanced server among a plurality of servers in a network, the method comprising the steps of:

receiving, at a last load balancing node associated with a selected server among the plurality of servers, a first packet of the client request at the last node;

storing a client stickiness label in a cookie at the client in response to receiving the first packet of the client request at the last node;

storing one or more identifiers of ingress interfaces on which the packet arrives, in a send path list for server load balancing, as the first packet of the server reply is routed from the last load balancing node to the client using hop-by-hop decisions;

receiving one or more subsequent packets of the client request;

retrieving the client stickiness label from the cookie in response to receiving subsequent packets of the client request at the last node, and

forwarding the subsequent packets of the client request to the selected server based on the client stickiness label.

41. A method as recited in claim 40, wherein the cookie is created on the client exclusively for storing client stickiness labels relating to server load balancing.

42. A method as recited in claim 40, further comprising the step of forwarding the subsequent packets to the selected server only on a route that is defined by the send path list and without hop-by-hop routing decisions.

43. A method as recited in claim 40, further comprising the steps of:

terminating a first TCP connection associated with the client at the last node;

initiating a second TCP connection from the last node directed to and terminating at the selected server; and

TCP splicing the first TCP connection and the second TCP connection.

44. A computer-readable medium carrying one or more sequences of instructions for routing data from a client through one or more load-balancing nodes to a selected load-balanced server among a plurality of servers in a network, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

receiving, at a load balancing node in a path from the client to the plurality of servers, a first packet of a request from a client;

creating and storing a mapping of flow identifying information, associated with the first packet, to a client stickiness label;

pushing the client stickiness label into a sending path list that is stored in association with the first packet;

storing the client stickiness label in a mapping of client stickiness labels to server identifiers at a last load balancing node associated with the plurality of servers, wherein the mapping associates the client stickiness label with a server identifier that uniquely identifies a selected server that has been selected from among the plurality of servers to receive the client request; and

forwarding all subsequent packets associated with the client request to the same selected server based on looking up the client stickiness label of such subsequent packets in the mapping.

45. An apparatus for routing data from a client through one or more load-balancing nodes to a selected load-balanced server among a plurality of servers in a network, comprising:

means for receiving, at a last load balancing node associated with a selected server among the plurality of servers, a first packet of a server reply to a request from a client;

means for storing one or more identifiers of ingress interfaces on which the packet arrives, in a send path list, as the first packet of the server reply is routed from the selected server to the client using hop-by-hop decisions;

means for setting a first flag value in the first packet of the server reply;

means for receiving one or more subsequent packets of the client request;

means for setting a second flag value in each of the subsequent packets; and

means for forwarding the subsequent packets to the selected server on a route that is defined by the send path list and without hop-by-hop routing decisions.

46. A load-balancing router, comprising:

a network interface that is coupled to a data network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions for routing data from a client through one or more load-balancing nodes to a selected load-balanced server among a plurality of servers in a network and which, when executed by the processor, cause the processor to carry out the steps of;

receiving, at a last load balancing node associated with a selected server among the plurality of servers, a first packet of a server reply to a request from a client;

storing one or more identifiers of ingress interfaces on which the packet arrives, in a send path list, as the first packet of the server reply is routed from the selected server to the client using hop-by-hop decisions;

setting a first flag value in the first packet of the server reply;

receiving one or more subsequent packets of the client request;

setting a second flag value in each of the subsequent packets; and

forwarding the subsequent packets to the selected server on a route that is defined by the send path list and without hop-by-hop routing decisions.