Transcript S1-web


Welcome to 711.

Xinfeng Ye
Room: 303-589
Office hours: whenever I am around or email
me for appointment


1
Course admin




There are two assignments. Each assignment is
worth 15 marks.
The final exam is worth 70 marks
This is a practical paper that requires separate
pass in theory (exam) and coursework
(assignments)
Class rep?
2
Steps on accessing a web site
3
The time for DNS server to resolve the web server’s name to
IP address (if necessary).


Not shown in the diagram
The time for the client to set up a TCP connection with the
web server
The time for the request transmitted from the client to the
web server
The time for the web server to parse the request and generate
a web page
The time for the response transmitted from the host to client





The time when all the information are received by the client
The time for the client browser to render the page


Not shown in the diagram
4
How to reduce the response time

Reduce the network latency (i.e. transmission delay)

Place servers closer to the clients


Reduce the amount of information that have to be sent
to the clients



Benefits the users that connect to the servers through lowbandwidth networks
For a given bandwidth, less information to be transmitted
means less time is needed for transmission
Reduce the load on the web server


Could be significant
Generate the response faster
How to achieve these?

Proxy server, caching server

A proxy server normally caches web contents. But, web contents can
be cached on other types of servers as well.
5
Web Cache

A web cache usually sits between the web server
and clients
Watches requests come by, and saves copies of the
responses for them.
 When there is a coming request for the same URL
resource, the web cache can retrieve the cached
response and send it back to the client without
asking for the web server to serve this request again.

6
Advantages of Web Caching

Reducing network latency
There is a distance between clients and web servers.
 Caching web object locally can dramatically reduce
transmitting latency

7

Reducing bandwidth consumption
Cache the web objects close to the client side
 Reponses to the same requests do not need to be
transferred again between the proxy server that
caches the web objects and the origin web server.


Reducing server load
Some of the requests do not need to be handled by
the origin server.
 As some requests can be served from proxy servers,
the origin web server can direct more capability to
deal with other requests.


Improve the response time for the non-cached contents.
8
Categories of Web Caching

Browser
Many web browsers support caching.
 When a web page is first requested, the browser
saves the web page in the disk.
 If the page is requested again or the user clicks the
“Back” button, the cached page might be used.



In some cases, the browser might need to check with the
remote web server to see whether the cached page is still
valid. If it is valid, the page in the local disk is used.
Examples: Firefox, IE.
9
Proxy Server



There are two types of proxy servers, i.e. forward proxy
and reverse proxy
A forward proxy is an intermediate system that enables
a browser to connect to a remote network to which it
normally does not have access. A forward proxy can
also be used to cache data, reducing load on the
networks between the forward proxy and the remote
web server.
A reverse proxy (http accelerator) is installed in front of
web servers. All connections coming from the Internet
addressed to one of the web servers are routed through
the proxy server, which may either deal with the request
itself or pass the request to the web server behind.
10


Proxy servers are located
in various locations
throughout the Web.
hierarchical caching
structure


Each cache serves many
clients, which may be
users or other caches.
When the request is not
served by a local cache,
the request is passed on
to a higher level in the
hierarchy, until reaching a
root cache, which, having
no parent, would request
the object from the origin
server.
11

cooperative caching architecture


Caches communicate with each other as peers (e.g., using an
inter-cache protocol).
On a miss, a cache would ask a predetermined set of peers
whether they already have the missing object.



If so, the request would be routed to the first responding cache.
Otherwise, the cache attempts to retrieve the object directly from the
origin server.
This approach can prevent storage of multiple copies and
reduce origin server retrievals
Suffers from increased inter-cache communication.

Instead of asking peers directly about each request, a peer periodically
gives peers a summary of the contents of the cache
12
13
Content Delivery/Distribution Network
(CDN)




CDN is designed to place content caching
servers at the edge of network around the world.
It reduces the traffic congestion on the network
and the latency perceived by users.
The caching servers at the edge side of network
are called edge servers which can cache HTML
pages, images, audio and video files.
Examples: Akamai, Digital Island
14


When the client requests a web page, the request is
firstly sent to a forward proxy.
The forward proxy then decides which edge server to
communicate with.



If none of the edge servers cache this page, the request is
delivered to the web server.
Otherwise, one of the edge servers , which is closest to the
client, will serve the request.
Examples: Akamai EdgeSuite, IBM WebSphere Edge
Server
15
16
Potential problems

The end user see stale (e.g., old or out-of-date) content,
compared to what is available on the origin server (i.e.,
fresh content).


Caching tends to improve the response times only for
cached responses that are subsequently requested (i.e.,
hits).



HTTP does not ensure strong consistency
Misses that are processed by a cache generally have decreased
speed. Thus, a cache only benefits requests for content
already stored in it.
Caching is limited by a high rate of change of source
data.
Some responses cannot or should not be cached

Web server will set and send the HTTP headers that
determine cacheability
17
Dynamic Data Page



Dynamic data pages are generated by applications
according to the underlying frequently changing data
sources such as databases and files.
Dynamic data pages are usually generated on the
demand of user’s request.
Dynamic pages have two characteristics: high volatility
and high variation



It is volatile because not only it changes more frequently but
also its change is unpredictable.
It is various because it is often customized or personalized
from a set of content fragments.
Compared to a static page, a dynamic data page is
expensive to create.

more valuable to cache a dynamic data page
18
Proxy-based Dynamic Page Caching

Proxy-based caching approaches can be classified into
three broad categories




In the page-level caching , the proxy server caches fullpage outputs.


page-level caching
fragment-level caching
data-centric caching
Many commercial products have applied this approach.
Compared to no-caching, the page-level caching has the
following advantages:



reduce the page generation delay
reduce the delay associated with packet filtering and other
firewall-related delays
reduce the bandwidth required to transmit the content from
the web server to the proxy
19

The page-level caching has the following
limitations

There is often very little reusability of full HTML
pages


A personalised page displaying the name of the user at the
top of the page: the cached page in the proxy is only
reusable if the same user accesses to the same page
Unnecessary invalidation

If there is only one element of the page becomes invalid,
then the whole page needs to be invalidated in the cache.
20
Fragment-level caching

Fragment-level caching requires establishing a
template for each dynamically generated page.

The template file specifies the contents and layout of the
page.
Essentially, each page is factored into a number of fragments of
differing cacheability profiles and different caching expiration
time.
 The fragments and the templates of the pages are maintained as
separate elements on the origin servers and the proxy servers.
 A web page is assembled at proxy caching server when the page
is requested.


Popularized by Akamai as part of the Edge Side Includes
(ESI) initiative
21
Edge Side Includes (ESI)



Edge Side Includes (ESI) is a simple markup language
used to define web page fragments of differing
cacheability profiles and different caching expiration
time.
ESI defines some tags that can be used in the template
files.
A template file is a normal HTML file with ESI tags.

Amongst the ESI tags, “esi: include” is used to include a
fragment.
22
<html>
<body>
<esi:include src=http://example.com/advertise.jsp />
<esi:include src=http://example.com/navigation.jsp />
<esi:include src=http://example.com/personalize.jsp />
<esi:include src=http://example.com/news.jsp />
</body>
</html>
advertise
navigation
personalize
news
23
24

Compared with page-level caching approach,
fragment-level caching approach can improve
hit rates as it can specify granular caching
capability.


Fragment-level caching need the developer to
partition the pages.


According to the properties of different fragments,
the fragment can be set with different caching
expiring time and cacheability.
Might require the re-writing of pages or applications
Further reading

http://www.esi.org/
25
Data-centric caching


Fragment-level caching requires the web pages to be
factored into a number of fragments
Data-centric caching focuses on the contents of the
data being transmitted.



Carried out by the underlying mechanism.
Does not require the cooperation of the web page authors
We will look at two schemes:

Value-Based Web Caching


S. C. Rhea, K. Liang and E. Brewer, Value-Based Web Caching, Proc.
of the 12th International Conference on World Wide Web, pp. 619 –
628, 2003
Delta encoding
 Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, Balachander
Krishnamurthy, Potential benefits of delta encoding and data
compression for HTTP, 1997
26
Value-Based Web Caching

A lot of information being transmitted over the
Internet are redundant, since they are identical.

25-30% text-based responses were caused by resource
modifications.


Aliasing, which means two distinct URIs reference the same
data, also results in redundant data being transmitted over the
network.


Many modifications only change the contents of the information
being transmitted by a small amount.
Aliased data account for 36% of the data transferred
Value-based web caching exploits similarities between
data to eliminate redundant data transmission caused by
resource modification and aliasing
27
Message Digest (hash)

Used to represent a message with a given
number of bits.


produced by condensing the information in the
message
MD5

Produce a 128-bit digest.
28

A page is broken into blocks of approximately 2KB
each, and each block is named by its fingerprint (i.e.
digest) calculated using a secure hash function MD5.



According to the properties of MD5, it is highly unlikely that
two blocks containing different contents have the same
fingerprint.
Two blocks are regarded as identical if their fingerprints
are the same.
The cached blocks are indexed using their fingerprints.

If the responses to two requests contain identical blocks, the
identical blocks do not need to be sent again in the second
response.
29

The scheme was proposed to reduce the latency
of the users connecting to the Internet through
low-speed connection.
30

The scheme uses two kinds of proxies.






The child proxy caches the contents of the blocks and their
fingerprints.
The parent proxy only records the fingerprints of the blocks that
are cached on the child proxy.
The origin server is responsible for partitioning pages into blocks
and computing the fingerprints.
When a parent proxy receives the blocks that constitute the
response to a user’s request, the parent proxy determines which
blocks the child proxy already has by checking the fingerprints of
the received blocks.


One resides on the user’s PC, called child proxy;
The other one resides on the user’s ISP, called parent proxy.
The parent proxy only sends the blocks that the child proxy does not
have to the child proxy.
The child proxy assembles the page according to the
received/cached blocks and delivers the page to the user.
31
32

Instead of using a fixed block size, e.g. 2KB per block,
the scheme uses Rabin functions to determine how to
partition a page into blocks.

The benefit of this approach is that modifications to a page
would only affect the block(s) in which the modifications
occur.
33




Determine the boundary according to the value of the blocks.
Let f be a function mapping n one-byte inputs uniformly and
randomly to the set {0, …, 2047}.
Place a block boundary before byte i in a resource if the value of
f on the n bytes proceeding byte i is 0.
Since f is uniform and random, we expect to evaluate it on
average 2048 times before finding a zero; thus the expected
block size from this technique is 2 kB.
34
35
Delta encoding





In delta encoding, the origin server generates many
different “base files”.
When a user’s request arrives, the server finds the base
file that is closest to the response to be sent back to the
user.
The difference (“delta”) between the response and the
chosen base file is computed.
Then, the delta and a reference to the base file are sent
back to the user.
The bandwidth savings stem from the fact that the base
file is commonly used and the user has a local copy of
the base file. Thus, the user can obtain the requested
page by applying the delta to the base file.
36
server
request
client
V1
V1
734 exam is cancelled.
V2
734 exam is not cancelled.
V3
734 exam is on.
37
Review




What are the main steps in accessing a web
applications?
What measures can be used to reduce the response time
of a web-based application? What is the techniques for
implementing these measures?
What does a web cache work? What does a web cache
do to reduce the response time to web applications?
Assume that (a) two clients access a web application
through two connections with different network
latencies, and, (b) the difference in network latency for
the two connection is x ms. Explain why the difference
in response time to the two clients might be
significantly higher than x ms.
38
Review







How do the forward proxy and reverse proxy work?
Understand how web caches are placed on the Internet and how
they are used.
How does a CDN work?
What are the problems associated with the use of web cache?
What are dynamic pages and what are the features of the
dynamic pages?
Understand how page-level caching and fragment-level caching
work and the potential problems associated with them.
What are the two observations on the network traffic that justify
the use of value-based web caching?
39
Review


How does the value-based web caching technique
work? What are the potential problems that associated
with the value-based caching?
How does delta encoding based web caching scheme
work? Compare with other web caching techniques,
what are the strength and the weakness of the scheme?
40