INET Conferences


Conferences


INET


NDSS

Other Conferences


[INET'98] [ Up ][Prev][Next]

WebHint: An Automatic Configuration Mechanism for Optimizing World Wide Web Cache System Utilization

Hiroyuki INOUE <h-inoue@is.aist-nara.ac.jp>
Takeshi SAKAMOTO <takesh-s@is.aist-nara.ac.jp>
Suguru YAMAGUCHI <suguru@is.aist-nara.ac.jp>
Nara Institute of Science and Technology
Japan

Yuji OIE <oie@cse.kyutech.ac.jp>
Kyushu Institute of Technology
Japan

Abstract

A distributed cache system for World Wide Web (WWW) infrastructure is introduced in order to reduce both network traffic and the latency of page retrieval for the users. In this kind of system, the administrators of cache servers must determine by themselves how and which neighboring cache servers should be incorporated, based on their level of expertise. However, it is very difficult for them to update the related management in response to changes in the state of the network and/or the neighboring cache servers in a dynamic and timely manner.

In this paper, we propose the use of the WebHint system, including "hint server," which will automatically update the information associated with neighboring cache servers in a way to reduce both the number of packets exchanged among cache servers and the response time for end users. We extended the ICP (Internet Cache Protocol; RFC 2186) messages between cache servers and the hint server to communicate with each other. We added three types of messages: "hint notification," "hint query," and "hint reply." When the cache servers have fetched or removed a WWW object from the cache, they notify the hint server of updates and details of cache contents. For this update, the ICP notification messages are used. Our extended ICP query message is used for searching the content database that the hint server is managing. In case a user accesses a WWW object via its local cache server, the cache server sends our extended ICP query message to the hint server. The hint server searches its contents database and then lets the cache server know which cache server has the object (or answers that no server has the object). The hint reply ICP message is used for this reply.

We've implemented the WebHint prototype and made a preliminary evaluation. The extended ICP message contains the cache status and detailed information about the object indicated by the URL. We also added the hint data on the payload of the ICP packet. We compared the cache system composed of a hint server and several cache servers with the conventional system composed of several neighboring cache servers. We received the same hit rate on each system. When a new cache server is added, we confirmed that the hint server then includes its information in the hint data and all cache servers working together. Similarly, when a cache server is out of service, it discards its related information. We measured the performance of the hint server itself. It shows that the hint server program requires significantly fewer resources on the computer compared with a WWW cache server program. Therefore a dedicated hint server can be easy to install even on a low-performance computer such as a PC Unix or old workstation.

Contents

Introduction

The WWW cache mechanism has been introduced and is widely used in the Internet to reduce WWW traffic as well as to reduce the amount of time that end-users spend waiting for pages to load [1]. The user sets the cache server as his proxy server and all the requests from the user are sent to the cache server. The proxy configuration can be automatically controlled on a recent WWW browser, once the user has set up the initial proxy configuration [2]. The distributed cache has been introduced in order to distribute the load or to reuse the cache contents mutually. In this kind of system, the administrators of cache servers have to determine by themselves how and which neighboring cache servers should be incorporated, based on their level of expertise. However, it is very difficult for them to update the related management in response to changes in the state of network and/or the neighboring cache servers in a dynamic and timely manner.

In this paper, we propose a distributed cache system that introduces the "hint server" which can grasp the status and the contents of cache servers. This system, named WebHint, will automatically update the information associated with neighboring cache and some cache parameters. We extend the ICP (Internet Cache Protocol) [3][4] messages between cache servers and the hint server to communicate with each other. By using a hint server, the cache administrator will only describe the hint server(s) as the information of cache structure in the configuration file at the beginning, instead of describing the relationship of some neighboring or parental caches and maintaining its information.

Management of distributed WWW cache server

Distributed WWW cache server

The first cache server introduced was the CERN HTTPD server [5] which stored recently accessed pages for subsequent use. When a user requests a URL (Uniform Resource Locator) [6], the WWW client does not send the request to the original WWW server that contains the requested data but to the cache server as the proxy server. If the WWW object specified by the URL is in the cache server, it sends the object to the client without access to the original WWW server in principle. The cache server is normally located at the local site of the clients or the network connected to the clients with a hi-speed line. Since the users' requests demonstrate a high degree of cohesiveness, both the traffic and the latency of page retrieval for the users are expected to improve.

In order to reuse or share the cache contents mutually, several cache servers can be organized to forward requests from one cache to another hierarchically using Harvest cache [7]. The squid cache derived from Harvest and developed at NLANR [8] is a major cache server for building the hierarchical cache system in the Internet and intranet. Cache servers exchange the information by means of ICP messages. If a cache server does not have the requested object specified by the URL, it sends inquiries to other cache servers and waits for the reply. If it receives a "hit" reply, it will retrieve the object to the cache that has sent the reply. If the time-out occurs while waiting for the reply, it retrieves the object according to the default rule. Another approach is to distribute the requests to several cache servers in a deterministic way by using URL hashing [9][10]. In this system, the requests with the same URL are always sent to a unique cache server that is calculated by URL string, so it is not necessary to send a ICP query message to other cache servers in the distributed cache system.

Management of cache structure

In the hierarchical cache system, the administrators must describe the cache structure in the configuration file. Furthermore, when the structure or the network status changes, they have to update the configuration file to keep the cache performance optimal in response to the change, based on their level of expertise.

In order to save a great deal of time, various systems are proposed. The squid group applies the ICP communication to the multicast IP packet. The cache administrator who wants to join a cache group specifies nothing but the multicast address assigned for the group. This does not require any administration to be performed. It is, however, difficult to control for a server joining the group and to prevent the reply packets from flooding on the network. Another approach is that a cache server gets the server list closer to it from a database using a WHOIS system [11]. The administrators register their server to the database beforehand. The WHOIS server only tells the list of cache servers and doesn't consider the cache contents on every cache.

WebHint system

System model

The WebHint system is composed of four components: original WWW servers, WWW clients including the browsers, cache servers, and hint servers (Figure 1). We've recently introduced the hint server in order to grasp the contents and status of cache servers and to reply to a query from the cache with the hint information about the object that the cache is going to retrieve. In our WebHint architecture, a hint server should be installed at the location where the hint server can handle ICP queries as much as possible, such as a backbone link concentration point or POP (point of presence) in AS, co-location point with external gateways in each organization, or even in IX (Internet eXchange).


Figure 1. System model

When the cache server has retrieved an object and stored it in the cache or removed an object from the cache, it will pass on the information about the object to the hint server with notification messages. The cache server on a WebHint system knows nothing but the hint server and sends the query messages about the object requested by the user only to the hint server(s) instead of sending to other cache servers, and it then waits for the reply message. Therefore, we expect the following advantages with the WebHint system:

Automatic configuration of cache structure and performance
The administrators of the cache server only describe the location of the hint server in the configuration, instead of describing a list of several neighboring cache servers and maintaining the list according to the servers or the network configuration that will be changed. Since it is possible for a cache server to follow the instruction from the hint server, the hint server can act as the filtering server that censors specific sites or URLs like WebSENSE [12].
Reduction of the number of ICP messages
The cache server sends the ICP notification and query messages only to the hint server. In comparison with the conventional cache systems (Figure 2(a)), our system can successfully reduce the number of ICP packets to approximately 4/2(n-1) that of the conventional ones, where n is the number of neighboring cache servers in the system (Figure 2(b)).


Figure 2. Comparison with ICP sequences

Improvement in the response time for users
In the conventional cache system, the cache server sends the ICP query messages to all neighboring cache servers and has to wait for the responses. In our proposed system, as the cache server only communicates with the hint server, it only waits for the response message from the hint server. It might be possible to optimize the parameters related to ICP communication such as time-out time to wait for the response. So the cache server can slightly improve the response time for end-users.

Protocol

We extend the ICP messages between cache servers and the hint server to communicate with each other. There are three types of messages we added: "hint notification," "hint query," and "hint reply." When the cache servers have fetched or removed a WWW object from the cache, they notify the hint server of updates and details of cache contents. For this update, the ICP hint notification messages are used. Our extended ICP hint query message is used for searching the content database that the hint server is managing. In case a user accesses a WWW object via its local cache server, the cache server sends our extended ICP query message to the hint server. The hint server searches its content database and then lets the cache server know which cache server has the object, or answers that there is no server with the object. The ICP hint reply message is used for this reply.

The sequence of the extended ICP messages is as follows:

  1. The client sends the request from the user to the local cache server.
  2. The local cache sends the ICP hint query message to the hint server(s).
  3. The local cache waits for the ICP hint reply message from the hint server(s).
  4. When the hint server receives the hint query message, it searches the database for the hint data that matches the query. If it can find it, it sends the ICP hint reply message with hint data back to the cache server. Otherwise, it sends the ICP hint reply message without hint data.
  5. The local cache will retrieve the object followed by the hint information in the reply message(s) and relay it to the client.
  6. If the object is cacheable, the cache server stores it in the cache and sends the ICP hint notification message to the hint server(s). The hint server that receives the notification message adds the information about the object to its database.
  7. If a time-out occurs while waiting for the reply message or there is no hint in the hint reply message(s), the cache server will retrieve the object in the default manner that is described in the cache configuration.
  8. When a cache server has removed an object from the cache, it also sends the ICP hint notification message to the hint server(s).
  9. The hint server should periodically check the hint database in order to purge the expired information. The purging is executed based on the object expiration date or the cache expiration date.

Redundancy and scalability

The hint server is not a concentrated server, nor a single server. The WebHint architecture provides an efficient and scalable environment for a distributed cache system. If the number of hint servers pointed by a cache server is more than one, all hint servers are identical for a cache server. So, when a hint server is down or unreachable, the cache will detect that it is down and work without it. Even if all hint servers are down, the cache will work as a single server, and the users will hardly notice the failure.

The hint server can be organized in a tree-like hierarchical structure. The notification or query messages sent to the hint server can be relayed to an upper server. You can imagine this behavior by contrasting the WebHint system with the routing mechanism of the Internet. The static configuration of neighboring cache servers corresponds to the static routing configuration, and the WebHint corresponds to dynamic routing such as RIP (Routing Information Protocol) [13].

Prototype and system evaluation

Implementation

We've implemented the WebHint prototype to verify the effectiveness of the distributed cache system. The hint server is written in C language and is running on BSD/OS2.1 of BSDI, IRIX6.3 of SGI, and Solaris2.5 of Sun. The cache server is modified by the existing squid cache server to communicate with the hint server and to follow the instruction with the hint data. The source code of WebHint version 1.0 consists of approximately two thousand lines in C language.

Figure 3. Extended ICP message format

We extend the ICP message for WebHint, because it is insufficient for the current ICP to inform the object information and the cache status to the hint server. The format of the extended ICP message for WebHint is shown in Figure 3. The first half of the message is compatible with the ICP message header defined in RFC 2186. The second half of the message is used to describe the object indicated by the URL and the hint data. We've added new ICP opcodes named ICP_OP_HNOTIFY, ICP_OP_HQUERY and ICP_OP_HREPLY, which respectively mean "hint notification," "hint query," and "hint reply." For each opcode, some subcodes are defined in order to indicate the kind of hint or notification, which is stored in the "Options" field in ICP. These opcodes are assigned in unused numbers in RFC 2186 and the squid system. In the hint query message, the fields concerning the object information have no meaning and are normally set to zero. These messages are sent by the UDP packet on the network as well as the current ICP.

The database of the hint server is designed with a tree structure whose key is a URL in order to add or delete the object quickly. To expire an old object periodically, another link structure exists in the database, whose link is designed with a linear list that is arranged with the order of the object expiration time in the cache.

Evaluation

Configuration of cache server

We verified the zero administration on the configuration of the cache structure. When there are five cache servers and two hint servers in a system, the configuration of host "cache2" on a conventional cache system is as follows:

    #          hostname     type            HTTP/ICP port
    cache_host cache1       sibling         3128 3130
    cache_host cache3       sibling         8000 8130
    cache_host cache4       sibling         3128 3130
    cache_host cache5       sibling         8888 3130

The configuration of a cache server on a WebHint system is the same as others:

    #          hostname     type            HTTP/ICP port
    cache_host hints1       hintserver      0    4649
    cache_host hints2       hintserver      0    4649

This management will reduce much of the time required for the initial configuration and usual administration.

When a new cache server is added, we confirmed that the hint server then includes its information in the hint data and all cache servers work in a cooperative way under the hint server. Similarly, when a cache server is down, the hint server stops including its information after a short period.

Cache utilization

We measured the cache utilization with and without the hint server (HS) on five neighboring cache servers by squid. Figure 4 shows the cache utilization (hit rate) for total client requests. "Hit rate" indicates the percentage of the requests satisfied by the local cache, and "Sibling hit rate" indicates the percentage of the requests satisfied by the other cache servers with an ICP query. From this result, it seems that there is hardly any difference in cache utilization between conventional caches and the WebHint system. The WebHint system, however, has the advantage of automatic configuration.


Figure 4. Cache utilization

Figure 5 shows the percentage that the time-out occurs on a cache server while waiting for an ICP reply from other caches or the hint server. In this measurement, since the excessive requests were arrived from the client to the cache servers on 12,000 to 16,000, the cache servers lost some ICP query messages from other caches or couldn't send the ICP reply message to them; thus, many time-outs occurred. Meanwhile, the cache server with the hint server rarely experienced a time-out. That may be because the hint server is dedicated to handle the ICP query and notification that can be handled more easily than HTTP requests on a cache server.


Figure 5. Time-out rate

Performance of hint server

Figure 6 shows the response time of a hint server and cache servers when it receives the ICP query messages. The response time also includes processing time of receiving message, searching and updating the database, and sending reply message. They ran on an IRIX6.3 of SGI O2 workstation with 64MB of memory. The cache servers sometimes took much time to respond, because the clients sent many requests and the servers became busy. Meanwhile the hint server kept a stable response time. This result indicates that the hint server we developed has quite a short response time and will satisfy the requirements of a cache server.


Figure 6. Response time

Conclusion and future work

We proposed the WebHint system which makes the administration of cache servers automatic and provides an efficient and scalable environment for a distributed cache system. According to the results of our experiment, the cache utilization on the WebHint system was the same as the conventional neighboring cache system, but the administrative time was significantly less. The hint server that is currently introduced in the WebHint system is a very light process for a computer, so it can be installed at many places along the network.

We are developing and conducting experiments on the WebHint system by applying it to the CacheBone in WIDE project [14] in Japan and implementing the protocol between hint servers. Through this experiment, we are trying to make its incremental improvements on the algorithm to optimize the time-out value to wait for the reply messages or to consider the current routing and the network topology with generating hint data. For its operation in a real environment, there remains the future extensions for the security facility, the filtering server, and well-organized GUI interfaces for operators.

Appendix

The current version of WebHint is available on our Web server:

http://shika.aist-nara.ac.jp/products/webhint/

The latest documentation and other related information are also available here.

Acknowledgments

The authors would like to thank the members of the WIDE project for having discussed the hint server and the WWW cache system.

References

  1. M. Abrams et al., "Caching proxies: Limitations and potentials," Proceedings of the 4th WWW Conference, Boston, pp. 119-133, Dec. 1995.
  2. Netscape Inc., "Navigator Proxy Auto-Config File Format," http://www.netscape.com/eng/mozilla/2.0/relnotes/demo/proxy-live.html, Mar. 1996.
  3. D. Wessels, K. Claffy, "Internet Cache Protocol (ICP), version 2," RFC 2186, Sep. 1997.
  4. D. Wessels, K. Claffy, "Application of Internet Cache Protocol (ICP), version 2," RFC 2187, Sep. 1997.
  5. The World Wide Web Consortium, "CERN httpd (W3C httpd)," http://www.w3.org/pub/WWW/Daemon/, Jul. 1996.
  6. T. Berners-Lee, L. Masinter, M. McCahill, "Uniform Resource Locators (URL)," RFC 1738, Dec. 1994.
  7. A. Chankhunthod et al., " A Hierarchical Internet Object Cache," Technical Report 95-611, Computer Science Dep., Univ. of Southern California, Mar. 1995.
  8. National Laboratory for Applied Network Research, "Squid Internet Object Cache," http://squid.nlanr.net/
  9. SHARP Inc., "Super Proxy Script," http://naragw.sharp.co.jp/sps/index.html, Aug. 1996.
  10. K. W. Ross, "Hash Routing for Collections of Shared Web Caches," IEEE Network Nev./Dec. 1997, pp. 37-44.
  11. Tohoku Univ., "whois Cache Map Database Information Service (in Japanese)," http://www.nemoto.ecei.tohoku.ac.jp/cache-tains/whois-cache-map.html, Jan. 1997.
  12. NetPartners Internet Solutions, Inc., "WebSENSE - Internet Screening System," http://www.websense.com/
  13. G. Malkin, "RIP Version 2 - Carrying Additional Information," RFC 1723, Nov. 1994.
  14. WIDE Project, "WIDE Project," http://www.wide.ad.jp/

Authors' information

Hiroyuki INOUE is a PhD candidate at the Graduate School of Information Science, Nara Institute of Science and Technology, and also works for Sumitomo Electric Industries, Ltd. His research interests include load-balancing of the distributed system and network security for the Internet.

Takeshi SAKAMOTO is a master's candidate at the Graduate School of Information Science, Nara Institute of Science and Technology. His research interests include the WWW cache system.

Suguru YAMAGUCHI has been an associate professor at the Graduate School of Information Science, Nara Institute of Science and Technology, since 1993. He received his PhD in engineering from Osaka University in 1991. He has also been a member of the WIDE Project since its creation in 1987, where he has been conducting research on network security systems for a wide-area distributed computing environment. His research interests include technologies for information sharing, multimedia communication, network security, and network management for the Internet.

Yuji OIE has been a Professor in the Department at the Computer Science and Electronics, Kyushu Institute of Technology, Iizuka, since 1997. He has also been a Professor of the Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma, since Aug. 1997. He received the BE, ME, and DE degrees from Kyoto University, Japan, in 1978, 1980, and 1987, respectively. From 1980 to 1983, he worked at Nippon Denso Company Ltd. From 1990 to 1995, he was an Associate Professor in the Department of Computer Science and Electronics, Kyushu Institute of Technology, Iizuka. From 1995 to 1997, he was a Professor at the Information Technology Center, Nara Institute of Science and Technology, Ikoma. His research interests include high-speed and multimedia networks, in particular their protocols and architectures.

[INET'98] [ Up ][Prev][Next]