Algorithm 3 outlines the Binsearch algorithm. Intuitively, Binsearch keeps doubling the current test load until it finds a load that saturates the server. After that, Binsearch applies regular binary search, i.e., it recursively halves the most recent interval of test loads where the algorithm estimates the peak rate to lie.
Binsearch allows the controller to find the lower and upper bounds for the peak rate within a logarithmic number of test loads. The controller can then estimate the peak rate using another logarithmic number of test loads. Hence the total number of test loads is always logarithmic irrespective of the start test load or the peak rate.
![\begin{algorithm}
% latex2html id marker 1051
[t]
\caption{Binsearch {\bf Input}...
...earch$_{low}$)/$2$\;
\vspace{-1ex}
\par
\end{list}\vspace{-2ex}
\end{algorithm}](img85.png)