bramcohen: Estimated Time Left

Bram Cohen (

bramcohen) wrote,
@ 2005-11-11 11:40:00

Estimated Time Left
It turns out that estimating time left to complete a download is non-trivial. What BitTorrent currently does (simplifying a little) is to average total download over total time for the first half of the file, then for the second half of the file to update estimated time left as each piece comes in by assuming that the amount of download averaged over for the current estimate is equal to the amount of download left. This approach gives a fairly reasonable estimated time left under almost all circumstances, but it has a significant artifact.

The problem comes up when what was a very unstable download rate suddenly becomes a steady download rate. Frequently after that the estimated time left will drop at a predictable rate of, say, two seconds per second. A certain amount of this is totally unavoidable. The download rate may change to something else, and then the estimated time left might be totally reasonable or start creeping back up again. The problem is that the dropping tends to happen continuously, all the way to the end of the download. It would be far more preferable for the rate of dropping to be somewhat higher, and then after, say, 25% of the remainder has been downloaded, to have the estimated time left basically nailed and drop at a nice clean rate of one second per second. The amount of time it takes for the estimated rate to get accurate should probably be a parameter to the algorithm, settable at somewhere between 0% and 100%, which can be set based on whatever seems to be most psychologically reassuring for the users of the given application. Note that having this property probably makes the estimated time left less accurate from the point of view of placing bets on when the download will complete, but considerably nicer to watch go down as the download progresses.

If anyone can figure out an estimated time left algorithm which fulfills this criterion, and doesn't have any nasty artifacts I would greatly appreciate it.

(Post a new comment)

	i'm probably oversimplifying the problem, but endquote 2005-11-11 09:07 pm UTC (link)
	What I've done in the past (to buffer A/V files for playback before completed download) is to get the average bps over the last N seconds, rather than the average over the life of the download. This should should tell you what the connection is behaving like now, rather than how it's been on average. (Reply to this) (Thread)

	Re: i'm probably oversimplifying the problem, but bramcohen 2005-11-11 11:18 pm UTC (link)
	That suffers from two problems - first, if the download time is many times larger than N, the download rate will fluctuate wildly, and second, if the download rate was very atypical exactly N seconds ago, the current download rate will vary strangely for no apparent reason. (Reply to this) (Parent)

Probably heard this before...

_creepystalker_
2005-11-11 09:15 pm UTC (link)

Why not use the average amount of time it took for the seeds to download the file? You could then scale that estimated time by the current download speed to the average download speed ratio. I have at least one BitTorrent client going day and night, and I can say that knowing when the torrent is going to end is very important to me, and I'm sure other people..

..though it is half the fun to guess when the torrent is going to be done...

-Fredric

(Reply to this) (Thread)

	Re: Probably heard this before... bramcohen 2005-11-11 11:21 pm UTC (link)
	Why not use the average amount of time it took for the seeds to download the file? Because (a) you don't have it, and (b) you care about how long it will take for you to download, not them, and you're different from them because you have a different upload capacity, download capacity, and are downloading at a different time. (Reply to this) (Parent)

The expensive and labour intensive approach

dojothemouse
2005-11-11 09:18 pm UTC (link)

Collect a ton of data collected from users in boatloads of different situations and dump it all into SPSS Clementine. You have money now, right?

If you do the average bps over the last N seconds, you might fail to predict regular changes in how much data you can get from the swarm at different parts of the download, or given different scarcity for remaining chunks. Dunno if you're interested in that.

I've never played with an algorithm more complicated than inserting into a red-black tree, so, uh, don't assume that I assume that I know what I'm talking about.

(Reply to this) (Thread)

	Re: The expensive and labour intensive approach dojothemouse 2005-11-11 11:15 pm UTC (link)
	Alternatively you could find an expert on machine learning who was already set up and willing to crunch data for you and for free. And skip Clementine and skip expensive. But that's pure fantasy, right? (Reply to this) (Parent)(Thread)

Re: The expensive and labour intensive approach -

bramcohen, 2005-11-11 11:23 pm UTC

Re: The expensive and labour intensive approach -

dojothemouse, 2005-11-11 11:41 pm UTC

Re: The expensive and labour intensive approach -

dojothemouse, 2005-11-11 11:44 pm UTC

chouyu_31
2005-11-11 09:20 pm UTC (link)

I believe that all techniques which estimate download time remaining have artifacts of some kind or another. Whether or not they are nasty is subjective. I would personally use a weighted average of the transfer rates over blocks of time or data.

Say, for example, you have been downloading a file for 60 seconds. We forget all transfer rate information for the first 30 seconds. The most recent 30 seconds, we divide up into 10 groups (31-33, 34-36, ...). Each of those 10 groups are individually averaged and numbered 1...10. We then come up with a weighted average of the form...

wa = sum(g[i]*(i+1)**j for i in xrange(10))/sum((i+1)**j for i in xrange(10))

Choose j, 0 < j <= 3 to decide how much you want to weight the most recent time versus the earliest time.

The above method has a history, but is still generally more reliant on recent data than old data. Considering that transfer rates can do literally anything, whatever mechaism you use is going to have issues. Deciding how far back to remember transfer rates for weighing is a the above, and what j to use, will take a bit of tuning, but if done right, should recover from mistakes relatively quickly.

(Reply to this) (Thread)

	bramcohen 2005-11-11 11:25 pm UTC (link)
	That technique is similar to what I'm using now, but a lot more complicated, will act funky when you get close to the end of the download, and still has the artifact which I complained about in this post. (Reply to this) (Parent)(Thread)

(no subject) -

chouyu_31, 2005-11-12 02:38 am UTC

edm
2005-11-11 09:32 pm UTC (link)

I'm thinking out loud here, but possibly it'll be of use at least as something to consider. It seems to me that most users will accept the download time going up again if, eg, the download rate suddenly slows significantly due to a source disappearing or net congestion or whatever -- there's an obvious explanation for it going up so it's expected. But obviously you don't want to do this dramatically every time there's a short blip in the download rate.

So, there's a couple of predictors of the download speed: (1) the overall average download speed (time taken to receive the parts of the file received so far, divided by the time spent trying) and (2) the "recent" transfer speed (eg, bytes received in the last minute). I suspect the averaging period for the second probably needs to be at least somewhat tunable (perhaps to taking the lowest of several short periods - 30 seconds, 1 minute, 5 minutes, 10 minutes), or adjusted by file size (eg, time to download most recent 1%).

When you have relatively little of the file, there's a strong risk that whatever portion you've managed to get quickly so far was just "lucky", and that luck might not hold out. So the instantaneous (type 2) download speed is relatively untrusted, and the long-run (type 1) download speed is more likely to be accurate. But you might have reached the turning point (eg, enough people have the bits of the file you don't yet have) that you're assured of a good download speed from here in, so you can't completely discount the instantaneous download speed.

When you have almost all the file, given the way bittorrent operates (as I understand it, getting the rare parts first, then the common parts), there's a much stronger chance that you'll be able to download the remaining parts at something approaching your instantaneous download speed, and the struggle over the earlier parts of the file doesn't apply. But of course not completely, because a bunch of people who have finished downloading might close their sessions making those "common" bits much rarer, or there might be some sort of network event.

To the first order of approximation it seems to me that the closer you are to the start of the file (well, having very little of it), the more likely the first situation will apply (ie, strong risk that instantaneous download speed is a short term fluke), and the closer you are to the end of the file (having nearly all of it), the more likely the second situation will apply. So as a very rough metric one might take the percentage of the file retrieved as a weighting factor between these two. Eg:

((% left to retrieve) * long-run-speed) + ((% retrieved) * instantaneous-speed)

I've not really explored that to see what sort of artifacts it'll have, or whether they're "nasty" (as I noted above, I think there's some acceptance that the time ought to go up again if the instantaneous download rate significantly slows), but possibly with some additional fudge factors (eg, pessimism about the continuation of the instantaneous speed -- or the long run speed if that's faster) it might work out. The user might also be given a weighting factor to apply to the above, in the form of trust-in-instantaneous-speed.

I'd be interested to know if you've tried something like that and how well/badly it's worked.

Ewen

(Reply to this) (Thread)

	bramcohen 2005-11-11 11:33 pm UTC (link)
	The problem is that long run speed continues to factor no matter what, resulting in the artifact I complained about above and a few others as well. (Reply to this) (Parent)(Thread)

(no subject) -

edm, 2005-11-12 12:15 am UTC

minorninth
2005-11-11 10:25 pm UTC (link)

I would love to treat this as a machine learning problem and see if I can train, say, an SVM regression algorithm to predict the remaining time. One of my colleagues at JPL did some work on predicting the onset time of a CME given timeseries of space weather data. This problem ought to be easier, if anything.

One thing that makes it interesting, though, is that there's a psychological aspect to it: the user wants to see the time steadily decreasing. It's bad to skip two seconds for every one second, but it's even worse to increase the time remaining too often or jump around in time. (I hate progress bars that update the time remaining with wildly inaccurate estimates 5 times per second.) So the algorithm that gives the best predictions in a mean-squared-error sense may not actually be the preferred one from a UI standpoint.

Could you collect some training data from hundreds of different runs that I could play with? Whatever approach you use, I think it would be helpful to have such data to analyze. Any supplemental data, like the number of peers, would also be helpful.

I've wanted a little code snippet to do something like this for several other projects, too. I'd love to see a little generalized LGPL function for "smart" progress bar time-remaining estimates that I could incorporate into several projects.

- Dominic

(Reply to this) (Thread)

	bramcohen 2005-11-11 11:39 pm UTC (link)
	Machine learning is totally the wrong tool for this problem. What's needed is something simple, reliable, and analyzable. Machine learning accomplishes none of those. (Reply to this) (Parent)(Thread)

(no subject) -

minorninth, 2005-11-12 12:16 am UTC

(no subject) -

jamuraa, 2005-11-12 06:25 am UTC

(no subject) -

dojothemouse, 2005-11-12 09:35 am UTC

(no subject) -

jamuraa, 2005-11-12 05:26 pm UTC

grimmtooth
2005-11-12 12:22 am UTC (link)

What I've done in the past for a similar issue (determining the frequency stability of an RF semi-anechoic chamber) was to utilize two techniques in parallel.

The first was to use a sliding window; samples outside that window were discarded. This allowed my data to more accurately reflect relevant data, rather than readings taken three years in the past when the chamber was brand new and after re-calibrating all the equipment at least twice.

The second was to discard all data that fell outside two times the average deviation for all samples to date.

This worked out pretty well.

The latter technique was actually borrowed from other areas in our labs; our mech and elec engineers all used it in one form or another for analyzing data in a statistical fashion.

(Reply to this) (Thread)

	bramcohen 2005-11-25 07:20 am UTC (link)
	That first technique suffers from bizarre fluctuations in value when the back end of the sliding window was an atypical time. Your second technique suffers from some fairly serious systemic bias. If individual piece downloads significantly faster than normal happen regularly (if, say, a fast peer decides to send you a few) then they'll be ignored. (Reply to this) (Parent)(Thread)

(no subject) -

grimmtooth, 2005-11-25 02:35 pm UTC

	zx2c4 2005-11-12 12:38 am UTC (link)
	What about taking the average of download speeds for consecutive times that stay within, N kbps. As soon as the speed changes by N in a time greater than T, the numbers averaged are discarded. T and N would be varible based on the previous history of how often the changes occur. (Reply to this) (Thread)

	bramcohen 2005-11-25 07:20 am UTC (link)
	Sudden changes are exactly what I'm trying to avoid. (Reply to this) (Parent)

gjm11
2005-11-12 12:39 am UTC (link)

Suppose the time is now t. Estimate what the transfer rate will be at time t+h, for any h>0, by averaging between times t-kh and t (where k is a tunable parameter); of course, if t-kh<0 you just average from 0 to t. Integrate with respect to h, and see when the integral reaches the total amount of data remaining to transfer.

If k is very small, this says (kinda): assume the future transfer rate is equal to the most recently observed transfer rate.

If k is very large, this says: assume the future transfer rate is equal to the overall transfer rate so far.

If the transfer rate has been constant for time dt, the future transfer rate will be assumed to be the same constant for a further time dt/k. So, if the transfer rate is random for a while and then settles down permanently, the predicted transfer rate will be perfectly steady once you're k/(k+1) of the way through the steady phase. So for your figure of 25% you'd want k/(k+1) = 1/4, or k=1/3.

For bonus points, estimate your uncertainty about the transfer rate at time t+h as some sort of measure of variation of the transfer rate for times t-kh..t; then when you do that integration you can estimate your uncertainty about the amount that will have been transferred by time [whenever], and you can use *that* to give an estimate of uncertainty in the completion time, or to let the user ask for "pessimistic" completion times (e.g., the time by which you're 95% sure it will be done, in some sense). This is almost certainly not worth doing.

Doing all that integration sounds pretty alarming, but (1) you only need to do this (say) 10 times per second, and you can do a *lot* of calculation when it only happens that often, and (2) I bet you can simplify it somewhat.

This also requires you to keep a complete history, not just a couple of averages or totals. If you make a note every 1k or every 0.1 seconds, the amount of memory required can't grow unreasonably fast, so this too isn't a real problem.

(Reply to this) (Thread)

	bramcohen 2005-11-25 07:22 am UTC (link)
	The current transfer rate is too volatile. The overall rate so far suffers from being too static. There needs to be a sliding window with a shrinking range to keep the estimated time left from getting horribly distorted towards the end. (Reply to this) (Parent)(Thread)

(no subject) -

gjm11, 2005-11-25 09:55 pm UTC

moving average

cratermoon
2005-11-12 01:20 am UTC (link)

A standard exponentially smoothed weighted moving average is simple, but I'm insufficiently skilled to analyze it for nasty artifacts. If you keep only the last N measurements you'll be continually "windowing" the calculation to the current download speed, and then stop windowing when the download rate and % left indicates that there are N chunks left and just countdown from there.

(Reply to this) (Thread)

	Re: moving average bramcohen 2005-11-25 07:22 am UTC (link)
	That's what I'm using right now. (Reply to this) (Parent)

jrronimo
2005-11-12 01:41 am UTC (link)

I have no-where near the qualifications of anyone else posting here, but that's okay, I'll take an ignorant shot:

What if you take the Total File Size divided by the Download Speed over the last N Download Speeds (averaged)?

It should be slightly more accurate than just dividing the total file size by the current download speed (which will vary wildly). It'll be inaccurate until the mean speeds are reached (when the first 5 Download Speeds are 1KB/s, 2KB/s, 3KB/s, 5KB/s, 9KB/s for N=5), but once the speed stabilizes a bit more (90KB/s-95KB/s, but doesn't change over the most recent 20 minutes of downloading), it should be relatively okay.

(Reply to this)

An even dumber idea on my part

dojothemouse
2005-11-12 02:55 am UTC (link)

The same problem exists for the progress bar. Since the time-left is impossible to calculate, you can only display that you have %78 of the bytes in the file downloaded, but that's not necessarily a great indicator of progress.

If you can't come up with a better algorithm for determining time-to-arrival, you might be able to come up with a better algorithm for error in your time-to-arrival.

If that is the case, I think you should cook up a brand new widget:

And use gradients to indicate the level of confidence in either your current progress or the total time to completion. Put the thing on a time scale rather than byte scale. When the process nears completion, your predictions will be more accurate and the amount of gradient will decrease. A stalled download would look like someone rubbed an eraser across your monitor. It would be awesome.

You wanted simpler, right? Sorry...

(Reply to this) (Thread)

	Re: An even dumber idea on my part simoncion 2005-11-12 03:24 am UTC (link)
	Brilliant! (Reply to this) (Parent)

Re: An even dumber idea on my part -

bramcohen, 2005-11-25 07:25 am UTC

	Kalman filter dvorak 2005-11-12 08:58 am UTC (link)
	Friend of mine suggested this: http://en.wikipedia.org/wiki/Kalman_filter He says it's used frequently in digital sensors and such for predicting that sort of stuff. Not sure if it fits what you want, but from his description it sounded close. (Reply to this) (Thread)

Re: Kalman filter

ciphergoth
2005-11-12 10:06 am UTC (link)

This sounds like a good idea. It would be much like the example on that page. \sigma_z is zero. The tricky part is choosing the right values in the Q matrix. A diagonal matrix would be fine, but I think you'd have to cheat somewhat and choose a Q proportional to your current estimate of the download rate - or your download rate plus some offset, otherwise you could never recover from an estimate of zero.

Then it would be a question of analyzing a lot of downloads to see what Q factors gave you the best estimate...

(Reply to this) (Parent)

Re: Kalman filter -

masterkill, 2005-11-12 06:27 pm UTC

Re: Kalman filter -

gjm11, 2005-11-13 01:09 am UTC

Re: Kalman filter -

bramcohen, 2005-11-25 07:31 am UTC

Re: Kalman filter -

ciphergoth, 2005-11-27 06:09 pm UTC

	discountbrain 2005-11-13 06:07 am UTC (link)
	I know nothing, but taking samples with the number of seeds/(avg download rate for 30 second window) with samples every 3 minutes would result in an average speed per seed and would result in a dataset that you could check the remainder of the download against with the number of seeds available. this is assuming that the tracker does not go offline. (Reply to this) (Thread)

	bramcohen 2005-11-25 07:32 am UTC (link)
	Estimating the download rates of peers or the system as a whole is not particularly useful when what you're really interested in is the time left for your own specific peer. (Reply to this) (Parent)

Drift

mattbamberger
2005-11-13 05:57 pm UTC (link)

Seems like the interesting part of this is making the displayed time count down nicely. How about counting down the estimate in realtime, and applying a drift factor to converge on the current best estimate?

float CalcSecsLeftToDisplay() // Called once / second
{
float secsLeftTrue = CalcTrueSecsLeft();
s_secsLeftDisplay -= 1;
s_secsLeftDisplay += DriftFactor( secsLeftTrue, s_secsLeftDisplay );
return s_secsLeftDisplay;
}

// Too simple, but you get the idea.
// Real function would drift harder as the values diverged further.
// If CalcTrueSecsLeft is too erratic, you could add hysteresis here.
float DriftFactor( secsLeftTrue, secsLeftDisplay )
{
if ( secsLeftTrue > secsLeftDisplay )
return 0.3;
else if ( secsLeftTrue < secsLeftDisplay )
return -0.3;
return 0;
}

(Reply to this) (Thread)

Re: Drift

bramcohen
2005-11-25 07:38 am UTC (link)

I've thought of that, the problem is that the drift factor might not be large enough, causing you to actually finish before the time left hits zero, or for the estimated time left to go up such a large amount that you're stuck just watching time left go up by drift factor for a very long time.

There's also the matter of potential systemic bias depending on how your drift factor works. For example, if your downloads alternate between a reliable rate and stopped, and you're using current download rate to estimate time left, then you might spend all time drifting either up or down, and if, say, the paused periods tend to be longer, then you'll spend more time drifting up, so long term your estimated time left will keep going up indefinitely, even though real progress is being made.

Of course these problems don't invalidate the approach, they just indicate that the formulas for the drift factor and the thing being drifted towards must be chosen very carefully.

(Reply to this) (Parent)

Another view of the problem

arnaudl
2005-11-15 09:25 am UTC (link)

Hello,
from my point of view the question is: what is the reason of download speed changes?

From what I observed in my experimentations, the main reason is the change of peers in the set of peers that upload data to you.
I would say that as long as this set of peers is stable, a simple estimate based on the past will fit your purpose.
However, when the set changes, it would reset the history of download speed and start a new history.
A typical use case is when a single seed (using the old algorithm) sends at a very high speed data to you. If this single peer leaves your set of active downloading peers, then your estimate of total download speed should reflect
this huge change. In this case, the only way if to forget the history for this peer.

Of course, this is a bit simplistic, but I believe that gives the scheme for a reasonable solution.
The questions that remain are:
-which threshold do you use to deem that the peer set change should lead to an history reset? As you know the upload speed of each remote peer that sends data to you, that should not be that hard. In particular, you can maintain an history peer active downloading peer, and remove this history as soon as the peer has left the active downloading set.
-how do you manage the transition between history reset and the new estimate availability? Probably a simple weight that gives few impact to the past should solve this problem.

Arnaud.

(Reply to this) (Thread)

Re: Another view of the problem

bramcohen
2005-11-25 07:41 am UTC (link)

In practice the peer set changes frequently enough that such cleverness is quite difficult to use in a reasonable way. Also, the tit for tat algorithm makes it so that losing a peer changes download rate a lot less than you'd expect. And of course, if you're consistently maxing out your download capacity then it won't much matter if it's being maxed out by n-1 peers rather than n.

(Reply to this) (Parent)

Digital decay...

kamil_choudhury
2005-11-15 12:51 pm UTC (link)

...is probably the best way to go.

Take a time window of samples, and then multiply them by a exponential of form e^t over the time window, giving greatest weight to the most recent sample, and the least to the the oldest one in the window. Take care to normalize the exponential. In my (meagre) experience this works-- although it depends heavily on what metric you are using as your "sample".

(Reply to this)

	Pardon my rudeness, Please reply my email soon. Thank you vividyu 2005-11-17 05:04 pm UTC (link)
	Pardon my rudeness, Please reply my email soon. Thank you (Reply to this) (Thread)

Pardon my rudeness, Please reply my email soon. Thank you

vividyu
2005-11-18 02:03 am UTC (link)

My email address is vividyu@yahoo.com.cn

and the following is my questions:

What is the innovative concept in Internet today and what is the big challenge here?

Tell me about the birth of BitTorrent Inc.;

What inspires you? Who inspired you?

How do you make Hollywood on your side? Can you give me some specific examples of that?

How do you try to ensure that BitTorrent Inc. continually innovates even as it grows into a large corporation?

What are the biggest challenges facing you and your company?

What's your role today in the BT phenomenon, and how is it different from your role in the past?

Please describe the development organization and process.

What's next on your agenda?

A lot of people seem to be happy that venture investment is again on the rise. Are you?

How do you view VC efforts?

(Reply to this) (Parent)

Generalisation of your method.

haircaspian
2005-11-28 05:45 am UTC (link)

If I understand correctly, in the second stage of your method you assume the final n bytes of the download will take as long as the n bytes before. For example, the time remaining once you've downloaded 90% is estimated as the time it took to get from 80% to 90%.

It seems like if the actual download speed jumped at 80% to a higher stable value, at 90% the estimated time should start progressing at 1 sec/sec. That doesn't match the description, I'm not sure why not, but I'll carry on anyway. I think I've got the maths right.

If you want the speed to correct after 85% is downloaded instead of 90%, (taking 25% instead of 50% of the time remaining), estimate that the last 15% will take as long as the 5% before it to download, or in general, the last 3n bytes will take 3 times as long as the n bytes before them took to download.

To tune it to some other percentage than 25%, call it t%, estimate the final Cn bytes take C times as long as the n bytes before, where C=(100%-t%)/(t%)
The first stage is the same as in your method, and the changeover is as soon as t% is downloaded. At t%=50% it's the same as your original method

I see gjm11 has almost the same proposal, but starting with download rate instead of its inverse, download time.

(Reply to this)

A sideways approach

ciphergoth
2005-12-01 11:53 am UTC (link)

I'm guessing that part of the problem you're trying to solve is that users find it very weird when the estimated time to finish goes up instead of down. Rather than calculating it differently, maybe you need to present it differently.

Instead of displaying the number of seconds remaining, display an estimated time of arrival as a time of day. Then fluctuations in this value, in both directions, will seem more natural. Since this is what I want to know whenever the estimated time left is more than a few minutes, this might solve several problems at once.

(Reply to this)

PID Controller

mckoss
2005-12-28 06:59 pm UTC (link)

I will outline a solution approach, though I've not implemented this myself. This problem seems to be very correlated with that of feedback control systems in general. We are trying to estimate the behavior of an external system, and then make predictions about the effect of our inputs (here, guess about time remaining).

A good solution to should adapt itself well to:

- One-time changes in download speed.
- Simple time-varying changes (periodic).
- Linear increasing or decreases in download speed.

Using the techniques of a PID (Proportional-Integral-Derivative) controller, you estimation system is essentially building an online categorization of the behavior of the system that will adapt over time. By setting the parameters of the control system appropriately, you can tune it to have the best behavior for the most common situations.

Interesting problem - I think I heard you mention this in your Stanford lecture (video) - it's intriguing to me that you're still looking for a good solution - I hope this helps.

- mike

(Reply to this) (Thread)

	Re: PID Controller mckoss 2005-12-28 07:00 pm UTC (link)
	BTW - good wikipedia artivle on PID controllers: http://en.wikipedia.org/wiki/PID_controller (Reply to this) (Parent)

Username:		Create an Account Forgot your login? Login w/ OpenID
Password:
	Remember Me
	English • Español • Deutsch • Русский…

About

Help

Get Involved

Legal

Store

LJ Labs