Re: keepalive/lookahead

    The http analog for that would be headers and/or HTML tags of some
    kind that indicate other documents that should be fetched whenever a
    given document is fetched because of the high probability that these
    other documents will be viewed whenever the first one is viewed.  This
    doesn't strictly require keepalive, but it interacts well with it, as
    prefetch would be much cheaper to implement using it.  In fact, for
    sufficiently small documents it would be statistically cheaper to
    prefetch, in one TCP connection, some documents that go unread than to
    set up and tear down TCP connections for every document that is read.
    
    Sorry if this is too speculative for this group -- just thought it was
    an interesting idea.
    
I don't think it's too speculative.  In fact, we've been (slowly)
working out the details of a similar proposal, and it should be
possible to fit it into HTTP 1.x (x >= 2), since it does not
require incompatible protocol changes.  I'd suggest that we not
discuss it much until 1.1 is (nearly) done, but here's a summary.
For a longer description, see Venkata Padmanabhan's MS thesis,
   http://www.cs.berkeley.edu/~padmanab/papers/masters-tr.ps

The original idea was inspired by a paper at the June 1994 USENIX,
by James Griffioen and Randy Appleton, which described a predictive
prefetching scheme for use in a file system.

Concept #1: the server can observe request patterns from individual
clients and maintain a database of conditional probabilities: for
example, if a given client retrieves URL X, what is the probability
that within its next M retrievals, it will ask for URL Y?  (Conceptually,
this is a big square array, but it's probably quite sparse for small
values of M, and so it is best represented as a graph.)  Clearly, X
and Y would have to come from the same server (because the server
cannot observe other retrievals).

Example: if a client retrieves, say, http://www.yahoo.com/, there's
a good chance (say, 0.4) that the next request from that client to
that server will be for http://www.yahoo.com/images/main.gif, since
that is an inlined image in the document.  The probability is less
than 1.0, because the client may well have main.gif in its cache.
Another link with high probability, say 0.3 (I'm making up these
numbers!) is http://search.yahoo.com/bin/search, and the remaining
links on that page probably have fairly low probabilities.

Since the server sees requests *after* any client or proxy caches,
the probabilities it constructs are "correct" for use by caching
clients.

Summary of concept #1: Based on behavior of all previous clients,
the server can predict the next-fetch behavior of the current client.
Only servers can observe enough different clients to build a useful
probability table.

Concept #2: the decision of whether or not to prefetch should belong
to the client.  The client will probably have many of the high-probability
objects, such as logos and backgrounds, in its cache, and so we should
not waste network time pre-fetching potentially cached objects.  The
client also is the only thing that knows whether the user is sitting
and thinking (i.e., time for a prefetch) or has already chosen another
link (don't slow things down with a prefetch).

Summary of concept #2: Only the client can decide whether prefetching
is worth doing.

Concept #3: since the server makes the predictions and the client
acts on predictions, the protocol must provide a way for the predictions
to get from server to client.

So, here's a rough sketch of the proposal:
	(1) *after* sending an HTTP response, the server then sends
	some number of predictions, ech consisting of:
		(URL, probability, cache-validator, length-estimate)
	The length-estimate field allows a client with a slow link
	to decide whether it is worth prefetching.  The cache-validator
	can be used to avoid fetching objects that have not been
	updated since they were cached.

	(2) The client goes through the list of received predictions,
	tosses out the ones it has in its cache, and also the ones
	whose probability is below a user-settable threshold or whose
	length is too large.  If the user has not made another click,
	the client software sends a "PREFETCH" request, which looks
	and works exactly like a "GET" except for one thing: if the
	user wakes up and asks for a URL (other than one being
	prefetched), the client software immediately aborts the
	prefetch in progress (this probably requires the use of
	the TCP Urgent-pointer mechanism, as in Telnet) and then
	GETs the URL the user really wants.  This means that the
	prefetching mechanism should never add much latency, although
	it may soak up a lot of otherwise unused bandwidth.
	
	The server can adjust the amount of prefetch traffic it
	receives by changing the threshold for the predictions it
	sends to the clients.  A busy server would only transmit
	predictions with probability > 0.999 (say); a bored server
	might send predictions with probability > 0.1 (say).

Sorry if this is too speculative for this group.

-Jeff

Received on Tuesday, 5 September 1995 15:58:11 UTC