Algorithm for Dynamic Client Side Throttling

Problem

I am trying to come up with an algorithm that will dynamically throttle a client's number of outstanding requests based on the response times of completed requests. Response times are unpredictable and can be between 7 and 90 seconds. The response times are greatly affected by the total of outstanding requests, if the server is flooded it bogs down and times increase to very long times.

My specific scenario

My client application has several http requests it needs to send to a server (actually 3 servers that are load balanced and use a round robin distribution, the number of servers and the code running there are out of my control). Each request is a flat object containing 25 parameters. The server uses the parameters to do several look ups which may or may not trigger other look ups and calculations, this is where the server processing time is variable. The server returns a list of corresponding results which can be 0 to approximately 25 in length for most results.

What I have tried

I created a rolling average class that keeps the response times of the last X number of responses and can give the average at any point. Then when each response is received I compare its response time to the average. If the response time is equal or less than the average I increase the number of allowed outstanding requests. If the current response time is greater than the average I decrease allowed outstanding requests.

This approach worked somewhat in scaling up but I had cases where the average just grew over time and allowed more and more outstanding requests which brought everything to a crawl.

I have an implementation question on stackoverflow if you want more details on how I am doing this in code minus the rolling average part.

https://stackoverflow.com/q/30263716/1168353

I have been using a mocked out version of the server that just sleeps a thread before returning a response. I pick a "bestWaitSeconds" that is the fastest time it can return and a "MaxRequestsB

this is a fairly basic problem in control theory and there are "design patterns" in this area to handle this type of system, and think there is probably an example right out of a control theory book very close to your question. basically the theory involves a concept somewhat like the way a thermostat regulates temperature in a house. if the house is too hot, the heater shuts off, if is too cool, it turns on. you want something like the opposite where more delay ("throttling") is applied when there is greater load, however the principle is the same.

a basic solution is something like this. keep track of the minimum response time, this is a "baseline". now measure the current instantaneous difference between the minimum response time and current response time, this is roughly proportional to "load". now one does not one long-past load to influence current load readings. but neither does one want a large current spike in load to effect the throttling too much. the immediate idea here is to use a exponential running/ moving average of the load measurements to determine the throttling (this metric is used a lot in stock trading algorithms). exponential averages have a tunable continuous parameter (0..1) that basically weights between current and past values, at one end the past values are weighted lighter, at the other end the current value is weighted heavier.

my suggestion is to try this algorithm for different weighting values and then graph the results. notice a lot of web load problems vary over daily rates where midday or midweek have highest load. in that case a changing weight value might be more optimal. a basic strategy to figure out the general trend of cycles in input load would be to have no throttling and then just look at daily or weekly loads.

note that some round-robin routers are automatically doing something like basic load balancing because they do not route to already busy connections.

StackExchange Computer Science Q#43149, answer score: 4