Ken-ichi Chinen <k-chinen@is.aist-nara.ac.jp>
Suguru Yamaguchi <suguru@is.aist-nara.ac.jp>
Nara Institute of Science and Technology
Japan
As the number of World Wide Web (WWW) users grows, the perceived latency of the WWW is becoming an important issue. The retrieval time of WWW resources depends on several factors such as network bandwidth, propagation delay, and host performance of both servers and clients. The network bandwidth and host performance can be improved by upgrading, but the propagation delay cannot be eliminated.
We have focused our attention on prefetching technology for reducing WWW latency. This technology aims to reduce the propagation delay by separating the request and the utilization. We have developed a prefetching scheme called interactive prefetching and have implemented a proxy server with this scheme. This proxy collects referenced resources in each page client retrieved. This paper shows the design and implementation of this prefetching proxy server. Furthermore, we present its performance evaluation conducted on our campus network.
A resource retrieval on the World Wide Web (WWW) starts with a request issued by a client. The WWW server replies with any requested resources. The client parses this response and displays it. This interaction often takes a long time, which is called the WWW latency. Large WWW latency may cause user discontent.
WWW latency depends on network latency and performance of both servers and clients. Network latency depends on network bandwidth and propagation delay. Network bandwidth and host performance can be improved by upgrades. As the costs of network connectivity and computer performance have been decreasing dramatically, it will be easier to get broad-bandwidth networks and high-performance computers in the near future. But the propagation delay cannot be eliminated because the speed of light is constant.
One solution is caching, a popular technology of WWW proxy servers. A cache stores resources that have been accessed recently. Therefore, caching improves retrieval time of frequently accessed resources. But its effect on WWW latency is small because frequently retrieved resources account for few retrievals. Several papers reported that the hit-rate of the caching proxy server is 30%-50% [1] [2].
An alternative solution is prefetching. If one fetches necessary resources before the client's requests and passes them to the client, the client can retrieve resources in a short time. Several researchers have designed a statistical prefetching scheme [3] [4]. In this scheme, the system retrieves popular pages based on observation of the client's access patterns. However, there are several drawbacks. Because frequently retrieved resources are only a small fraction of all retrievals, there is no way to guess the client's next request by any statistical method. User interests tend to change rapidly. To get a high hit rate, this scheme requires a long observation time. It is difficult to catch new trends immediately. Although prefetching improves the hit rate of frequently retrieved resources, its overall reduction of WWW latency is small.
We have developed another prefetching scheme called interactive prefetching. In this scheme, the system gathers references by parsing Hypertext Markup Language (HTML) in the page and collects several referenced pages with each request. This scheme reduces much of the WWW latency.
We have designed and implemented a proxy server with this scheme, which is called an interactive prefetching proxy server. Like the caching proxy server, this proxy prefetches and stores referenced pages. It also shares the result of the prefetching among clients.
The WWW can be considered to be a page-oriented service. A page consists of texts, in-line images, and references to other pages (Figure 1). A page is written in HTML [5]. In interactions of the WWW, the client requests HTML resource and in-line images and displays them as a formatted page. The prefetching system should act in a page-oriented manner.
Users click highlighted text on the page. This means that many requests are to retrieve referenced resources, so prefetching of referenced pages makes for faster retrieval at the client site. Therefore, our prefetching scheme is designed to get these referenced pages.
The prefetching is not a recursive copying of all resources. The prefetching system gathers references to other pages by parsing the HTML of the client's retrieval page and collects referenced pages (HTML and in-line image) at each request of the client (Figure 2). For example, If page A of Figure 2 is retrieved, the prefetching system collects page B and C. Collection of page B means fetching B and in-line images of B (b1, b2, and b3). Thus, the system collects B, b1, b2, b3, C, c1, and c2 when page A is retrieved. List 1 shows a fundamental algorithm of this scheme.
The system should prefetch target pages in a short time until the next request, because the WWW is an interactive service and the interval of its requests is short. In addition, fetching of many resources puts heavy load onto the host. So an effective selection method for prefetching targets is required. We have designed a scheme to prefetch several referenced pages at the top of the retrieval page.
An alternative method is to select prefetching target resources by contents or attributes (content length, type, or date). But this method is not practical, because the prefetching system cannot know these contents and attributes without fetching.
Figure 1: The WWW consists of pages
Figure 2: The prefetching system fetches many resources
procedure Prefetching(base_page : URL)
var
A, I : URL;
rpage_set, image_set : set of URL;
begin
{gather A-tag by parsing of HTML }
rpage_set := GatherReferences(base_page);
foreach A in rpage_set do
begin
{get HTML part of referenced page via HTTP }
Get(A);
{gather IMG-tag by parsing of HTML }
image_set := GatherImages(A);
foreach I in image_set do
begin
{get in-line images of referenced page via HTTP }
Get(I);
end;
end;
end;
List 1: A fundamental algorithm of the prefetching scheme
We have designed an interactive prefetching mechanism as one of the functions of the proxy server, after considering the following points:
Like the caching proxy, the mechanism gets and stores referenced pages in the client's retrieved pages. Clients can access the prefetching proxy by the same way as the caching proxy. With the prefetching scheme on the proxy server, the result can be shared among clients.
We have simulated a performance of the prefetching scheme using the access log of the proxy server located in the campus network of the Nara Institute of Science and Technology (NAIST).
We have calculated hit rate as the measure of the scheme's performance, because it is difficult to calculate actual latency and the response time. When a request hits a cache, the proxy can reply immediately. As the hit rate increases, the mean retrieval time decreases.
We collected references and calculated the hit rate using 8,519 clients requests in the log. Figure 3 shows the relation between the hit rate and the number of prefetching targets. It shows three phenomena:
If the prefetching system collects all referenced pages included in
clients' retrieved pages, we will get a 69% hit rate. However, the
prefetching system puts a heavy load onto the host. As the number of
prefetching targets increases, the hit rate and the load increase.
Therefore, we should consider the balance between the load and the hit
rate.
Figure 3: The hit rate vs. the number of prefetching targets
This section describes a implementation of the interactive prefetching proxy server called the WWW Collector (Wcol) [6]. The Wcol runs on most popular UNIX platforms. To get around the load problem, the Wcol is separated into several processes.
We have evaluated the performance of the Wcol in an actual environment. We replaced the proxy server with the Wcol in the campus network of NAIST (Table 1). The Wcol is configured to prefetch 10 referenced pages in the requested page and 10 resources (in-line images) included in the referenced page. Table 2 shows the consequence of the operation.
The prefetching proxy has a higher hit rate than the caching proxy. We observed the count of cache hits and cache misses and how the cache was created, at the prefetching proxy. Hits on cache results were counted as hits of the caching proxy. Hits on both prefetching results and caching results were counted as hits of the prefetching proxy. The hit rate of the prefetching proxy was 64.4%, 1.67 times higher than the caching proxy. In addition, the effect of the prefetching mechanism appears in a shorter time (Figure 4).
The prefetching proxy makes faster retrievals than the caching proxy. We observed retrieval time at the prefetching proxy. The retrieval time of remote resources at the proxy was used as the retrieval time at the client because LAN is much faster than WAN. The prefetching proxy is 2.46 times faster than the proxy server without caching and is 1.62 times faster than the caching proxy (Figure 5).
A drawback of prefetching systems is the large traffic. The traffic of the interactive prefetching proxy server is 2.81 times larger than the proxy server without caching and 4.12 times larger than the caching proxy (without prefetching) (Figure 6).
Figure 7 shows the frequency of resources. It shows that recyclable resources account for only a small part of retrievals into the WWW.
| Machine | SGI Indigo (IP20) |
|---|---|
| OS | IRIX 5.3 |
| CPU | R4000 |
| Memory | 80MB |
| Cache | 300MB (disk) |
| I/F | Ethernet |
| Observation period | 5 weekdays |
|---|---|
| The number of accesses | 55,085 |
| Retrieval time w/o cache | 15.55 sec (average) |
| Retrieval time w/ cache | 10.28 sec (average) |
| Retrieval time w/ prefetch | 6.33 sec (average) |
| Hit-rate w/ prefetch | 64.4% |
| Hit-rate w/o prefetch | 38.5% |
| Traffic w/ prefetch | 1.22GB |
| Traffic w/o cache | 434.05MB |
| Traffic w/ cache | 296.43MB |
Figure 4: The hit rate in an actual environment (the campus
network of NAIST)
Figure 5: The retrieval time comparison among schemes
Figure 6: The traffic comparison among schemes
Figure 7: The frequency of resources
Other efforts in latency improvement include batch prefetching schemes and hybrid systems of caching and mirroring. The batch prefetching scheme collects frequently accessed pages during off-peak times [4]. The hybrid system caches and mirrors frequently accessed pages [3]. As mentioned above, most Web items are not frequently retrieved and these systems have little effect on resources not frequently used. Therefore, the effect of these schemes on reducing WWW latency is small.
Some prefetching systems are designed to prefetch at the client [7] [8]. Because a prefetching scheme on the client cannot share results among clients, these systems will generate larger traffic than the prefetching mechanisms on proxy servers.
We don't try to replace servers, clients, or protocols because replacements are difficult and require cost and time. However, there are many proposals for new protocols and modifications of both servers and clients [9] [10]. When these come into wide use, we can use them for prefetching.
We describe an interactive prefetching scheme for the World Wide Web to reduce the latency perceived by users. In this scheme, the prefetching system guesses the next request and prefetches several referenced pages on the page the client retrieves.
We have developed a prefetching proxy server with an interactive prefetching scheme called the Wcol. This approach enables sharing results of prefetching among clients and requires no modifications of servers or clients.
By simulations using actual requests, we have found that the hit rate of the prefetching proxy increases as the number of prefetching targets increases. But the hit rate cannot reach 100% with any type of prefetching, because the hit rate curve is not linear and it converges at a certain point.
We have applied the prefetching proxy to our campus network. This experiment shows that the prefetching proxy has improved WWW latency and makes faster retrieval than the caching proxy.
We thank the testers and users of our system. Our test bed is supported by many organizations. The campus network and equipment are supported by the Information Technology Center of the NAIST. The external links of the NAIST are supported by the WIDE project and the Internet 1996 World Exposition. We thank Kazufumi Mitani and members of the WWW Cache Task Force of the WIDE project for useful comments on this research.
We also thank Tomomitsu Baba, Yukari Hada, Satosi Futenma, Youki Kadobayashi, Kazumasa Kobayashi, Kiyohiko Okayama, Hisakazu Hada, and Hiroyuki Inoue for useful comments on this paper.
The Wcol is published in WWW Collector Home Page for evaluation by other sites [6]. It is possible to get the Wcol from that page. This page shows the current status of the prefetching proxy server and related systems.
We have developed another prefetching system called the hybrid prefetching proxy server. Almost all prefetching systems must handle a large number of HTTP connections. The connections put a heavy processing load onto the host. In order to resolve this drawback, we have separated the prefetching engine from the proxy server and connected it as a sibling proxy server. The combination of the proxy server and the prefetching engine (a.k.a. catalyst) is called the hybrid prefetching proxy server. Because communication between the proxy server and the prefetching engine is done by the Internet Cache Protocol (ICP), the hybrid system can run with other hierarchical caching systems.