Transcript Slide 1

CS411 Dynamic Web-Based Systems
Adaptive Web Caching
Flying Pig
Fei Teng/Long Zhao/Pallavi Shinde
Computer Science Department
Contents
ADAPTIVE WEB CACHING
1. Introduction
2. Related Research
3. Main Findings
4. An Ideal Adaptive Web Caching System
5. Multicast
6. Request Forwarding
7. Page Retrieval
8. Hierarchy and Scalability
9. Auto-configuration of Cache Groups
10. Group Creation and Maintenance
11. Conclusions
12. Future Scope
Introduction
ADAPTIVE WEB CACHING
The World Wide Web has seen an exponential growth in:
• the user population
• the total host count
• the amount of total traffic volume
Popular web pages create ‘hot-spots’ of network load due to
the same data transmitted over the same network links
repeatedly to different users.
The solution is obviously Caching
Introduction
ADAPTIVE WEB CACHING
•
The solution to data dissemination to a multitude of users is
to create a multicast delivery system – i.e. data should be
fetched only once and forwarded via a multicast tree to
different users
•
As requests on the web are asynchronous – web multicasting
is done via caching
•
The challenge in building a caching system is not knowing
beforehand which pages the users will be requesting
•
This is where an Adaptive Web Caching System comes in...
Related Research
ADAPTIVE WEB CACHING
The Harvest/SQUID Object Cache is a Web caching
infrastructure currently being deployed in the Internet.
All cache servers in the SQUID system are connected in a
manually configured hierarchical tree
This project has helped reduce unnecessary network load
through caching
Related Research
ADAPTIVE WEB CACHING
However, there are limitations due to manual configuration of
such large systems:
•
the burden on system administrators to configure the cache
hierarchy and to coordinate with each other
•
the inevitable human errors
•
misunderstanding of issues concerning the overall system
performance
•
the desire for local optimization
•
And the lack of adaptivity to network changes
Main Findings
ADAPTIVE WEB CACHING
An Adaptive Web Caching System has the following characteristics
•
An overlapping mesh, with each page having its own cache
tree
•
Auto-configuring
•
Routes requests to the nearest cache likely to have the data
•
Adaptive to changes in topology, load, user demands, etc.
•
Scalable
An Ideal Adaptive Web Caching System
ADAPTIVE WEB CACHING
Ideally the more a page is requested by users, the page would
automatically walk down the distribution tree (i.e. it is
proportional to the intensity of the requests).
This way the most popular pages would be the closest to the
end user and more cached copies of these pages would exist.
While pages that have been rarely requested for will either not
leave the origin server of be very high up in the distribution
tree.
An ‘adaptive’ system will load itself according to the demand
Multicast
ADAPTIVE WEB CACHING
IP multicast can be used as a basic building block to build this
system. The adaptive caching system makes use of both
features of IP multicasting:
•
Multicast page requests to locate nearest cache copy
available
•
Multicast page responses in order to efficiently
disseminate pages with common interests
Request Forwarding
ADAPTIVE WEB CACHING
•
Cache servers join more than one multicast group, this
way all cache groups heavily overlap each other.
•
If there is a cache miss in one group, each cache
checks if its other cache groups lie in the direction
towards the origin server of the requested page.
Page Retrieval
ADAPTIVE WEB CACHING
•
Once a request reaches a group of servers that have
requested it, the node holding the page multicasts the
response to the group.
•
This also loads the neighbouring caches in the same
group with the page.
Hierarchy and Scalability
ADAPTIVE WEB CACHING
•
On a base of overlapping mesh, each popular page
grows its own cache tree.
•
Cache pages based on the popularity of the page
allows the design of this system to scale well with large
user populations.
•
Cache tree for each page may grow dynamically, but
the cache groups remain relatively stable.
Auto-configuration of Cache Groups
ADAPTIVE WEB CACHING
For the Cache Group infrastructure to be scalable and robust, they
need to be self-configuring for the following reasons:
•
Manual configuration does not scale (For ex. SQUID
system)
•
Manual configuration tend to be error-prune
•
Self-configuring capabilities allow cache groups to
adapt according to changing conditions in network
topology, traffic load, user demand etc.
Group Creation and Maintenance
ADAPTIVE WEB CACHING
The basic functionality for cache group managements concerns
group creation and maintenance. This includes:
•
regrouping according to the observed group load
•
the group cache hit ratio
•
the tolerance of group overhead
•
the change in topology and caches
Group Creation and Maintenance
ADAPTIVE WEB CACHING
•
An open membership policy for cache groups
•
No authentication step required
•
Cache consistency and data authentication must be
properties that reside in the data
Conclusions
ADAPTIVE WEB CACHING
With this Adaptive Web Caching System:
•
no manual configuration required, it is auto-configuring
Higher the demand
for a page
=
Page further down the distribution
tree and closer to the end user
Conclusions
ADAPTIVE WEB CACHING
•
is adaptive to changes in topology, load, user demands,
etc.
Cache trees can automatically build themselves as popular
pages are pulled down towards their clients.
With time the trees should also automatically vanish as the
pages become a past interest.
Future Scope
ADAPTIVE WEB CACHING
Collaboration with the Harvest/SQUID Caching team to explore
transition strategies to convert the current manually configured
caching infrastructure into an auto-configured adaptive caching
system.
•
incremental deployment into the current unicast
caching infrastructure of dynamic mechanisms for
forwarding requests to neighbouring caches
•
incremental deployment of a multicast-based cache
architecture into the existing architecture of unicast
communications between clients, web caches, and
servers
Thank you for listening!
ADAPTIVE WEB CACHING
Questions?