We started from these principles:
(1) The goal of prefetching is to utilize otherwise
unused bandwidth to reduce perceived latency.
(1a) Prefetching should never increase perceived latency.
(2) Only the server has sufficient history or knowledge
to be able to predict, based on the retrieval of one URL,
which other URLs are likely to be retrieved by a client.
(3) Only the client (browser) knows what is in its own
cache, and whether the user has shifted attention.
Therefore, in our approach (which assumes a persistent connection):
(1) the server keeps a history of per-client fetch
streams in order to build a Markov model for making
predictions (this is based on a file system paper
by Griffioen and Appleton in Summer '94 USENIX).
I suppose our approach would work just as well with
the more mechanistic Touch/Farber approach, although
that could probably be simulated by a more elaborate
probabilistic model.
(2) after each retrieval, the server consults its
Markov model to obtain one or more predictions of the
next retrieval by the same client. A "prediction"
includes a URL and a probability. [It might also
include a cache validator for the URL?]
(3) The server maintains a threshold probability,
perhaps statically chosen by an administrator, or
dynamically chosen based on server load. It transmits
predictions to the client if their probability
exceeds this threshold. For example, if the predictions
are:
/a/b/c .9
/a/b/d .7
/a/b/e .1
and the threshold is .5, then the server tranmits only
the first two predictions.
(4) We would modify HTTP to add a new response header
to carry predictions. Ideally, these should come AFTER
the data in the response (to avoid any extra latency),
but it might be tricky to do that, and it might not matter
that much. The header might also carry the size of the
object, in case this influences the prefetching decision.
(5) The client receives the predictions, and immediately
weeds out anything that is already valid in its cache.
It also maintains its own threshold probability, and
weeds out predictions below that threshold. If any
predictions are left, and the user has not yet made
an explicit request, the browser prefetches the predicted
URLs.
(6) If the user makes an explicit request while a prefetch
is happening (except for the prefetched URL!), the browser
immediately aborts or suspends the prefetch and does what
the user asked for.
As far as I can tell, ours differs from the other "prefetch"
approaches in that we split up the prediction mechanism
from the control mechanism, since it's not possible to optimize
both in the same place. The server knows the behavior of clients
in general, but doesn't know the state of a particular client's
cache or the preferences of its user. The browser knows its
cache state and user preferences, but may never have visited
this server before, so cannot make its own predictions. And
(ignoring the effects of congestion), since the client has
complete control over the prefetching mechanism, if the user
shifts attention or makes an unpredicted request, the prefetch
can be aborted immediately, so no extra latency is imposed.
We believe that this can be easily added to HTTP 1.x, since it
requires only:
(a) persistent-connection support, already in 1.1
(b) a new response header to transmit predictions, e.g.,
Prediction: <URL> <probability> [<size>] [<validator>]
(c) an effective way of aborting prefetches
(c) is actually useful with persistent connections in any event.
-Jeff