Prefetching Brand-new Documents for Improving the Web Performance

Suyoung Yoon <syyoon@kt.co.kr>
Eunsook Jin <ejin@kt.co.kr>
Jungmin Seo <jmseo@kt.co.kr>
Ju-Won Song <jwsong@kt.co.kr>
Multimedia Technology Research Lab., Korea Telecom
Republic of Korea

As the World Wide Web has grown in popularity in recent years, much work has focused on reducing the Web traffic. Caching has proven a useful technique for improving the Web performance by reducing the network traffic. But, several recent studies show that the maximum hit ratio achievable by any caching algorithm is only about 30% to 50%. Therefore various research efforts have been performed on further increasing the hit ratio. One of them is prefetching documents before actual client requests. In this paper, we propose a new prefetching approach which combines the server's knowledge of brand-new(recently created or modified) documents with client behaviors. The results of trace-driven simulations show the performance improvement by reducing access latency without increasing network traffic and server load significantly.
 

Table of Contents

• 1. Introduction
• 2. Related Work
• 3. Prefetching Brand-new Documents
• 3.1 Approach
• 3.2 Collecting Brand-new Documents
• 3.3 The Effects of Proxies
• 3.4 Relating with Push technologies
• 4. Experiments
• 4.1 Environments
• 4.2 Results
• 5. Combining Our Method with Other Prefetching Methods
• 6. Conclusions
• 7. References

1. Introduction

With the prolific growth of the World Wide Web in recent years, much work has focused on improving the Web performance. Caching is a proven technique for reducing the latency perceived by Web clients[1,4,7,9,13,14]. The fundamental concept of caching is the intermediate storage of copies of popular Web documents close to Web clients. Caching is effective because many Web documents are requested more than once, and it can also decrease network traffic and reduce server load. But, several recent results suggest that the maximum hit ratio that can be achieved by any existing caching algorithm is usually no more than 30% to 50%, that is, regardless of the size of the cache and the caching scheme in use, one out of two documents cannot be found in the cache[1].

Therefore various research efforts have been performed on further increasing the hit ratio. One of them is anticipating future document requests and then prefetching the documents in a local cache before actual client request. In this paper, we propose a new prefetching approach which combines the server's knowledge of brand-new(recently created or modified) documents with client behavior. Previous prefetching methods need to examine and analyze the log file of Web server to predict future client requests. This may result in performance degradation because log files, in general, have enormous number of records. Instead, our brand-new approach does not use the access log but exploits the tendency of web clients to get Web documents.

This paper is organized as follows. In Section 2, we review related work on the Web prefetching. The detail description of our prefetching method is given in Section 3. Section 4 shows experimental results of our prefetching approach followed by a discussion of combining our scheme with other methods. This paper concludes with a summary of results in Section 6.
 

2. Related Work

Prefetching complements the research in caching, since all benefits of prefetching are in addition to those of caching. While caching attempts to provide fast access to a document from the second time it is accessed, prefetching provides fast access to a document at the first time it is accessed. Moreover, the already existing infrastructure for caching can be exploited for prefetching.

The research area of Web document prefetching is rather new and the research is currently being actively performed[2,3,6,8,10,11,12]. Bestavros implemented a system in which the server responses to a client request with, in addition to the requested resource, a list of related resources as monitored by the server[2,3]. Related resources are determined from the resource dependencies based on the previous resource requests to the server. Wachsberg et al. proposed a prefetching scheme based on the past user behavior[12]. They developed a client-based approach whereby each proxy keeps a list of documents needed by its clients, and it decides which of them to prefetch. In comparison to other prefetching approaches, they did not utilize the server information.

Hine et al. investigated ways of exploiting knowledge about client behavior to improve the Web performance[6]. The knowledge they used includes dependencies between resources and general knowledge of each client's behavior. They explored two directions for making use of this information. One of the directions examines combining knowledge of client behavior with resource dependencies to reduce latency by prefetching selected resources. The other direction use knowledge of dependencies to influence cache replacement decisions.

Markatos et al. proposed the Top 10 approach to prefetch documents, which combines the server's active knowledge of the most popular documents with client access profiles[8]. In this mechanism, if a client requests a document, the server sends the requested document and the most popular documents to the client according to the client access profiles. Contrary to the previous proposed sophisticated prefetching algorithms, their approach uses a simple and easy-to-calculate metric.

While most of previous developed prefetching methods need to examine server logs to anticipate clients future requests, our Brand-new approach does not have to access server logs. The detailed description of our proposed prefetching method is given in the next section.
 

3. Prefetching Brand-new Documents

This section proposes our new prefetching method. Section 3.1 describes the basic idea and implementation details of the method. Section 3.2 explains how to collect brand-new documents. The effect of proxies is given in Section 3.3. In Section 3.4, we describes the relation with push technologies of our proposed prefetching method.

3.1 Approach

Suppose a customer goes to the video shop to rent some video tapes. In the aspect of the client behavior, we may classify the clients as following three types.
 
• Type 1 : The client is looking for the "best sellers" corner at the shop to find the most popular video tapes.
• Type 2 : The client is looking for the "golf training" video tapes because he(or she) likes to play golf and wants to improve his(or her) golf skill with the aid of the training video.
• Type 3 : The client is looking for the recently-arrived new video tapes at the shop. He(or She) is a video-watching mania, so there are few of video tapes at the shop that he(or she) has not watched.


We believe that the above classification can be easily applied to Internet users. When a user of type 1 visits internet game sites, he(or she) tries to download the programs that are the most popular. The users of type 1 are usually beginners of that area. The Web sites help the clients find the programs by listing game programs along with their popularities. Top 10 approach[8] is appropriate for the type 1 clients since it prepares popular documents before actual client requests.

Suppose someone visits the 'infoseek' search engine to get information about 'push' technology. If he(or she) enters the word 'push' as the keyword and clicks the 'search' button, the search engine will show the items related to the keyword. Each item listed has a brief description and a link from which detailed information can be obtained. The order of the link is determined by the popularity and quality of the information. Then the client usually clicks the first few items. Bestavros[2,3] and Hine[6] exploited this tendency of type 2 clients. That is, clients of the type 2 usually try to find documents related with a subject.

Finally, let's assume someone visits the 'ESPN' Web site to see today's NBA scores or 'dilbert.com' site to see today's cartoons. Similarly, when someone visits the 'Amazon' bookstore to get some books, he usually clicks the links highlighted by 'New' icons. We catch the idea of prefetching brand-new documents by considering these kinds of Web clients. We believe that frequent users are more likely to get the up-to-date information from the Web.

The key issue of prefetching is anticipating future user needs. But it is difficult to guess the user behaviors, since no program can predict the future. Most of the existing solutions predicting future user requests are based on the previous access patterns of Web clients by analyzing the access log of the web server. Instead, our approach does not use the access log but exploits the tendency of web clients to get Web documents.  As in other prefetching methods, we also assume the use of proxies that manage the cache and aggregate requests to the server.  Generally, web clients, who frequently use the internet, are trying to get the up-to-date information from the Web. Therefore, in our method, the web server keeps the set of Brand-new documents, SN, which have been modified or created recently. On receiving a request from a client through a proxy, the server sends both the requested document and SN to the proxy. The proxy delivers the requested document to the client and stores SN in the cache using its own caching policy. The size and contents of documents to be prefetched are determined by the cooperation of the client and the server.

Figure 1 shows the basic architecture of our brand-new prefetching approach. Two entities are added to the typical Web client/server environment. Client agent, on the client side, receives brand-new documents from the Web servers and caches them. On the server side, brand-new agent is responsible for collecting the brand-new documents. The circled numbers in the figure represent steps of information or request flow. When a Web client requests a URL, the Web browser makes the http request to the Web server via the client agent(step 1). The client agent catches the request and examines whether the request can be served from its cache of prefetched documents. If client agent finds the document in its cache, it will serve the request from its cache(step 2). Otherwise, it forwards the request to the Web server in the same way of an ordinary http request(step 3). After receiving http request, the Web server sends brand-new documents prepared by brand-new agent as well as the requested document to the client agent(step 4 and 5).

When the client agent receives results from the Web server, it serves the http request initiated by the client(step 6) and also saves brand-new documents from the server into its local cache(step 7). The cache can be operated by one of many existing cache replacement policies. We use LRU for experiments, most popularly used, as the replacement policy.


Client side                       Server side

Figure 1 : Basic flow of Brand-new prefetching.

The performance of basic implementation can be enhanced by adopting Web caching policies like the piggyback caching algorithm[7]. Using the piggyback approach, when a client makes a http request, client agent piggybacks the list of its cache contents as part of the request. In response, the Web server does not send brand-new documents that are contained in the piggybacked list, this can result in reducing the network traffic.
 
 

3.2 Collecting Brand-new Documents

This section explains ways of collecting or preparing brand-new documents. Our approach, in the same way of other prefetching methods, does not consider dynamic http requests that are required to call the cgi programs. That is, we only deal with the client request of static HTML documents. The role of brand-new agent is to collect new documents in advance of client requests. The number of documents to be collected will be initially determined by system parameters of the Web server. This number would be changed according to client behaviors. The agent periodically searches for new documents at document directories of the Web server. These directories can be easily obtained in the configuration file of the Web server("obj.conf" in the case of Netscape Web server).

Another method of collecting brand-new documents is to create a special directory for them. When Web server applications add(or modify) documents, they put the documents under this directory. Then, brand-new agent does not have to search for whole directories managed by the Web server, instead, the Web server considers documents under the directory as 'brand-new'.
 

3.3 The Effects of Proxies

Web clients usually make a small number of requests to each server. If a client is going to request only one document from a server, prefetching is worth nothing. A proxy acts an intermediary between potentially hundreds of clients and remote Web servers by funneling requests from clients to various servers. If clients go through the proxy, prefetching or caching documents at the proxy may improve performance significantly, since documents prefetched on behalf of one client may also be used by other clients as well. And the proxying can be implemented in multi-level framework. That means, each proxy may have roles as a client and a server at the same time. For example, the first-level proxy plays the role of the server for the Web client because it serves the client request. But in the view point of second-level proxy, the first-level proxy is a client which sends document requests to the second-level proxy. This applies to the second-level, the third-level proxies, and so on.

With slight modification of the client agent from the basic architecture of the brand-new approach, our prefetching method can be easily extended to the multi-level proxying structure. On each level, client agent, Ci, cooperates with the proxy to prefetch documents from the next level client agent, Cj, where Cj acts as a server to Ci and a client to the next level proxy.

3.4 The Relation with Push Technologies

Most Web caching systems in use today are demand-driven from clients. That is, the caches are passive, and documents are retrieved or validated when requested by a client. On the other hand, using the prefetching, documents are retrieved to clients without client requests. In that meaning, prefetching approach is similar to the push technology, where the delivery of information on the Web appears to be initiated by the information server rather than the information user or client. The difference between them is that push clients explicitly designate the documents they want to retrieve before the actual request.

In the push environment, documents which are moving through the network are almost recently created or modified. Therefore, our brand-new prefetching method will show much higher performance in this environment.
 

4. Experiments

Section 4.1 explains how to simulate our proposed prefetching method and Section 4.2 shows results of the simulation.

4.1 Environments

To test our ideas, we adopt the trace-driven simulation using server trace logs. Remember the trace logs are only used in the simulation study, that is, our prefetching approach does not need server logs. The trace logs used are from

    KTRDG(Korea Telecom Research and Development Group) (rcunix.kotel.co.kr) : Traces from KTRDG's homepage

We know that it is important to use traces from a variety of sources, since different server traces display access patterns from different client bases. But, there is a limitation to evaluate performance of our prefetching approach using the trace-driven simulation. That is, we need additional information, the set of brand-new documents, to simulate our approach. But those documents cannot be obtained from trace logs. To get the set of brand-new documents, we should access whole directories that the Web server manages. We used trace logs during one week of about 500,000 requests. We preprocessed the original traces and removed requests to "cgi" programs.

We use the hit ratio and traffic increase as performance measures in our experimental evaluation. Hit ratio is the ratio of requests that are served from prefetched documents to total requests. The higher this ratio is, the lower the client latency and the server load. Prefetching approaches inherently impose the traffic increase by unsuccessfully prefetched documents. Since no program can predict the future, some of prefetched documents will not be actually requested by clients, and thus should not have been prefetched in the first place.
 

4.2 Results

Figure 2 shows that hit ratios of the LRU cache algorithm and our prefetching method as a function of the cache size which is relative to the size of brand-new documents to be prefetched. We can see that as the cache size increases, hit ratios of the two approaches also increase. And we can notice that hit ratio of our brand-new prefetching approach is higher than that of the caching only, which is as expected. From the graph  we see that to achieve the performance improvement, the cache size should be at least twice the size of  documents prefetched.

Figure 3 reveals that results of the traffic increase as a function of the cache size. The traffic increase is mainly caused by unsuccessfully prefetched documents and the piggyback overhead for delivering the cache information to the server.



Figure 2 : Hit ratio without proxy.    Figure 3 : Network traffic.

Figure 4 and 5 plot hit ratios and traffic increase for proxies as a function of the cache size. We see that hit ratio of the prefetching using proxy is raised to about 40% comparing to the Figure 2. But there are only slight changes on the traffic increase.
 






      Figure 4 : Hit ratio using proxy.      Figure 5 : Network Traffic using proxy.

5. Combining Our Method with Other Prefetching Methods

Since all clients do not tend to get the newest document(clients of type 1 or type 2 in section 3.1), we also propose an extension of our method, which combines our approach and existing prefetching method, the TOP 10 approach[8] which uses the access log of web server. The TOP 10 approach sends the most popular documents of the server to clients. The extension examines the client's access behaviors and calculates hit ratios, HB and HT which represent the hit ratios of our method and the TOP 10 method respectively. According to the hit ratios calculated, the server dynamically determines the set of documents to be prefetched in advance of the actual request. The portion of documents to be selected by a method among total documents to be sent to the client is proportional to the hit ratio of the corresponding prefetching method. This adaptation will further increase the hit ratio achievable by any of the methods. The adaptation to prefetch documents SN is formalized as follows.

    SN = {Set of the first NB elements from brand-new  prefetching documents}
         UNION
         {Set of the first NT elements from Top-10  prefetching documents}

          where, NB = NP * HB / (HB + HT)
                 NT = NP * HT / (HB + HT)
                 NP = The total number of documents to be prefetched
                 HB = The hit ratio of the brand-new prefetching approach
                 HT = The hit ratio of the TOP 10 approach

NP can be determined by analyzing client behaviors. For the frequent clients, its value will be large. On the other hand, it will be small for the occasional clients. The HB and HT, which control the prefetching mode, can be also defined as system parameters of the Web server according to the tendency of clients who access the server. If most clients are of type 3, HB will be relatively large.
 

6. Conclusions

In this paper, we present a new prefetching technique which combines the server's knowledge of brand-new documents with client behaviors.

To support prefetching in our mechanism, the HTTP protocol between Web clients and Web servers needs to be enhanced to allow servers to deliver brand-new documents in addition to the requested documents to the client agent.

Our simulation results show that a substantial reduction in latency perceived by clients can be achieved at the cost of a similar increase in the network traffic. Since the retrieval time of a document includes a substantial startup latency, prefetching is more effective in reducing the access time than just increasing the bandwidth.

The brand-new prefetching we propose is specially appropriate for the Web servers such as news web sites like CNN and electronic shopping malls like Amazon, where documents in the server are frequently created or modified and Web clients have tendency to get up-to-date information. In addition, our prefetching method will show much higher performance in the push environment where clients usually want to get the latest information.

We leaves experiments for combining our method with existing prefetching methods as further study.
 

7. References

1. M. Abrams, C.R. Standridge, G. Abdulla, S. Williams, and E.A. Fox. "Caching Proxies: Limitations and Potentials," In Proceedings of the Fourth International WWW Conference, 1995.
2. Azer Bestavros. "Speculative Data Dissemination and Service to Reduce Server load, Network Traffic and Service Time for Distributed Informaion Systems," In Proceedings of ICDE'96:The International Conference on Data Engineering, March 1996.
3. Azer Bestavros. "Using Speculation to Reduce Server Load and Service Time on the WWW," In proceedings of CIKM'95:The Fourth ACM International Conference on Information and Knowledge management, November 1995
4. Pei Cao and Sandy Irani. "Cost-aware WWW Proxy Caching Algorithms," In proceedings of the 1997 USENIX symposium on Internet Technology and Systems, December 1997
5. Lara D. Catledge and James E. Pitkow. "Characterizing Browsing Strategies in the World-Wide Web," In Proceedings of the Third International Conference on the World Wide Web, Darmstadt, 1995.

http://www.igd.fhg.de/www/www95/proceedings/papers/80/userpatterns/UserPatterns.Paper4.formatted.html.
6. John H.Hine, Craig E. Wills, Anja Martel, and Joel Sommers. "Combining Client Knowledge and Resource Dependencies for Improved World Wide Web Performance," In  proceedings of  INET'98:Internet Global Summit, July 1998
7. Balachander Krishnamurthy and Craig E. Wills. "Study of Piggyback Cache Validation for Proxy Caches in the World Wide Web," In Symposium on Internet Technology and Systems. USENIX Association, December 1997.

http://www.usenix.org/publications/library/proceedings/usits97/krishnamurthy.html.
8. Evangelos P. Markatos and Catherine E. Chironaki. "A Top 10 Approach for Prefetching the Web," In proceedings of  INET'98:Internet Global Summit, July 1998
9. Jeffrey C. Mogul. "Hinted Caching in the Web," In Proceedings of the 1996 SIGOPS European Workshop, 1996.

http://mosquitonet.stanford.edu/sigops96/papers/mogul.ps.
10. Venkata N. Padmanabhan and Jeffrey C. Mogul. "Using Predictive Prefetching to Improve World Wide Web Latency," Computer Communication Review, 26(3):22-36, 1996.

http://www.acm.org/sigcomm/ccr/archive/1996/jul96/ccr-9607-mogul-padmanabhan.ps.
11. Joel Sommers and Craig E. Wills. "Prefetching on the Web Using Client and Server Profiles," Technical Report WPI-CS-TR-97-2, Computer Science Department, Worcester Polytechnic Institute, June 1997.
12. Stuart Wachsberg, Thomas Kunz, and Johnny Wong. "Fast World Wide Web Browsing over Low-bandwidth Links," 1996.

http://ccnga.uwaterloo.ca/~sbwachsb/paper.html.
13. Duane Wessles, "ICP and the Squid Web Cache,"

http://www.nlanr.net/~wessels/Papers/icp-squid.ps.gz
14. Lixia Zhang, Sally Floyd, and Van Jacobson. "Adaptive Web Caching," In the 2nd Web Caching Workshop, Boulder, Colorado, June 1997.

http://ircache.nlanr.net/Cache/Workshop97/Papers/Floyd/floy.ps.