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.
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 "MaxRequestsBeforeDegradation" that determines the maximum number of requests before times increase, anything below that returns bestWaitSeconds. The degradation formula looks like the below and only applies when "currentRequests" is more than MaxRequestsBeforeDegradation.
secondsToWait = (currentRequests - MaxRequestsBeforeDegradation) * (r.NextDouble() + .5) * bestWaitSeconds;
The random is just a way to apply the unknown return time stated in the problem. Times do go well above 90 seconds when the server is overloaded. This formula isn't exactly what the server does but it conveys the idea I think.
So basically the algorithm needs to get as close to MaxRequestsBeforeDegradation as possible. In the real case that MaxRequestsBeforeDegradation would change over long amounts of time so the algorithm also needs to adapt and explore up and down to continually know where the best number of outstanding requests is. Hope this helps.
How can I dynamically find the optimal number of outstanding requests allowed at a given moment to get the greatest throughput, given only a history of response times?