초록 ▼

Example embodiments are directed to methods of routing requests within a system having a plurality of server pools. At least one of the methods provides a method of routing requests within a system having a plurality of server pools. The method includes receiving a request at the system, first deter

Example embodiments are directed to methods of routing requests within a system having a plurality of server pools. At least one of the methods provides a method of routing requests within a system having a plurality of server pools. The method includes receiving a request at the system, first determining a first value associated with a first request type of the received request and second determining a probability of routing based on the first value and a probability of rerouting. The first value is a virtual queue value for requests of the first request type. The second determining is performed without determining an input rate at which the requests of the first request type are received. The received request is routed to at least one of the plurality of server pools based on the probability of routing.

대표청구항 ▼

1. A method of routing requests within a system having a plurality of server pools, the method comprising: receiving a request at the system;first determining a first value associated with a first request type of the received request, the first value modeling a number of requests of the first reques

1. A method of routing requests within a system having a plurality of server pools, the method comprising: receiving a request at the system;first determining a first value associated with a first request type of the received request, the first value modeling a number of requests of the first request type in a virtual queue;second determining probabilities of routing based on the first value and probabilities of rerouting for further processing, the second determining being performed without determining an input rate of received requests of the first request type; androuting the received request to at least one of the plurality of server pools based on the probabilities of routing. 2. The method of claim 1, wherein the first determining includes, increasing the first value. 3. The method of claim 1, wherein the second determining includes, updating the first value periodically. 4. The method of claim 3, wherein the first determining determines the first value associated with the first request type, the first request type being one of a plurality of request types and each of the plurality of request types having an associated value, the first value being the associated value for requests of the first request type, andthe updating updates the associated values for the plurality of request types. 5. The method of claim 3, wherein the updating is based on a mean service time for requests of the first request type, a probability of rerouting associated with the first request type and a second value, the second value modeling a number of requests of the second request type in a virtual queue. 6. The method of claim 5, wherein the updating updates the first value if -1+∑j⁢maxi⁢c⁢⁢τβj⁢μij⁡[η⁢⁢Qi-∑k=1I⁢⁢pik(j)⁢η⁢⁢Qk]+≥0 wherein i is the first request type, k is the second request type, j is the at least one of the plurality of server pools, r and c are parameters greater than zero, Qi is the first value for the first request type i, Qk is the second value associated with the second request type k, βj is a number proportional to the number of servers in the at least one of the plurality of server pools j, 1/μij is the mean service time for the first request type i and the server pool j, η is a parameter and pik(j) is a probability of rerouting that the first request type i request served by the pool j is rerouted as the second request type k request. 7. The method of claim 6, wherein the updating updates the first value if maxi⁢μij⁡[η⁢⁢Qi-∑k=1I⁢⁢pik(j)⁢η⁢⁢Qk]>0 for the server pool j. 8. The method of claim 7, wherein the updating updates the first value Qi and determines values Sj, Qi* and Ai*,j as follows Sj=min{Qi,cτβjμi*,j}Qi*:=Qi*−(1−pi*,i*)Sj Qi:=Qi+pi*,iSj, iε, i≠i* Ai*,j:=Ai*,j+Sj wherein i* is i*∈arg⁢⁢maxi⁢⁢μij⁡[η⁢⁢Qi-∑k=1I⁢⁢pik(j)⁢η⁢⁢Qk]. 9. The method of claim 8, wherein the updating includes determining an average of the value Aij and the probability of routing as follows: Āij:=η1Aij+(1−η1)Āij ϕij⁢:=A_ij∑m⁢A_im wherein Φij is the probability of routing the first request type i request to the server pool j. 10. The method of claim 5, wherein the updating updates the first value if maxi⁢μij⁡[∑k=1I⁢⁢pik(j)⁡(wik(j)-nVi+nVk)+pi⁢⁢0(j)⁡(wi⁢⁢0(j)-nVi)]>0⁢ wherein i is the first request type, k is the second request type, j is the at least one of the plurality of server pools, Vi is the first value for the request type i, Vk is the second value associated with the second request type k, μij is a mean service time for the request type i and the server pool j, n is a parameter, pik(j) is a probability of rerouting that the first request type i request served by pool j is rerouted as the second request type k request, and wik(j) is a corresponding reward. 11. The method of claim 10, wherein the updating updates the first value Vi and determines values Ai0, Vi* and Ai*,j as follows: Vi*:=Vi*+τβjμi*,j(1−pi*,i*)Vi:=[Vi−τβjμi*,jpi*,i]+, iε, i≠i* Ai*,j:=Ai*,j+τβjμi*,j Ai0:=Ai0+[Vi−τβjμi*,jpi*,i]−, iε, i≠i* wherein i* is i*∈arg⁢maxi⁢⁢μij⁡[∑k=1I⁢⁢pik(j)⁡(wik(j)-η⁢⁢Vi+η⁢⁢Vk)+pi⁢⁢0(j)⁡(wi⁢⁢0(j)-η⁢⁢Vi)]. 12. The method of claim 11, wherein the updating includes determining an average of the value Aij and the probability of routing as follows: A_ij⁢:=η1⁢Aij+(1-η1)⁢A_ijϕij⁢:=A_ij∑m⁢A_im wherein Φij is the probability of routing the first request type i request to the server pool j, and Φi0 is a probability of blocking the first request type i request. 13. The method of claim 1, wherein the first determining is not based on measurements of input rates of different request types. 14. The method of claim 1, wherein the first determining includes, decreasing the first value associated with the first request type. 15. A method of controlling a routing system, the method comprising: receiving a request having a first request type, the first request type being associated with a first value, the first value modeling a number of requests of the first request type in a virtual queue;updating the first value periodically based on a mean service time to process the request and at least a second value associated with a second request type, the updating being performed without determining an input rate of received requests of the first request type and, the second value modeling a number of requests of the second request type in a virtual queue; androuting the request based on the updating. 16. The method of claim 15, wherein the updating updates the first value if -1+∑j⁢maxi⁢c⁢⁢τβj⁢μij⁡[η⁢⁢Qi-∑k=1I⁢⁢pik(j)⁢η⁢⁢Qk]+≥0 wherein i is the first request type, k is the second request type, j is the at least one of the plurality of server pools, τ and c are parameters greater than zero, Qi is the first value, βj is a number servers in the at least one of the plurality of server pools j, 1/μij is the mean service time for the first request type i request and the server pool j, η is a parameter and pik(j) is a probability that the first request type i request served by pool j is rerouted as the second request type k request. 17. The method of claim 15, wherein the updating updates the first value if maxi⁢μij⁡[∑k=1I⁢⁢pik(j)⁡(wik(j)-nVi+nVk)+pi⁢⁢0(j)⁡(wi⁢⁢0(j)-nVi)]>0 wherein i is the first request type, k is the second request type, j is the at least one of the plurality of server pools, Vi is the first value, 1/μij is the mean service time for the first request type i and the server pool j, n is a parameter, pik(j) is a probability of rerouting that the first request type i request served by pool j is rerouted as the second request type k request, and wik(j) is a corresponding reward for the second request type k request. 18. The method of claim 15, further comprising: increasing the first value associated with the first request type when the request is received. 19. The method of claim 15, further comprising: decreasing the first value associated with the first request type when the request is received. 20. The method of claim 15, wherein the updating includes, determining a probability of routing based on the mean service time to process the request, at least the second value and a probability of rerouting, andthe routing routes the request based on the probability of routing.