Methods of routing for networks with feedback
View Patent ↗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 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; and
routing 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, and
the 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
max
i
c
τβ
j
μ
ij
[
η
Q
i
-
∑
k
=
1
I
p
ik
(
j
)
η
Q
k
]
+
≥
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, Q i is the first value for the first request type i, Q k 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 p ik (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
max
i
μ
ij
[
η
Q
i
-
∑
k
=
1
I
p
ik
(
j
)
η
Q
k
]
>
0
for the server pool j.
8. The method of claim 7 , wherein the updating updates the first value Q i and determines values S j , Q i* and A i*,j as follows
S j =min{ Q i ,cτβ j μ i*,j }
Q i* :=Q i* −(1 −p i*,i* ) S j
Q i :=Q i +p i*,i S j , iε , i≠i*
A i*,j :=A i*,j +S j
wherein i* is
i
*
∈
arg
max
i
μ
ij
[
η
Q
i
-
∑
k
=
1
I
p
ik
(
j
)
η
Q
k
]
.
9. The method of claim 8 , wherein the updating includes determining an average of the value A ij and the probability of routing as follows:
Ā ij :=η 1 A ij +(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
max
i
μ
ij
[
∑
k
=
1
I
p
ik
(
j
)
(
w
ik
(
j
)
-
nV
i
+
nV
k
)
+
p
i
0
(
j
)
(
w
i
0
(
j
)
-
nV
i
)
]
>
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, V i is the first value for the request type i, V k 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, p ik (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 w ik (j) is a corresponding reward.
11. The method of claim 10 , wherein the updating updates the first value V i and determines values A i0 , V i* and A i*,j as follows:
V i* :=V i* +τβ j μ i*,j (1 −p i*,i* )
V i :=[V i −τβ j μ i*,j p i*,i ] + , iε , i≠i*
A i*,j :=A i*,j +τβ j μ i*,j
A i0 :=A i0 +[V i −τβ j μ i*,j p i*,i ] − , iε , i≠i*
wherein i* is
i
*
∈
arg
max
i
μ
ij
[
∑
k
=
1
I
p
ik
(
j
)
(
w
ik
(
j
)
-
η
V
i
+
η
V
k
)
+
p
i
0
(
j
)
(
w
i
0
(
j
)
-
η
V
i
)
]
.
12. The method of claim 11 , wherein the updating includes determining an average of the value A ij and the probability of routing as follows:
A
_
ij
:=
η
1
A
ij
+
(
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; and
routing the request based on the updating.
16. The method of claim 15 , wherein the updating updates the first value if
-
1
+
∑
j
max
i
c
τβ
j
μ
ij
[
η
Q
i
-
∑
k
=
1
I
p
ik
(
j
)
η
Q
k
]
+
≥
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, Q i 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 p ik (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
max
i
μ
ij
[
∑
k
=
1
I
p
ik
(
j
)
(
w
ik
(
j
)
-
nV
i
+
nV
k
)
+
p
i
0
(
j
)
(
w
i
0
(
j
)
-
nV
i
)
]
>
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, V i 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, p ik (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 w ik (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, and
the routing routes the request based on the probability of routing.