Design Considerations

Once we were confident that sending deltas could often reduce bandwidth requirements and/or client-observed latency of Web access, we had to consider two issues. One was what the architecture of a delta-based system would be. We rejected any scheme that would require changes to HTTP or to existing content providers, though we later learned that HTTP/1.1 will support a PATCH directive to allow efficient uploading of changes to shared documents. Instead, we settled on a proxy-based architecture in which the browser connects to a proxy on the same machine (the client proxy), and that proxy in turn connects to a server proxy on a well-connected host. We have control over both of these proxies; in fact we use a common source code base for them, though that is not necessary. The design of the proxies is covered in greater detail in Section 4.2.

The second open issue was how the deltas would help when the user's machine does not store an old version of the page. If the well-connected proxy has many clients, or can talk to a nearby proxy that does, it may have fast access to a cached copy of the requested page. When that page is current, nothing need be done other than sending the cached copy over the phone line. If it is stale, however, there might be an opportunity to use deltas after sending the stale data.

In fact, one might expect the server proxy to handle a number of clients and to keep multiple versions of each document in its cache. Sometimes a client's request will specify a version which the caching proxy has, and then only a delta needs to go back over the slow link. Other times, the server proxy will not have the same version cached as advertised by the client in which case it will try to utilize the time by sending in the stale copy it has and subsequently sending the delta. Since in the latter scenario the benefit is potentially lower, especially when is not very large, we may bias the system so that it hits the first scenario more often than the second. This may be brought about by auxiliary mechanisms like prefetching during idle times to keep the client and server proxies' caches in sync.

In total, there are numerous ways in which the optimistic delta mechanism can improve the efficiency of WWW access:

• The client and server proxies may share an out-of-date version. Consider the case when the client proxy sends an If-modified-since request with a No-cache directive to the proxy, which caches the same version, and assume that the page has been modified on the content provider site. In this case, the proxy obtains the page, computes the delta and, if it is smaller than the whole page, sends the delta instead of the whole page to the client. Thus, the demand for bandwidth of the (slow) link to the client is decreased. Again, we refer to this case as a ``simple delta,'' which is less ``optimistic'' than others: it only relies on the delta being small enough to be beneficial but does not risk transferring useless data.
• The server proxy may have the current version, but the client proxy wants to check the validity of its own cached copy with the content provider. Assume the client sends an If-modified-since request with No-cache to the proxy server, which caches a newer version that is the same as the version on the content provider site. In this case, the proxy immediately sends its copy to the client (marked as Stale); in parallel, it sends an If-modified-since request to the content provider, verifies that its copy is actually current and sends a null delta to the client. The browser can display the page as soon as the conditional GET returns via the server proxy, rather than having the newer contents of the page transferred starting then.

  The same latency reduction applies if the client has no cached copy but requests the most current version of a page, since the server proxy can send a Stale copy and then confirm that the copy is current after its own If-modified-since request.

• The server proxy may have a newer version than the client, as well as the client's cached version. Assume the client proxy asks the server proxy for a page that the client has cached, and the server's copy is more recent but is not necessarily the most current version. The server can respond with a delta against the client's version. If the page is out of date or the client specifies that the cache be bypassed, the content provider is consulted and a second delta can be sent if needed.
• The client and server proxies may share a current version of an ``uncacheable'' page, one that must be retrieved directly from the content provider on each access. Our system permits the client and server proxies to cache such pages as a basis for deltas between versions of a page, while ensuring correctness by providing the browser with the most current version every time. The server proxy can determine that the page is unchanged (using a regular GET over the high-speed network and comparing the contents with the cached version) and notify the client proxy to use the cached version rather than transferring the page over the low-speed network. Note that while other systems do this for cacheable pages, ours does this even for uncacheable ones as far as the slow link is concerned, while taking advantage of deltas when the differences are small.