1. Introduction
   Academic and corporate communities have been dedicating considerable effort to Web Caching and Replication to meet the scalability demands on the intranet and internet infrastructure. Web Caching and Replication is a rapidly evolving field which makes it difficult to keep up with recent advances. This tutorial captures a snapshot of the sate-of-the-art in web caching design describing a variety of specific trends and techniques.
      
2. Drivers for Web Caching and Replication
   This section introduces the concept of Web caching and replication in the context of Content Delivery Network (CDN). The components which form the backbone of the CDN are Storage Area Network (SAN), Web Switches and Proxy Caching server and Replica Origin servers. It will be shown how Web caching and replication helps to improve Quality of Service (QoS) of CDN by reducing latency, network load and server load.
      
3. Components of Web Caching and Replication System
   This section is devoted to the description of various components and terminology related to Web caching and replication systems. Some of these components are: Caching Proxy, Reverse Proxy, Transparent Proxy caching, Hierarchical Web Caching, Cache server, Cache Cluster, Origin server, Replica Origin server etc. Various diagrams are used to represent these components and concepts.
      
4. Web Caching and Replica Communication Protocols
   The underlining framework to make Web caching and replication work is defined by the communication between Clients, Proxy caches and Replica Origin servers. There are four aspects of this communication - 1) Between client and Replica; 2) Inter Replica; 3) Between Client and Cache; and 4) Inter Cache. In the context of Client to Replica communication, the URL redirection and DNS redirection capabilities will be discussed. The protocol used for Inter Replica communication depends on the particular Replica relationship such as Batch driven mirroring, Demand driven mirroring or cooperative synchronized replication. The Web Proxy Auto Discovery (WPAD) protocol provides the web client with a mechanism to discover Proxy servers. All of these protocols will be discussed in this section. In addition to this, the inter cache protocols covered in this section are : Internet Cache Protocol (ICP), Hyper Text Cache Protocol (HTCP), Cache Array Routing Protocol (CARP) and Cache Digest.
       
5. Web Acceleration
   One of the key contributors to latency is the actual time needed to transport pages between the client, Proxy server and the Replica Origin server. There are at least two mechanisms to accelerate this transport time - 1) Delta Compression which exploits the fact that updated web pages often change very slightly, thus resulting in very small sizes for the transmitted deltas and 2) Proxy Cache Aware Object Bundling which significantly reduces the setup costs of multiple TCP connections.
       
6. Replication Strategies
   Numerous replication strategies have been proposed by various researchers. Some of these strategies are : Cache with Limited Validation (CLV) where Intermediate Proxy servers cache documents for a given Time to Live (TTL); Server Invalidation (SI) where Intermediate Proxy servers cache the document until the Origin Server invalidates the copies; Server Updates x (SU-x) where the Origin server replicates the pages at the "x" most popular intermediate Proxy servers; or any hybrid of these. However, there is no single strategy which is optimal for all pages. By creating a cost function for each strategy, it can be shown that the system where the replication strategy for an object is based upon dynamic adaptive strategy selection, outperforms its non-adaptive counterpart. This section will discuss various adaptive strategy selection schemes and algorithms. Multicast based caching and replication protocols will also be presented.
       
7. Cache Placement Problem
   There are two types of placement - 1) Static i.e. the problem of determining the optimal locations in the infrastructure for the placement of Cache servers and 2) Dynamic i.e. the problem of determining the set of Cache servers for the placement of an object. Most of the optimization problem related to cache or replica locations are NP-hard. This is the reason that most of the algorithms developed to solve these problems are based on heuristics. This section will discuss how a combination of simulation and Mixed Integer Linear Programming can be used to solve the static problem i.e. Cache Replica Location Problem. For the dynamic case, this section will specifically consider a cluster-based streaming proxy and show at least two sub-optimal algorithms that can give results close to the optimal cache placement: a) Dynamic First Fit (DFF); b) Minimum Weight Perfect Match (MWPM).
      
8. Prefetching
   Web caching can be viewed as a "passive" method to improve response time. Adaptive schemes for cache replication can be viewed as an "active" method to further improve the response time which still does not try to anticipate the demand for the objects. Prefetching, on the other hand, is a "proactive" method because it actively preloads objects anticipated to arrive in near future and thus, further reduces the response time.. This section discusses all of the three methods of prefetching - 1) Between Clients and Origin servers; 2) Between Proxy servers and Origin servers; and 3) Between Clients and Proxy servers. A model integrating the functions of web caching and prefetching is also presented.
      
9. Edge Server
   The concept of web caching and replication traditionally applies to the output of an application. Recently, this concept of replication has been extended to the application itself. One can envision an infrastructure of resources geographically distributed along with the users. In an integrated environment of web caching and prefetching, it is feasible to deploy applications on demand at the servers located closer to the users. This section will discuss a platform for automatic redeployment of applications or network servers as required by changing demand and for distributing client requests among application replicas based on their load and proximity.
      
10. Commercial Products
    This section presents the list of Caching products commercially available and compares them. These vendors are : CacheFlow Inc.,Cisco Systems, IBM Corporation, InfoLibria, Inktomi Corp., Microsoft,, Netscape, Network Appliance, Novell Inc., Entera Inc., Oracle, Warp, Times Ten, Chutney Technologies, Xcache. Some of these products are available as software which can run on any off-the-shelf hardware platform while the others are built upon custom hardware.
       
11. Future Directions
    In the closing, the presentation addresses various future directions in web caching technology. Some of them are - 1) Integration of caching, web switching and firewall functions, 2) Use of AI algorithm, 3) Integration of caching and content management etc

Dipu Ghosh is currently leading a team of Performance Engineers at BankOne engaged in developing models for the end-to-end performance and availability.

Before joining BankOne in 2002, Dipu worked as Distinguished faculty member and researcher in the area of Network Convergence, Content Delivery Network and e-Business Infrastructure for the Learning and Performance Center (LPC) of Lucent technologies and taught various Internetworking courses to Lucent's R&D organization.

Before joining LPC in 1999, he was a Technical Manager, System Architect and Researcher in the areas of Intelligent Network and ISDN Interface for Lucent and Bell Laboratories. Dipu championed and led the development of USDS, the first distributed high performance (1600 calls per second) Network Database Application in AT&T's signaling network. He developed the concept of Integrated Reliability Engineering and applied it during the development of USDS which had resulted in 100% uptime for the product during its six years of operation in the production network. He represented AT&T and Lucent Technologies in both ANSI and CCITT in developing the Connection-Oriented SCCP protocol and had made numerous contributions. Dipu was the architect of the implementation of Connection-Oriented SCCP in AT&T's signaling network for highly secured data transfer across the voice signaling network.

Dipu holds a M.S. and a PhD degree in Electrical Engineering from University of Connecticut and an MBA degree from Ohio Unversity.

Included in the conference comprehensive registration rate ($200 on-site at the conference). 

Registration for this tutorial is available at the SCS Home Page in concert with the SPECTS'04.

Sponsored by The Society for Modeling and Simulation International
P.O. Box 17900
San Diego, California 92177
Phone 858-277-3888
Fax 858-277-3930
E-mail scs@scs.org

Return to SPECTS'04 Home Page

Return to SCS Home Page

Copyright 2004, SCS. All Rights Reserved.