Granted Patent B1

US 12,348,422 · App. 18/153,865 · Granted Jul 1, 2025

Inventors: Zhiyuan Yao (Île-de-France, FR); Yoann Desmouceaux (Paris, FR); Mark Townsley (San Francisco, CA)

Assignee: CISCO TECHNOLOGY, INC.

H04L47/125

Abstract

Claims (67)

1. A computer-implemented method of directing data traffic among computerized network devices connected over a data transmission network, comprising:

receiving a data request;

identifying application tasks that are currently underway at a plurality of network devices;

calculating a current processing speed of the plurality of network devices based at least in part on the application tasks;

receiving feedback data embedded in packet headers corresponding to data traffic flows, wherein the feedback data comprises an instant server load state score, the current processing speed and a time stamp associated with each of the plurality of network devices;

upon receipt of the feedback data, using the feedback data to calculate weights for each of the plurality of network devices, wherein the weights correspond to load states of each respective network device of the plurality of network devices at respective times during data traffic flows;

using a weighted sampling mechanism for selecting candidate devices from the-plurality of network devices;

tabulating a load state score for each of the candidate devices that are available to complete the data request, wherein the load state score for a respective candidate device is a function of a previous load state score, the current processing speed of the respective candidate device, and a time value corresponding to an elapsed amount of time since the load state score was last updated;

identifying a selected candidate device based at least in part on the tabulated load state scores to complete the data request; and

encapsulating an identifier for the selected candidate device in the packet headers, wherein the encapsulating comprises selecting a partition method from modulo or range division based, at least in part, on a transmission protocol of a respective data traffic flow of the data traffic flows.

2. The computer implemented method of claim 1 , further comprising identifying the selected candidate device based at least in part on a lowest load state score among the candidate devices.

3. The computer implemented method of claim 1 , wherein receiving the data request comprises receiving the data request at an application server on the network.

4. The computer implemented method of claim 1 , further comprising receiving the feedback data at a load balancer used to calculate the weights for the plurality of network devices.

5. The computer implemented method of claim 1 , wherein the feedback data is embedded in at least one of TCP SYN-ACK packets, QUIC Hello packets, DTLS Hello Response, higher bits of a TCP timestamp, a key option field of a Generic Routing Encapsulation header, or least significant bits of 1Pv6 addresses.

6. The computer implemented method of claim 1 , wherein the tabulating comprises evaluating a queue length at each of the candidate devices with the time value.

7. The computer implemented method of claim 1 , wherein the using comprises:

generating probabilities of use and aliases for each of the plurality of network devices, wherein the probabilities distribute packets to network devices with higher weights that correspond to lower load states;

tabulating index values, threshold values, and the aliases in an alias table;

associating the index values with the candidate devices;

determining a quantity of candidate devices that should be considered for completing the respective data request or data flow;

using the quantity as a number of respective hash functions applied to the packet for selecting respective index values within the alias table;

responsive to identifying a new task, associating a random number with each selected respective index value;

for each selected respective index value of the alias table, determining the respective threshold value;

providing either the index value or the alias to a score table by comparing the random number to the threshold for a respective index value; and

identifying a selected candidate device to complete the respective data traffic flow as the candidate device having the lowest load state score.

8. The computer implemented method of claim 1 , further comprising calculating the load state score based at least in part on a formula:

g ′=max(0, g−v (Time( )− t )),

where g′ is a new score, g is the previous load state score, vis the processing speed, and time ( ) is a function that returns a current timestamp and tis a previous timestamp.

9. The computer implemented method of claim 8 ,

wherein: if g is 0, then assign g′=0;

if g is not 0, then compute g′; and

if g′≤0, assign g′=0, and update score g to 0.

10. The computer implemented method of claim 1 , further comprising calculating the load state scores for each of the candidate devices once at initiation of the data traffic flow.

11. The computer implemented method of claim 8 , wherein the previous load state score (g) is calculated based at least in part on the application tasks.

12. The computer implemented method of claim 11 , wherein the previous load state score (g) is selected based at least in part on a variance threshold factor corresponding to a degree to which the application tasks on the respective network device vary in a time domain, wherein:

if the application tasks on a server side are lower than the variance threshold factor, in terms of workload, g can be defined as a current number of active connections; and

if the application tasks on the server side are greater than the variance threshold factor in terms of workload, g can be computed as a sum of expected remaining computations for CPU-bound applications or storage use for IO-bound applications.

13. The computer implemented method of claim 1 , wherein the current processing speed is calculated based at least in part on the application tasks as follows:

if the application tasks are CPU-bound, the current processing speed corresponds to provisioned CPU numbers of the respective network device;

if the application tasks is pure IO-bound, the current processing speed corresponds to provisioned throughput of the respective network device;

if the application tasks are profiled in computer memory at the respective network device, the current processing speed corresponds to a previously calculated score according for available resources at the respective network device; and

if the application tasks are profiled in computer memory at the respective network device, and the application tasks are profiled as complex, the current processing speed corresponds to a moving average of sampled processing times.

14. The computer implemented method of claim 11 , wherein sampled processing times comprise a time interval between outbound reply and the data request.

15. The computer implemented method of claim 1 , wherein:

for connection-id of QUIC connections, assigning connection-id rand ( ) k for a connection for server k (using modulo partition);

for an IPV6 header, predefine 20-bit flow label field for each respective network device by using a different range division based on ranges [k*2{circumflex over ( )}20/N, (k+1)*2{circumflex over ( )}20/N−1],

where N is a number of respective network devices of the plurality of network devices and k is an identifier for the selected candidate device; and

for highest bits of TCP timestamp options, encode the identifiers for each of the respective network devices.

16. The computer implemented method of claim 1 , further comprising, identifying the selected candidate device with a load balancer having a processor and computer memory storing software running the computer implemented method in P4 programming language.

17. A system for directing data traffic among computerized network devices connected over a data transmission network, comprising:

a first network device of a plurality of network devices connected to the data transmission network, the first network device having a computer processor, computer memory and software stored in the computer memory, the first network device configured to implement steps comprising:

receiving a data request;

identifying application tasks that are currently underway at the first network device;

calculating a current processing speed of the first network device based at least in part on the application tasks;

embedding feedback data in packet headers corresponding to data traffic flows from the first network device back to other network devices included in the plurality of network devices, wherein the feedback data comprises an instant server load state score, the current processing speed and a time stamp;

a second network device of the plurality of network devices connected to the data transmission network, the second network device comprising a respective computer processor, a respective computer memory and respective software stored in the respective computer memory, wherein the second network device is configured to implement respective steps comprising:

receiving the feedback data;

using the feedback data to calculate weights for respective network devices of the plurality of network devices, wherein the weights correspond to load states of each respective network device at respective times during the data traffic flows;

using a weighted sampling mechanism for randomly selecting candidate devices from the respective network devices;

tabulating a load state score for each of the candidate devices that are available to complete a respective data traffic flow, wherein the load state score for a respective candidate device is a function of a previous load state score for the respective candidate device, the current processing speed of the respective candidate device, and a time value corresponding to an elapsed amount of time since the load state score was last updated;

identifying a selected candidate device to complete a respective data traffic flow of the data traffic flows; and

encapsulating an identifier for the selected candidate device in the packet headers, wherein the encapsulating comprises selectin a partition method from modulo or range division based, at least in part, on a transmission protocol of a respective data traffic flow of the data traffic flows.

18. The system of claim 17 , wherein the current processing speed is calculated based at least in part on the application tasks as follows:

if the application tasks are CPU-bound, the current processing speed corresponds to provisioned CPU numbers of the first network device;

if the application tasks are pure IO-bound, the current processing speed corresponds to provisioned throughput of the first network device;

if the application tasks are profiled in the computer memory at the first network device, the current processing speed corresponds to a previously calculated score according for available resources at the first network device; and

if the application tasks are profiled in the computer memory at the first network device, and the application tasks are profiled as complex, the current processing speed corresponds to a moving average of sampled processing times.

Assignments (1)

References Cited (30)