Method and apparatus for routing data to a load balanced server using MPLS packet labels

• US 6,856,991 B1
• Filed: 03/19/2002
• Issued: 02/15/2005
• Est. Priority Date: 03/19/2002
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Srivastava, Sunil K.
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Le, Debbie M.
• Application Number:
  US10/101,677
• Time in Patent Office: 1,064 Days
• Field of Search: 707 1- 3, 707/10, 707/104.1, 709/238, 709/236, 709/105, 709/201, 370/236
• US Class Current: 1/1
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• 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/1021 based on client or server locations
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

A method of routing data to a load-balanced server through a network having one or more load-balancing nodes is disclosed. The first packet of a client request is received at one of the load-balancing nodes, which stores information identifying a flow associated with the packet and an incoming interface identifier. The node then makes a server load-balancing decision and stores an outgoing interface identifier. When the packet reaches the last load-balancing node before the selected server, that last node also requests an MPLS label to uniquely identify the flow, connection and route. The label is stored in a mapping at the last node that associates the label with the flow and interface identifying information. The packet is routed to the selected server. The first server response packet is switched hop-by-hop and the MPLS label is stored at each node traversed by the response packets, in association with a flow identifier and incoming and outgoing interface identifiers. For all other packets in the request and response, nodes fast-switch the packets based on the label mappings. 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 to a selected load-balanced server among a plurality of servers in a network that comprises a plurality of load-balancing nodes, the method comprising the steps of:

receiving a first packet of a client request at one of the load-balancing nodes in the network;

storing information identifying a flow associated with the first packet, an identifier of an interface of that node on which the first packet arrived, and an outgoing interface identifier;

receiving a first packet of a server reply at a last node associated with a selected server among the plurality of servers;

receiving one or more subsequent packets of the client request;

receiving a label value;

storing the label value in a load balancing mapping at the last node that associates the label with the flow and interface identifying information; and

forwarding the subsequent packets to the selected server on a route that is defined by the load-balancing mapping and without hop-by-hop routing decisions.

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

routing a first server response packet from the server to the client on a hop-by-hop basis;

storing the label value at each node traversed by the response packets in a second load-balancing mapping that associates the label value with a flow identifier and the incoming and outgoing interface identifiers; and

fast-switching all other packets in the request and response between the client and the server based on the second load-balancing mappings.

3. A method as recited in claim 2, wherein the step of fast-switching all other packets in the request and response comprises the steps of fast-switching all other packets in the request and response between the client and the server based on the second load-balancing mappings without performing hop-by-hop routing decisions and without performing repeated load-balancing decisions.

4. A method as recited in claim 1, wherein the label value is selected to uniquely identify the flow associated with the first packet and a connection and route associated with the first packet.

5. A method as recited in claim 1, wherein the label is generated and formatted according to multi-protocol label switching (MPLS) protocol.

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

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

receiving one or more subsequent packets of the server reply;

receiving an MPLS label value;

storing the MPLS label value in a load balancing mapping at the last node that associates the MPLS label value with the flow and interface identifying information; and

forwarding the subsequent packets of the server reply to the client on a route that is defined by the load-balancing mapping and without hop-by-hop routing decisions.

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

9. A method as recited in claim 1, further comprising the steps of 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, 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.

10. A method as recited in claim 1, further comprising the steps of distributing the label value from the last node to all other nodes using Cisco tag switching protocol.

11. A method as recited in claim 1, further comprising the steps of distributing the label value from the last node to all other nodes using one or more MPLS messages.

12. A method of routing data from a client to a selected load-balanced server among a plurality of servers in a network that comprises a plurality of load-balancing nodes, the method comprising the steps of:

receiving a first packet of a client request at one of the load-balancing nodes in the network;

performing a load-balancing decision to result in selecting one of the plurality of servers to receive the client request;

storing information identifying a flow associated with the first packet, an identifier of an interface of that node on which the first packet arrived, and an outgoing interface identifier;

receiving a first packet of a server reply at a last node associated with a selected server among the plurality of servers;

receiving one or more subsequent packets of the client request;

receiving an MPLS label value;

storing the MPLS label value in a load balancing mapping at the last node that associates the MPLS label with the flow and interface identifying information; and

forwarding the subsequent packets to the selected server on a route that is defined by the load-balancing mapping and without hop-by-hop routing decision.

13. A method as recited in claim 12, further comprising the steps of:

routing a first server response packet from the server to the client on a hop-by-hop basis;

storing the MPLS label value at each node traversed by the response packets in a second load-balancing mapping that associates the MPLS label value with a flow identifier and the incoming and outgoing interface identifiers; and

fast-switching all other packets in the request and response between the client and the server based on the second load-balancing mappings.

14. A method as recited in claim 13, wherein the step of fast-switching all other packets in the request and response comprises the steps of fast-switching all other packets in the request and response between the client and the server based on the second load-balancing mappings without performing hop-by-hop routing decisions and without performing repeated load-balancing decisions.

15. A method as recited in claim 12, wherein the MPLS label value is selected to uniquely identify the flow associated with the first packet and a connection and route associated with the first packet.

16. A method as recited in claim 12, further comprising the step of selecting one of a plurality of servers to respond to the client request in response to receiving the first packet of a client request at one of the load-balancing nodes in the network.

17. A method as recited in claim 12, wherein the first node and last node are load-balancing routers that participate in the network as Anycast nodes.

18. A method as recited in claim 12, further comprising the steps of 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, 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.

19. A method as recited in claim 12, further comprising the steps of distributing the MPLS label value from the last node to all other nodes using one or more MPLS messages.

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

receiving a first packet of a client request at one of the load-balancing nodes in the network;

storing information identifying a flow associated with the first packet, an identifier of an interface of that node on which the first packet arrived, and an outgoing interface identifier;

receiving a first packet of a server reply at a last node associated with a selected server among the plurality of servers;

receiving one or more subsequent packets of the client request;

receiving a label value;

storing the label value in a load balancing mapping at the last node that associates the label with the flow and interface identifying information; and

forwarding the subsequent packets to the selected server on a route that is defined by the load-balancing mapping and without hop-by-hop routing decisions.

21. An apparatus for routing data from a client to a selected load-balanced server among a plurality of servers in a network that comprises a plurality of load-balancing nodes, comprising:

means for receiving a first packet of a client request at one of the load-balancing nodes in the network;

means for storing information identifying a flow associated with the first packet, an identifier of an interface of that node on which the first packet arrived, and an outgoing interface identifier;

means for receiving a first packet of a server reply at a last node associated with a selected server among the plurality of servers;

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

means for receiving a label value;

means for storing the label value in a load balancing mapping at the last node that associates the label with the flow and interface identifying information; and

means for forwarding the subsequent packets to the selected server on a route that is defined by the load-balancing mapping and without hop-by-hop routing decisions.

22. A load-balancing router configured for routing data from a client to a selected load-balanced server among a plurality of servers in a network, comprising:

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

a processor;

one or more stored sequences of instructions which, when executed by the processor,

cause the processor to carry out the steps of;

receiving a first packet of a client request at one of the load-balancing nodes in the network;

storing information identifying a flow associated with the first packet, an identifier of an interface of that node on which the first packet arrived, and an outgoing interface identifier;

receiving a first packet of a server reply at a last node associated with a selected server among the plurality of servers;

receiving one or more subsequent packets of the client request;

receiving a label value;

storing the label value in a load balancing mapping at the last node that associates the label with the flow and interface identifying information; and

forwarding the subsequent packets to the selected server on a route that is defined by the load-balancing mapping and without hop-by-hop routing decisions.