Methods of routing for networks with feedback

• US 9,378,503 B2
• Filed: 06/30/2010
• Issued: 06/28/2016
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Stolyar, Aleksandr
• Primary Examiner(s): CHOUDHURY, AZIZUL Q
• Application Number:
  US12/801,893
• Publication Number:
  US 20120005370A1
• Time in Patent Office: 2,190 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: H04L 12/00 Data switching networks interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

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.

Claims

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

7. The method of claim 6, wherein the updating updates the first value if

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*,iS_j, iε

, i≠

i*

A_i*,j;

=A_i*,j+S_j

wherein i* is

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;

=η

₁A_ij+(1−

η

₁)Ā

_ij

10. The method of claim 5, wherein the updating updates the first value if

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*,jp_i*,i]⁺, iε

, i≠

i*

A_i*,j;

=A_i*,j+τ

β

_jμ

_i*,j

A_i0;

=A_i0+[V_i−

τ

β

_jμ

_i*,jp_i*,i]⁻

, iε

, i≠

i*

wherein i* is

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:

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

17. The method of claim 15, wherein the updating updates the first value if

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.