edit: I did some more investigation, and I missed something crucial: The distribution of requests over time becomes very wonky if the lower bound isn't 0. It stabilizes given enough time, but that time seems very long. Whereas lower-bound 0 quickly becomes uniform.
See the following figure, where I plot the # of requests over type: https://i.imgur.com/PNUFhjc.png
And that is why you should use 0.
---
I am not an expert, but I got nerd-sniped.
I have made some simulations[1] and done some napkin math[2], and I would summarize as follows:
I don't think there is any globally optimal, I think it depends on your exact circumstances, and which of {excess waiting time, excess load} you want to optimize. Defaulting to 0 is a lot easier to implement, and is at most a factor 2 worse than the optimal lower bound w.r.t. waiting time vs. load. You may also consider [0.5 * maximum, maximum], which trades some excess waiting time for less load. Your suggestion is a similar heuristic one might use depending on their exact circumstances.
[1] https://gist.github.com/Dryvnt/1984d9389ae7386127f5e8998bf52...
[2] Consider a family of random bounded exponential back-off strategies with ultimate upper bound U as follows:
Strategy X(z): Random of [z * U, U], where z is constant, 0
There are other families of back-off algorithms with other characteristics, and I am not considering or comparing those, just this family. Note that strategy OP suggests is X(0). Consider that X(1) is non-random, which is undesirable.
Simple probability tells us
avg(X(z)) = (1 + z) * U / 2
Server load ~= frequency, frequency is inverse duration, so
load(X(z)) ~= 1 / avg(X(z)) = 2 / (1 + z) * U
The difference in load between any two X strategies is
load(X(z1)) / load(X(z2)) = (1 + z1) / (1 + z2)
Since z1 and z2 are constant, this relative load is constant. Due to the bounds on z, the largest possible relative load is
load(X(1)) / load(X(0)) = 2 / 1 = 2
Now consider your suggested strategy
Strategy Y: Random of [L, U], where L is the last choice
Note that
Y = X(y), where y = L / U.
In fact, Y approaches X(1) exponentially fast, since the difference between L and T is halved each step, on average. So your suggestion still falls within this at-most-factor-2 difference. Exactly where just depends on the outage length.
