Request routing system using reinforcement learning
A DNS service routes network traffic based on a routing policy. A DNS routing policy generation system receives latency data corresponding to a plurality of different users, and a learning system learns the routing policy based on the latency data. In learning the routing policy, the learning system waits latency samples so that more recent latency samples are weighted more heavily than less recent latency samples.
1. A computer system, comprising:
at least one processor; and
a memory storing computer executable instructions which, when executed by the at least one processor, cause the at least one processor to perform steps comprising:
performing a learning operation to generate a routing policy based on a set of latency data indicative of latency, corresponding to service requests, encountered at client computing systems, the set of latency data including more recent latency data and less recent latency data, the set of latency data being weighted in the learning operation to obtain weighted latency data so higher weights are assigned to the more recent latency data and lower weights are assigned to the less recent latency data;
receiving a DNS request;
accessing the routing policy; and
serving the DNS request by returning an internet protocol (IP) address of a service endpoint based on the routing policy.
2. The computer system of claim 1 wherein performing a learning operation to generate a routing policy comprises:
performing the learning operation to generate the routing policy as a routing map that maps client computing systems to service endpoints.
3. The computer system of claim 2 wherein performing a learning operation comprises:
computing a model free reinforcement learning algorithm (Q-learning algorithm) using the weighted latency data, to obtain Q-values for each pair of client computing systems and service endpoints; and
generating the routing map based on the Q-values.
4. The computer system of claim 3 wherein the computer executable instructions, when executed by the at least one processor, cause the at least one processor to perform steps further comprising:
detecting deployment of a new service endpoint; and
computing the Q-learning algorithm for the new service endpoint.
5. The computer system of claim 4 wherein computing the Q-learning algorithm for the new service endpoint comprises:
identifying a threshold latency value based on latencies corresponding to service endpoints, other than the new service endpoint; and
setting an initial Q-value for the new service endpoint based on the threshold latency value.
6. The computer system of claim 5 wherein computing the Q-learning algorithm for the new service endpoint comprises:
computing the Q-learning algorithm using the initial Q-value set for the new service endpoint.
7. The computer system of claim 2 wherein the computer executable instructions, when executed by the at least one processor, cause the at least one processor to perform steps further comprising:
obtaining the set of latency data.
8. The computer system of claim 7 wherein obtaining the set of latency data comprises:
receiving latency samples indicative of latency encountered at the client computing systems; and
aggregating the latency samples to generate the set of latency data.
9. The computer system of claim 8 wherein aggregating the latency samples comprises:
scoping the latency samples based on a user scope to obtain scoped, aggregated latency samples; and
generating the set of latency data based on the scoped, aggregated latency samples.
10. The computer system of claim 1 wherein performing a learning operation comprises:
detecting a learning trigger; and
performing the learning operation based on the learning trigger.
11. The computer system of claim 10 wherein detecting a learning trigger comprises at least one of:
detecting the learning trigger based on a time-lapse since a last learning operation was performed; or
detecting the learning trigger based on a volume of latency data received since a last learning operation was performed.
12. A computer implemented method, comprising:
performing a learning operation to generate a routing policy based on a set of latency data indicative of latency, corresponding to service requests, encountered at client computing systems, the set of latency data including more recent latency data and less recent latency data, the set of latency data being weighted in the learning operation to obtain weighted latency data so higher weights are assigned to the more recent latency data and lower weights are assigned to the less recent latency data;
receiving a DNS request;
accessing the routing policy; and
serving the DNS request by returning an internet protocol (IP) address of a service endpoint based on the routing policy.
13. The computer implemented method of claim 12 wherein performing a learning operation to generate a routing policy comprises:
performing the learning operation to generate the routing policy as a routing map that maps client computing systems to service endpoints.
14. The computer implemented method of claim 13 wherein performing a learning operation comprises:
computing a model free reinforcement learning algorithm (Q-learning algorithm) using the weighted latency data, to obtain Q-values for each pair of client computing systems and service endpoints; and
generating the routing map based on the Q-values.
15. The computer implemented method of claim 14 and further comprising:
detecting deployment of a new service endpoint; and
computing the Q-learning algorithm for the new service endpoint.
16. The computer implemented method of claim 15 wherein computing the Q-learning algorithm for the new service endpoint comprises:
identifying a threshold latency value based on latencies corresponding to service endpoints, other than the new service endpoint; and
setting an initial Q-value for the new service endpoint based on the threshold latency value.
17. The computer implemented method of claim 16 wherein computing the Q-learning algorithm for the new service endpoint comprises:
computing the Q-learning algorithm using the initial Q-value set for the new service endpoint.
18. The computer implemented method of claim 17 further comprising:
receiving latency samples indicative of latency encountered at the client computing systems; and
aggregating the latency samples to generate the set of latency data.
19. A computer system, comprising
at least one processor; and
a memory storing computer executable instructions which, when executed by the at least one processor, cause the at least one processor to implement:
a learning system configured to perform a learning operation to generate a routing policy based on a set of latency data indicative of latency, corresponding to service requests, encountered at client computing systems, the set of latency data including more recent latency data and less recent latency data, the set of latency data being weighted in the learning operation to obtain weighted latency data so higher weights are assigned to the more recent latency data and lower weights are assigned to the less recent latency data; and
a router configured to receive a DNS request, access the routing policy, and serve the DNS request by returning an internet protocol (IP) address of a service endpoint based on the routing policy.
20. The computer system of claim 19 wherein the learning system is configured to perform the learning operation by computing a model free reinforcement learning algorithm (Q-learning algorithm) using the weighted latency data, to obtain Q-values for each pair of client computing systems and service endpoints, and generate, as the routing policy, a routing map based on the Q-values.