Media Caching

Major scenaria of importance:

  1. Proxy server caching
    Intelligent algorithms for selective default caching:
    To cache or not to cache - the question is now!
  2. Demand video caching
    Intelligent algorithms for selective default prefetch:
    To prefetch-if, what, and when!
  3. Virtual, Inc.:
    An industry entrepreneur in the EBI aspect of the research:

 

 

Proxy Caching and Prefetching

 

 

Dejan Petkovic
dwecci@sezampro.yu
http://galeb.etf.rs/~dejan

Veljko Milutinovic
vm@etf.rs
http://galeb.etf.rs/~vm

 

 

Traditional Proxy Servers

An add-on to WWW servers to provide caching and security
(a part of WWW server)

References:

WWW cache related articles, papers, and reports:
http://cache.kaist.ac.kr/docs/related.html

WWW cache related links:
http://w3cache.icm.edu.pl/links/software.html

The Cache Now!
Campaign is designed to increase the awareness and use of proxy cache
on the Web:
http://vancouver-webpages.com/CacheNow/

Proxy caching

 

Topics of Interest

Hierarchical caching (client, proxy(c), proxy(i), proxy(s), server)
Transport characteristics

Cache characteristics
Removal policy
Coherence
Implementation
Proxy configuring

Prefetching in theory and practice:
active and passive prefetching

Client - Proxy - Server Architecture

Problems with traditional client-server architectures:
    1. Server overload and protection;
    2. Network congestion;
    3. Long response times.

System data flow

Proxy services:

Proxy forms:

(a) Firewall
(b) Caching
(c) Prefetching

h Server
h Client
h Intermediate

 

Cache stores a local copy of the requested object:
    1. Reducing hits to a server,
    2. Reducing the number of bytes over the Internet,
    3. Reducing time that users wait for an object to load.

Prefetching:
storing the local copy
of "not-yet-but-probably-soon" requested object,
reducing the latencies.

Hierarchical caching

Cache hierarchy at the School of Electrical Engineering

 

Client cache - built into a Web browser:

Proxy cache is located on a machine
on the path from multiple clients to multiple servers.

Parent: proxy ® rti7020
Peers: proxy « proxy2

Prefetch: local or server hinted

 

Transport characteristics

Latencies

 

Cache characteristics

Removal policy

Proposed algorithms:

First in first out sorts objects by the cache entering time (CET)
and removes those with the smallest CET.

Least recently used sorts objects by last access time (LAT)
and removes those with the smallest LAT.

Least frequently used sorts objects by number of references (NR)
and removes those with the smallest NR.

LRU-MIN tests whether there are any documents equal or larger in size;
if there is, removes one of them by LRU:
otherwise, considers all documents larger than half the size of incoming document;
if there is, removes one of them by LRU.

LRU-THOLD is identical to LRU,
except that no document larger than a threshold size is cached.
(Even if the cache has room, a document whose size is larger than the threshold is never cached.)

Hyper-G sorts objects by the number of references (NR) as a primary key,
LAT as a secondary key, and Size as a tertiary key.

Pitkow-Recker determines the relationship
between the number of document requests during a period (called the window)
and the probability of access on a subsequent day (called the pane).

Space Working Set removes the largest file in the cache.

Space-Time Working Set excludes the document
with the largest product of time since last access and byte size (size× time).

Space-Time Product removes the document with the greatest size× (timey)
where y is a parameter close to 1 (suggested 1.4).

Space-Time-Cost Working Set removes the file with the highest Size∙Time/Cost,
where Size is the byte size,
Time is the time since last access, and
Cost is the time needed to fetch the document.

CERN httpd3 takes into account the age of a document, time since last access,
expiration date, network delay, and byte size. Each of these factors changes
linearly from 0 to 1 according to the formula:

attribute_factor=1-(document_attribute)/(max_attribute)

The worth of a document is the product of all five factors.
The max_attribute is usually set in the configuration file.

Bolot-Hoschka proposed two weighting functions:

W(ti, Si, rtti, ttli) = w3/ti
W(ti, Si, rtti, ttli) = w1× rtti+w2× Si+(w3+w4× Si)/ti
W1, W2, W3, W4 - Weights

ti

-

The time since the document was last referenced

Si

-

The size of the document

rtti

-

The time it took to retrieve the document

ttli

-

The time to live

Latency-based Removal (LAT) selects for replacement the object i
with the smallest download time estimated, denoted di:

di = clatser(i) + si/cbwser(i).

Hybrid Removal (HYB) selects for replacement the object i
with the lowest value of the following expression:

(clatser(i) +WB/cbwser(i))(nrefiWN)/si,

clatj

-

Estimated latency

cbwj

-

Estimated bandwidth of the connection (in bytes/second)

si

-

The object's size

nrefi

-

Number of references to the object i since it last entered the cache

WB, WN

-

Constants that set the relative importance of the variables

Removal policy could be run:

Coherence

Web browsers can be configured to validate their caches
every time an object is requested, one per session, or never.

Proxy cache coherence maintenance based on:

Implementation

Some popular proxies: Squid, Netscape proxy server, WinGate,...

The most employed algorithm: LRU, removal policy runs on demand.

Proxy configuring

Squid - configuration file, read on start-up (disk space, LRU High/Low marks).

WinGate - program GateKeeper for dialog based configuring.

Prefetching

-Administrator hinted

-Images

-Referenced documents

-Objects found in the access list

Statistics

External latency: 80%

Cache with unlimited storage:

Total latency reduction: 24%

Hit rate: 50-55% (30-50% in practice)

Prefetching:

Local - total latency reduction: 41%

Server hinted - total latency reduction: 57%

Weighed hit rate: 5-10% less than hit rate.

Future trends

Advanced Caching

Subject recognition,

Spatial locality (server hinted and client estimated),

Prefetching based on spatial and temporal locality.

Virtual Proxy Servers

A middle layer between WWW servers and browsers of clients,
responsible not only for caching and security,
but also for search, indexing, filtering, profiling, agenting...

3 + 3

References:

Pitkow, Recker. "A Simple Yet Robust Caching Algorithm Based on Dynamic Access Patterns",
Proceedings of the Second World Wide Web Conference '94:Mosaic and the Web,
http://www.ncsa.uiuc.edu/SDG/IT94/Proceedings/DDay/pitkow/caching.html.

Williams, Abrams, Standridge, Abdulla, Fox, "Removal Policies in Network Caches for World-Wide Web Documents," http://www.acm.org/sigcomm/sigcomm96/papers/williams.html.< /P>

Roland P. Wooster, Marc Abrams, "Proxy Caching that Estimates Page Load Delays", WWW6, April 1997, pp. 325-334
http://www.cs.vt.edu/~chitra/docs/www6r./

Partl, Dingle "A Comparison of WWW Caching Algorithm Efficiency", http://webcache.ms.mff.cuni.cz:8080/paper/paper.html.

Wu, Liao "Virtual Proxy Servers for WWW and Inteligent Agents on Internet", Proceedings of the HCSS-97,
Maui, Hawai'I, USA, January 1997, pp. 200-209.

V. N. Padmanabhan, J. C. Mogul, "Using Predictive Prefetching to Improve World Wide Web Latency," ACM
Computer Communication Review, pp. 22-36, vol. 27, no. 3, July 1996. http://daedalus.cs.berkeley.edu/publications/ccr-july96.ps.gz.

Ken-ichi Chinen, Suguru Yamaguchi, "An Interactive Prefetching Proxy Server for Improvement of WWW Latency".

Hiroyuki Inoue, Kanchana Kanchanasut, Suguru Yamaguchi "An Adaptive WWW Cache Mechanism in the AI3Network"
http://www.isoc.org/isoc/whatis/conferences/inet/97/proceedings/A1/A1_2.HTM.

Gihan V.Dias, Graham Cope and Ravi Wijayaratne, "A Smart Internet Caching System," INET96 Conference,
http://www.isoc.org/isoc/whatis/conferences/inet/96/proceedings/a4/a4_3.htm.

Jeffrey C Mogul, "Hinted Caching in the Web".

"Squid Internet Object Cache," http://squid.nlanr.net/.

 

Research at UB/IFACT

 

Two major research domains:
      1. Algorithms
        Exploiting spatial and temporal locality,
        using past behavior and future correlation [Milutinovic97]
      2. Tools
        Efficient kernel modifications,
        to enable experimenting with various algorithms.

 

Acknowledgments:

Vladan Dugaric
Dejan Petkovic

Exploring Spatial and Temporal Locality
in HTML Documents

Traditional caching

Problems:

Existing solutions:

Access patterns analyzed on a server side
Þ suggested caching and prefetching.

Problem:

Server analyzes accesses only to local documents.
New protocols required.

Proposed solution:

To analyze fetched HTML documents and to track multiple references to objects.
Reference: pointer within the current HTML object to some other object.

Objects with more references in the current set of fetched documents
have higher probability of a repeated access in the relatively near future.

Objects with more accessed references in the current set of fetched documents
have higher probability of being accessed sooner then the referenced documents.

Problem:

Parsing takes CPU time (CPU used for proxy caching 5-10%).
Takes disk space for building tree structure.

Expected improvement in all levels of cache hierarchy.
Thesis research of Dejan Petkovic...

 

 

 

Example: