9 · Web caching ★
Slides 2-34 → 2-40 · HW2 P3
What a Web cache is
- A Web cache (also called a proxy server) answers client requests without involving the origin server.
- The user points the browser at the cache, so every HTTP request goes to the cache first:
- Hit (object is in the cache): the cache returns it right away.
- Miss: the cache requests the object from the origin server, stores a copy, then returns it to the client.
- The cache is both a client and a server: a server to the requesting browser, a client to the origin server.
- It's usually installed by an ISP (university, company, residential ISP).
Why cache?
- Lower response time for the client (the cache is closer).
- Less traffic on the institution's access link.
- The Internet is dense with caches, which lets "poor" content providers deliver content effectively.
The setup
An institutional network (fast LAN) connects to the public Internet through one access link of rate \(R\). Every object that comes from outside crosses that link.
Total response time = Internet delay + access delay (+ LAN delay, which is tiny and ignored).
- Internet delay: from when the router on the Internet side forwards the request until the response comes back. It's given (e.g. 2 s or 3 s).
- Access delay: the queuing + transmission delay on the access link. This is the part the formula computes.
The access-delay formula
$$\text{access delay} = \frac{\Delta}{1 - \Delta\beta} \qquad \Delta = \frac{\text{avg object size}}{R_{access}} \qquad \beta = \text{request rate (objects/s)}$$
- \(\Delta\) = time to send one object over the access link.
- \(\Delta\beta\) = the traffic intensity (link utilization). It's the same \(La/R\) from topic 3: \(\frac{L}{R} \cdot a\).
- As \(\Delta\beta \to 1\), the denominator \(\to 0\) and the delay blows up. If \(\Delta\beta \ge 1\), the delay is unbounded (the queue grows forever).
With a cache
Only misses cross the access link, so the arrival rate drops to \(\text{miss rate} \times \beta\):
$$\text{access delay}_{cache} = \frac{\Delta}{1 - (\text{miss rate})\,\Delta\beta}$$
$$\text{avg response} = (\text{hit rate}) \times \underbrace{0}_{\text{from cache}} + (\text{miss rate}) \times \big(\text{access delay}_{cache} + \text{Internet delay}\big)$$
Traps
• Hit rate vs miss rate. The slides say hit rate 0.4. HW2 P3 says miss rate 0.4. They're opposite. hit + miss = 1.
• Only the misses use the access link. Reduce \(\beta\) before plugging into the formula.
• A hit takes about 0 s (LAN speed). Don't add the Internet delay to hits.
• Convert bytes to bits if the object size is in bytes.
• Hit rate vs miss rate. The slides say hit rate 0.4. HW2 P3 says miss rate 0.4. They're opposite. hit + miss = 1.
• Only the misses use the access link. Reduce \(\beta\) before plugging into the formula.
• A hit takes about 0 s (LAN speed). Don't add the Internet delay to hits.
• Convert bytes to bits if the object size is in bytes.
Worked example: HW2 P3
Q: Average object = 900,000 bits. Access link = 15 Mbps (from the textbook figure). Request rate = 16 requests/s. Internet delay = 3 s.
(a) Total average response time (no cache)
Time to send one object over the access link:
$$\Delta = \frac{900{,}000}{15 \times 10^6} = 0.06 \text{ s}$$Traffic intensity:
$$\Delta\beta = 0.06 \times 16 = 0.96$$Access delay:
$$\frac{\Delta}{1 - \Delta\beta} = \frac{0.06}{1 - 0.96} = \frac{0.06}{0.04} = 1.5 \text{ s}$$Total:
$$1.5 + 3 = \mathbf{4.5 \text{ s}}$$(b) Install a cache, miss rate 0.4
Only 40% of requests cross the access link, so the traffic intensity becomes \(0.4 \times 0.96 = 0.384\):
$$\text{access delay} = \frac{0.06}{1 - 0.384} = \frac{0.06}{0.616} \approx 0.097 \text{ s}$$A miss takes \(0.097 + 3 = 3.097\) s. A hit takes ~0 s.
$$\text{avg} = 0.6 \times 0 + 0.4 \times 3.097 \approx \mathbf{1.24 \text{ s}}$$Takeaway: 4.5 s → 1.24 s. The cache cuts both the number of slow trips and the queuing on the access link.
By hand: \(\frac{0.06}{0.616}\): \(0.616 \times 0.1 = 0.0616\), which is just over 0.06, so the answer is a bit under 0.1 (≈ 0.097). Then \(0.4 \times 3.097 = 1.2388\). If you write ≈ 0.1 s and ≈ 1.24 s, you're fine.
Slide example: 3 ways to fix a slow access link
Access link 1.54 Mbps, Internet RTT 2 s, object 100 Kbits, 15 requests/s.
Data rate to browsers = \(15 \times 100{,}000 = 1.5\) Mbps.
| Option | Access link utilization | End-to-end delay | Cost |
|---|---|---|---|
| Do nothing | \(1.5 / 1.54 = 0.97\) | 2 s + minutes (queue explodes near 1) | |
| Buy a 154 Mbps link | \(1.5 / 154 = 0.0097\) | 2 s + msecs | Expensive |
| Install a cache, hit rate 0.4 | \(0.6 \times 1.5 = 0.9\) Mbps → \(0.9 / 1.54 = 0.58\) | \(0.6(2.01) + 0.4(\sim 0) \approx\) 1.2 s | Cheap |
The cache gives a lower average delay than the 154 Mbps link, and it's cheaper. (2.01 = 2 s Internet + ~0.01 s on the now lightly loaded access link.)
Conditional GET
Goal: don't send the object if the cache already has an up-to-date copy. That means no transmission delay and lower link utilization.
- The cache puts the date of its copy in the request:
If-modified-since: <date> - Not modified since then → the server replies
HTTP/1.0 304 Not Modifiedwith no object. - Modified → the server replies
HTTP/1.0 200 OKwith the new object.
Quick check
1. Object = 1 Mbit, access link = 20 Mbps, 15 requests/s, Internet delay = 2 s. No cache. Average response time?
$$\Delta = \frac{10^6}{2 \times 10^7} = 0.05 \text{ s} \qquad \Delta\beta = 0.05 \times 15 = 0.75$$ $$\text{access} = \frac{0.05}{1 - 0.75} = 0.2 \text{ s} \qquad \text{total} = 0.2 + 2 = \mathbf{2.2 \text{ s}}$$2. Same as #1, but a cache is installed with hit rate 0.6. Average response time?
Miss rate = 0.4, so the intensity becomes \(0.4 \times 0.75 = 0.3\). $$\text{access} = \frac{0.05}{1 - 0.3} = \frac{0.05}{0.7} \approx 0.071 \text{ s}$$ $$\text{avg} = 0.6 \times 0 + 0.4 \times (0.071 + 2) \approx \mathbf{0.83 \text{ s}}$$3. Same as #1, but 25 requests/s. What happens?
\(\Delta\beta = 0.05 \times 25 = 1.25 \ge 1\). Requests arrive faster than the link can send them, so the queue grows forever and the delay is unbounded. (The formula gives a negative number, which is meaningless.)4. What is \(\Delta\beta\), in topic 3 terms?
The traffic intensity \(La/R\) on the access link: object size × arrival rate ÷ link rate.5. Give two reasons to install a Web cache.
Lower response time for clients (the cache is closer), and less traffic on the institution's access link. (Also: cheaper than upgrading the access link.)6. Why is a Web cache both a client and a server?
It's a server to the browser that sent the request, and a client to the origin server when it has to fetch a missing object.7. How does conditional GET work? Which header and status code?
The cache sendsIf-modified-since: <date of its copy>. If the object hasn't changed, the server replies 304 Not Modified with no object. If it has changed, 200 OK with the object.