Methods of forwarding data packets using transient tables and related load balancers

• US 9,621,642 B2
• Filed: 06/17/2013
• Issued: 04/11/2017
• Est. Priority Date: 06/17/2013
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Ganesh, Jayasenan Sundara, Arisoylu, Mustafa, Anand, Prashant, Sawant, Nandan Mahadeo
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): Shitayewoldetadik, Berhanu
• Application Number:
  US13/919,388
• Publication Number:
  US 20140372567A1
• Time in Patent Office: 1,394 Days
• Field of Search: 709219, 709232, 709226, 709245, 709200, 709228, 707209, 707215, 707 7
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

Methods may be provided to forward data packets to a plurality of servers with each server being identified by a respective server identification (ID). A non-initial data packet of a data flow may be received, with the non-initial data packet including information for the data flow, and a bucket ID for the non-initial data packet may be computed as a function of the information for the data flow. Responsive to the bucket ID for the data packet mapping to first and second server identifications (IDs) of respective first and second servers and responsive to the non-initial data packet being a non-initial data packet for the data flow, the non-initial data packet may be transmitted to one of the first and second servers using one of the first and second server IDs based on a flow identification of the data flow being included in a transient table for the bucket ID.

Claims

1. A method of forwarding data packets to a plurality of servers with each server being identified by a respective server identification (ID), the method comprising:

receiving a non-initial data packet of a data flow wherein the non-initial data packet includes information for the data flow,

wherein the data flow is network traffic comprising a plurality of data packets transmitted from a client and forwarded over a network,

wherein an initial data packet of the data flow is a first data packet at a start of the data flow, and

wherein the non-initial data packet is a subsequent data packet in the data flow after the initial data packet;

computing a bucket ID for the non-initial data packet as a function of the information for the data flow; and

responsive to the bucket ID for the non-initial data packet mapping to first and second server ID of respective first and second servers and responsive to a determination that the non-initial data packet is a non-initial data packet for the data flow, transmitting the non-initial data packet to one of the first and second servers using one of the first and second server IDs based on a flow identification of the data flow being included in a transient table for the bucket ID,

wherein the transient table for the bucket ID is a list of data flows that are initiated while a bucket corresponding to the bucket ID is in a transient state initiated when a mapping of the bucket ID transitions from the first server to the second server.

2. The method of claim 1 further comprising:

before receiving the non-initial data packet, receiving the initial data packet of the data flow wherein the initial data packet of the data flow includes the information for the data flow;

computing the bucket ID for the initial data packet of the data flow as a function of the information for the data flow;

responsive to the bucket ID for the initial data packet mapping to first and second server ID of the respective first and second servers and responsive to the initial data packet being the initial data packet for the data flow, recording the flow identification for the data flow in the transient table for the bucket ID; and

responsive to the bucket ID for the initial data packet mapping to the first and second server IDs of the first and second servers and responsive to the initial data packet being the initial data packet for the data flow, transmitting the initial data packet to the first server using the first server ID.

3. The method of claim 2, wherein transmitting the non-initial data packet comprises transmitting the non-initial data packet to the first server using the first server ID responsive to the bucket ID for the non-initial data packet mapping to the first and second IDs of the first and second servers, responsive to the determination that the non-initial data packet is a non-initial data packet for the data flow, and responsive to the transient table for the bucket ID including the flow identification for the data flow.

4. The method of claim 3 wherein the non-initial data packet comprises a first non-initial data packet, and wherein the data flow comprises a first data flow, the method further comprising:

after receiving the first non-initial data packet of the first data flow, receiving a second non-initial data packet of a second data flow wherein the second non-initial data packet includes information for the second data flow;

computing the bucket ID for the second non-initial data packet as a function of the information for the second data flow; and

responsive to the bucket ID for the second non-initial data packet mapping to the first and second server IDs of the first and second servers, responsive to the second non-initial data packet being a non-initial data packet for the second data flow, and responsive to the transient table for the bucket ID omitting a flow identification for the second data flow, transmitting the second non-initial data packet to the second server using the second server ID.

5. The method of claim 4 further comprising:

before receiving the first and second non-initial data packets, defining a mapping table including a plurality of bucket IDs identifying a respective plurality of buckets, wherein the mapping table maps the first bucket ID to the first server ID for the first server as a current server ID for the first bucket ID, wherein the mapping table maps the first bucket ID to the second server ID for the second server as an old server ID for the first bucket ID, and wherein the mapping table maps the second bucket ID to only the third server ID for the third server as a current server ID for the third bucket ID.

6. The method of claim 5 further comprising:

after receiving the first non-initial data packet, revising the mapping table so that the mapping table maps the first bucket ID to only the first server ID for the first server as the current server ID for the first bucket ID without mapping the first bucket ID to the second server ID;

after receiving the first non-initial data packet, receiving a third non-initial data packet of the first data flow wherein the third non-initial data packet includes the information for the first data flow;

computing the first bucket ID for the third non-initial data packet as a function of the information for the first data flow; and

responsive to the bucket ID for the third non-initial data packet mapping only to the first server ID of the first server, transmitting the third non-initial data packet to the first server using the first server ID.

7. The method of claim 6 further comprising:

responsive to revising the mapping table, clearing the flow identification for the first data flow from the transient table for the first bucket ID.

8. The method of claim 5 wherein a number of the plurality of bucket IDs in the mapping table is greater than a number of the servers and server IDs, and wherein the mapping table provides a same server ID for more than one of the bucket IDs.

9. The method of claim 2 wherein the initial data packet comprises a first initial data packet, wherein the data flow comprises a first data flow, and wherein the bucket ID for the initial data packet comprises a first bucket ID, the method further comprising:

receiving a second initial data packet of a second data flow wherein the second initial data packet includes information for the second data flow;

computing a second bucket ID for the second initial data packet as a function of the information for the second data flow; and

responsive to the second bucket ID for the second initial data packet mapping to only a third server ID of a third server, transmitting the second initial data packet to the third server using the third server ID.

10. The method of claim 1 wherein the non-initial data packet comprises a first non-initial data packet, wherein the data flow comprises a first data flow, and wherein the bucket ID for the non-initial data packet comprises a first bucket ID, the method further comprising:

receiving a second non-initial data packet of a second data flow wherein the second non-initial data packet includes information for the second data flow;

computing a second bucket ID for the second non-initial data packet as a function of the information for the second data flow; and

responsive to the second bucket ID for the second non-initial data packet mapping to only a third server ID of a third server, transmitting the second non-initial data packet to the third server using the third server ID.

11. The method of claim 1 wherein the flow identification is derived from the information for the data flow, and wherein the bucket ID is derived from the flow identification via a hash function.

12. The method of claim 11 wherein the transient table for the bucket ID comprises a list of flow identifications for the data flows associated with the bucket ID which have been initiated when the bucket ID maps to the first and second server IDs.

13. A load balancer (LB) configured to forward data packets to a plurality of servers with each server being identified by a respective server identification (ID), the load balancer comprising:

a network interface configured to receive data packets from an outside network;

a server interface configured to forward data packets to the servers; and

a processor coupled to the network interface and the server interface, wherein the processor is configured to,

receive a non-initial data packet of a data flow through the network interface wherein the non-initial data packet includes information for the data flow,

wherein the data flow is network traffic comprising a plurality of data packets transmitted from a client and forwarded over a network,

wherein an initial data packet of the data flow is a first data packet at a start of the data flow, and

wherein the non-initial data packet is a subsequent data packet in the data flow after the initial data packet,

compute a bucket ID for the non-initial data packet as a function of the information for the data flow, and

transmit the non-initial data packet through the server interface to one of the first and second servers using one of the first and second server IDs based on a flow identification of the data flow being included in a transient table for the bucket ID responsive to the bucket ID for the non-initial data packet mapping to first and second server IDs of respective first and second servers and responsive to a determination that the non-initial data packet is a non-initial data packet for the data flow,

wherein the transient table for the bucket ID is a list of data flows that are initiated while a bucket corresponding to the bucket ID is in a transient state initiated when a mapping of the bucket ID transitions from the first server to the second server.

14. The load balancer of claim 13 wherein the processor is further configured to,

receive the initial data packet of the data flow through the network interface wherein the initial data packet of the data flow includes the information for the data flow before receiving the non-initial data packet,

compute the bucket ID for the initial data packet of the data flow as a function of the information for the data flow,

record a flow identification for the data flow in the transient table for the for the bucket ID responsive to the bucket ID for the initial data packet mapping to first and second server IDs of the respective first and second servers and responsive to the initial data packet being the initial data packet for the data flow, and

transmit the initial data packet through the server interface to the first server using the first server ID responsive to the bucket ID for the initial data packet mapping to the first and second server IDs of the first and second servers and responsive to the initial data packet being the initial data packet for the data flow.

15. The load balancer of claim 14, wherein the processor is configured to transmit the non-initial data packet by transmitting the non-initial data packet through the server interface to the first server using the first server ID responsive to the bucket ID for the non-initial data packet mapping to the first and second server IDs of the first and second servers, responsive to the determination that the non-initial data packet is a non-initial data packet for the data flow, and responsive to the transient table for the bucket ID including the flow identification for the data flow.

16. The load balancer of claim 15 wherein the non-initial data packet comprises a first non-initial data packet, and wherein the data flow comprises a first data flow, wherein the processor is further configured to,

receive a second non-initial data packet of a second data flow through the network interface after receiving the first non-initial data packet of the first data flow, wherein the second non-initial data packet includes information for the second data flow,

compute the bucket ID for the second non-initial data packet as a function of the information for the second data flow, and

transmit the second non-initial data packet through the server interface to the second server using the second server ID responsive to the bucket ID for the second non-initial data packet mapping to the first and second server IDs of the first and second servers, responsive to the second non-initial data packet being a non-initial data packet for the second data flow, and responsive to the transient table for the bucket ID omitting a flow identification for the second data flow.

17. The load balancer of claim 16 wherein the processor is further configured to,

define a mapping table before receiving the first and second non-initial data packets, wherein the mapping table includes a plurality of bucket IDs identifying a respective plurality of buckets, wherein the mapping table maps the first bucket ID to the first server ID for the first server as a current server ID for the first bucket ID, wherein the mapping table maps the first bucket ID to the second server ID for the second server as an old server ID for the first bucket ID, and wherein the mapping table maps the second bucket ID to only the third server ID for the third server as a current server ID for the third bucket ID.

18. The load balancer of claim 17 wherein the processor is further configured to,

revise the mapping table after receiving the first non-initial data packet so that the mapping table maps the first bucket ID to only the first server ID for the first server as the current server ID for the first bucket ID without mapping the first bucket ID to the second server ID,

receive a third non-initial data packet of a the first data flow through the network interface after receiving the first non-initial data packet, wherein the third non-initial data packet includes the information for the first data flow,

compute the first bucket ID for the third non-initial data packet as a function of the information for the first data flow, and

transmit the third non-initial data packet through the server interface to the first server using the first server ID responsive to the bucket ID for the third non-initial data packet mapping only to the first server ID of the first server.

19. The load balancer of claim 18 wherein the processor is further configured to,

clear the flow identification for the first data flow from the transient table for the first bucket ID responsive to revising the mapping table.

20. The load balancer of claim 17 wherein a number of the plurality of bucket IDs in the mapping table is greater than a number of the servers and server IDs, and wherein the mapping table provides a same server ID for more than one of the bucket IDs.

21. The load balancer of claim 14 wherein the initial data packet comprises a first initial data packet, wherein the data flow comprises a first data flow, and wherein the bucket ID for the initial data packet comprises a first bucket ID, wherein the processor is further configured to,

receive a second initial data packet of a second data flow through the network interface wherein the second initial data packet includes information for the second data flow,

compute a second bucket ID for the second initial data packet as a function of the information for the second data flow, and

transmit the second initial data packet through the server interface to the third server using the third server ID responsive to the second bucket ID for the second initial data packet mapping to only a third server ID of a third server.

22. The load balancer of claim 13 wherein the non-initial data packet comprises a first non-initial data packet, wherein the data flow comprises a first data flow, wherein the bucket ID for the non-initial data packet comprises a first bucket ID, and wherein the processor is further configured to,

receive a second non-initial data packet of a second data flow through the network interface wherein the second non-initial data packet includes information for the second data flow,

compute a second bucket ID for the second non-initial data packet as a function of the information for the second data flow, and

transmit the second non-initial data packet through the server interface to the third server using the third server ID responsive to the second bucket ID for the second non-initial data packet mapping to only a third server ID of a third server.

23. The load balancer of claim 13 wherein the flow identification is derived from the information for the data flow, and wherein the bucket ID is derived from the flow identification via a hash function.

24. The load balancer of claim 23 wherein the transient table for the bucket ID comprises a list of flow identifications for the data flows associated with the bucket ID which have been initiated when the bucket ID maps to the first and second server IDs.