Method and apparatus providing highly scalable server load balancing

• US 7,512,702 B1
• Filed: 07/19/2002
• Issued: 03/31/2009
• 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: Tappan, Daniel C., Srivastava, Sunil K.
• Primary Examiner(s): Baturay; Alicia
• Application Number:
  US10/199,760
• Time in Patent Office: 2,447 Days
• Field of Search: 709238-240, 709/242, 370/236
• 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/38 Flow based routing
• 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

Abstract

A method and apparatus providing highly scalable server load balancing are disclosed. Data packets from a client are routed through one or more routers to a server load balancer, which is selected from among a plurality of server load balancers in a network. In response to receiving a request packet, a particular server site to process the client request is selected. A first path to a second router associated with the particular server site, and a second path to a server load-balancing device associated with the second router, are determined. A mapping of flow identifying information, associated with the packet, to a first label value that identifies the first path and to a second label value that identifies the second path, is created. The first label value and the second label value are stored in the packet. All subsequent packets associated with the client request are forwarded to the server load-balancing device based on looking up the first label value and second label value in the mapping. As a result, a network is scalable to process and load-balance numerous client requests, which are efficiently routed to the site, server load-balancer, and server that are handling the request.

Claims

1. A method of providing highly scalable network server load balancing, the method comprising the steps of:

receiving, at a first router in a path from a client to one or more server sites, a packet of a request from a client;

selecting a particular server site to process the client request;

determining a first path from the first router through a network to a second router associated with the particular server site, and a second path from the first router to a server load-balancing device associated with the second router;

creating and storing a mapping of flow identifying information, associated with the packet, to a first multi-protocol label switching (MPLS) label value that identifies the first path and to a second MPLS label value that identifies the second path;

storing the first MPLS label value and the second MPLS label value in the packet;

distributing the first and second MPLS label values to the network by attaching the first and second MPLS label values to a discovery request packet that is sent into the network by the first router;

forwarding all subsequent packets associated with the client request to the server load-balancing device based on looking up the first MPLS label value and second MPLS label value in the mapping, wherein the server load-balancing device does not terminate any TCP connections;

receiving a cookie containing server address information from the second router, wherein the server address information identifies a server that is managed by the load-balancing device; and

storing the server address information in the mapping of flow identifying information.

2. A method as recited in claim 1, further comprising the steps of performing a global server load-balancing decision to result in selecting a particular server site to process the client request.

3. A method as recited in claim 1, wherein the receiving step further comprises terminating a TCP connection of the client at the first router.

4. A method as recited in claim 1, wherein the determining step further comprises performing a local server load-balancing decision to select the load-balancing device from among a plurality of load-balancing devices that are associated with the second router.

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

selecting a particular server load balancing device that is associated with the second router of the particular server site from among a plurality of server load balancing devices in the particular server site;

storing, in the mapping of flow identifying information, the second MPLS label value that identifies a path from the first router to the selected server load balancing device.

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

receiving a cookie containing server address information from the second router;

storing the server address information in the mapping of flow identifying information.

7. A method as recited in claim 1, further comprising the steps of performing network address translation to result in determining a network address of a server that is managed by the load-balancing device.

8. A method as recited in claim 1, wherein the forwarding step further comprises the steps of:

receiving one or more subsequent packets associated with the client request at the second router;

extracting the first MPLS label value and second MPLS label value from the packets;

forwarding the packets to the server load-balancing device based on the first MPLS label value and second MPLS label value.

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

receiving a subsequent client request packet at the second router;

extracting a 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 MPLS label in the mapping corresponding to the server identifier value.

10. A computer-readable storage medium storing one or more sequences of instructions for providing highly scalable network server load balancing, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

receiving, at a first router in a path from a client to one or more server sites, a packet of a request from a client;

selecting a particular server site to process the client request;

determining a first path from the first router through a network to a second router associated with the particular server site, and a second path from the client to a server load-balancing device associated with the second router;

creating and storing a mapping of flow identifying information, associated with the packet, to a first multi-protocol label switching (MPLS) label value that identifies the first path and to a second MPLS label value that identifies the second path;

storing the first MPLS label value and the second MPLS label value in the packet;

distributing the first and second MPLS label values to the network by attaching the first and second MPLS label values to a discovery request packet that is sent into the network by the first router;

forwarding all subsequent packets associated with the client request to the server load-balancing device based on looking up the first MPLS label value and second MPLS label value in the mapping, wherein the server load-balancing device does not terminate any TCP connections;

receiving a cookie containing server address information from the second router, wherein the server address information identifies a server that is managed by the load-balancing device; and

storing the server address information in the mapping of flow identifying information.

11. An apparatus for providing highly scalable network server load balancing, comprising:

means for receiving, at a first router in a path from a client to one or more server sites, a packet of a request from a client;

means for selecting a particular server site to process the client request;

means for determining a first path from the first router through a network to a second router associated with the particular server site, and a second path from the client to a server load-balancing device associated with the second router;

means for creating and storing a mapping of flow identifying information, associated with the packet, to a first multi-protocol label switching (MPLS) label value that identifies the first path and to a second MPLS label value that identifies the second path;

means for storing the first MPLS label value and the second MPLS label value in the packet;

means for distributing the first and second MPLS label values to the network by attaching the first and second MPLS label values to a discovery request packet that is sent into the network by the first router;

means for forwarding all subsequent packets associated with the client request to the server load-balancing device based on looking up the first MPLS label value and second MPLS label value in the mapping, wherein the server load-balancing device does not terminate any TCP connections;

means for receiving a cookie containing server address information from the second router, wherein the server address information identifies a server that is managed by the load-balancing device; and

means for storing the server address information in the mapping of flow identifying information.

13. An apparatus as recited in claim 11, further comprising means for performing a global server load-balancing decision to result in selecting a particular server site to process the client request.

14. An apparatus as recited in claim 11, wherein the means for determining a first path further comprises means for performing a local server load-balancing decision to select the load-balancing device from among a plurality of load-balancing devices that are associated with the second router.

15. An apparatus as recited in claim 11, further comprising:

means for selecting a particular server load balancing device that is associated with the second router of the particular server site from among a plurality of server load balancing devices in the particular server site; and

means for storing, in the mapping of flow identifying information, the second MPLS label value that identifies a path from the first router to the selected server load balancing device.

16. An apparatus as recited in claim 11, further comprising:

means for receiving a cookie containing server address information from the second router; and

means for storing the server address information in the mapping of flow identifying information.

17. An apparatus as recited in claim 11, wherein the means for forwarding all subsequent packets further comprises:

means for receiving one or more subsequent packets associated with the client request at the second router;

means for extracting the first MPLS label value and second MPLS label value from the packets; and

means for forwarding the packets to the server load-balancing device based on the first MPLS label value and second MPLS label value.

12. A load-balancing router for providing highly scalable network server load balancing, 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 first router in a path from a client to one or more server sites, a packet of a request from a client;

selecting a particular server site to process the client request;

determining a first path from the first router through the network to a second router associated with the particular server site, and a second path from the client to a server load-balancing device associated with the second router;

creating and storing a mapping of flow identifying information, associated with the packet, to a first multi-protocol label switching (MPLS) label value that identifies the first path and to a second MPLS label value that identifies the second path;

storing the first MPLS label value and the second MPLS label value in the packet;

distributing the first and second MPLS label values to the network by attaching the first and second MPLS label values to a discovery request packet that is sent into the network by the first router;

forwarding all subsequent packets associated with the client request to the server load-balancing device based on looking up the first MPLS label value and second MPLS label value in the mapping, wherein the server load-balancing device does not terminate any TCP connections;

receiving a cookie containing server address information from the second router, wherein the server address information identifies a server that is managed by the load-balancing device; and

storing the server address information in the mapping of flow identifying information.

18. A load balancing router as recited in claim 12, wherein the sequences of instructions comprise further instructions which when executed by the one or more processors cause performing a global server load-balancing decision to result in selecting a particular server site to process the client request.

19. A load balancing router as recited in claim 12, wherein the step of determining a first path comprises performing a local server load-balancing decision to select the load-balancing device from among a plurality of load-balancing devices that are associated with the second router.

20. A load balancing router as recited in claim 12, wherein the sequences of instructions comprise further instructions which when executed by the one or more processors cause:

selecting a particular server load balancing device that is associated with the second router of the particular server site from among a plurality of server load balancing devices in the particular server site; and

storing, in the mapping of flow identifying information, the second MPLS label value that identifies a path from the first router to the selected server load balancing device.

21. A load balancing router as recited in claim 12, wherein the sequences of instructions comprise further instructions which when executed by the one or more processors cause:

receiving a cookie containing server address information from the second router; and

storing the server address information in the mapping of flow identifying information.

22. A load balancing router as recited in claim 12, wherein the step of forwarding all subsequent packets comprises:

receiving one or more subsequent packets associated with the client request at the second router;

extracting the first MPLS label value and second MPLS label value from the packets; and

forwarding the packets to the server load-balancing device based on the first MPLS label value and second MPLS label value.