WebHint: An Automatic Configuration Mechanism for Optimizing World Wide Web Cache System Utilization
Hiroyuki INOUE <email@example.com>
Yuji OIE <firstname.lastname@example.org>
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.
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 . 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 . 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)  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.
The first cache server introduced was the CERN HTTPD server  which stored recently accessed pages for subsequent use. When a user requests a URL (Uniform Resource Locator) , 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 . The squid cache derived from Harvest and developed at NLANR  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 . 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.
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 . 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.
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).
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:
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:
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) .
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.
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
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.
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 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 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.
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  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.
The current version of WebHint is available on our Web server:
The latest documentation and other related information are also available here.
The authors would like to thank the members of the WIDE project for having discussed the hint server and the WWW cache system.
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.