On Mon, 11 Sep 2006 17:05:44 -0700, Bill Studenmund <wrstuden@NetBSD.org>
wrote:


> 
> Please suggest an algorithm and implementation. The more detailed, the 
> better.
> 
There's a well-known, simple algorithm that's used in many places,
including TCP (for average round trip time) and many operating systems for
their schedulers.

If L_i is the average latency time -- that is, the time from when a write
request is queued to when it finishes -- and L' is the latency of the
most recent completed request, then

	L_(i+1) = k*L_i + (1-k)*L

You can select k depending on how much weight you want to give the
historical average versus the most recent request, but .5 is quite
common.  You'll find that exact equation in Section 3.7 of RFC 793, for
example.

		--Steven M. Bellovin, http://www.cs.columbia.edu/~smb