Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation

Armando Fox and Eric A. Brewer, University of California, Berkeley

Acknowledgments: Steven Gribble, Mark Stemm, Elan Amir, Randy H. Katz
University of California, Berkeley

Latency, Bandwidth, and Content in Today's WWW

Content Targeted for High Bandwidth, Midrange PC's

But...Lots of 14.4K, 28.8K, and (soon) mobile/cellular users
But...potential market of mobile device users (e.g. PDA, Nokia 9000 smart GSM phone)
Latency and bandwidth become a real problem
About 1 in 5 Jumbo users turn off image loading
Transatlantic connections

Existing Approaches

Provide multiple versions of content, e.g. Xinside	Increased administration at server Changes to server code, to support e.g. Odyssey [Satyanarayanan et al. ] Difficult and getting worse, since "anyone" can be a server
Progressive encodings	E.g. LOWSRC image tag extension, PJPEG, PGIF Initial latency may still be high No active bandwidth management or traffic scheduling
Use ALT text	WWW is already graphics-intensive Advertising is making "logo visibility" important
Caching and prefetching	Reduces latency but not bandwidth to client Caching is necessary, but orthogonal to our approach

Real-Time Distillation

Highly lossy, real-time, datatype-specific compression

Goal: produce a useful representation that is

suitable for transmission given client's bandwidth
optimized for rendering on client device (colormap, screen size, etc.)
created on demand, in "real time": trade cycles for bandwidth
Assumption: cycles, memory, and connectivity on a desktop PC are cheap and plentiful

Distillation decisions are made and executed by a proxy

Distillation Example: Graphics

Distilled image: 320x200, 16 colors, 17K GIF

Original image: 880x600, 256 colors, (503K GIF)
Size reduction: nearly 30x
Total latency: about 6 seconds on a SPARC-20

Bandwidth Management by Refinement

Subregion of original, at full color and resolution: 15K GIF

Total latency: less than 1 second on a SPARC-20
For grayscale clients: grayscale and format conversion are incremental costs

Distillation Performance: Latency and Compression (14.4 Modem)

Reflects heavily-loaded PPP gateway at Berkeley and TCP slow-start.

Transmission Without Distillation (14.4 Modem)

Distillation adds latency, but reduces end-to-end latency.

Distillation Performance: Workload

100% compute-bound operation
One HP PA-RISC workstation can serve 15-20 (bursty) users!
Event-based simulation, based on current distillation performance and Berkeley Computer Science Division HTTP logs for Jan.-Feb. 1996:


10 users	16 users	20 users	24 users

Real-Time Adaptation

Goal: Automate distillation decisions based on network conditions.

Keep time-averaged statistics modeling quality of network
Optimize: Fetch time + Distill time + Xmit time <= Latency bound
Need automated statistical modeling [Brewer94] of distillation behavior
- Compression achieved as function of distillation axes
- Distillation latency as function of axes
- Target data formats optimized for client rendering or transmission

We are developing distillation-based proxies as part of the Daedalus Wireless Mobile Computing project at UCB.

Other Data Types

PostScript

Implemented PostScript distiller outputs HTML, plain ASCII, or "custom richtext"
Latency: about 5+2n seconds for an n-page tech report
Pipelined output reduces initial latency

Amir et al., An Application-Level Video Gateway , ACM Multimedia 95

Real-time NV to H.261 or VQ
Can fix frame rate, bit rate, color/resolution, etc.
In production use at CERN

Pythia, an Implemented WWW Proxy

Demonstrates distillation technology applied to the WWW
Implemented as HTTP 1.0+ proxy (similar idea: Mazer et al., Application-Specific Proxy Servers as HTTP Stream Transducers)
Publicly accessible
User preferences specified via HTML form
Links for refinement added to HTML
Distillers can run locally or on Berkeley's Network of Workstations (NOW)
Distillation tuned to network parameters periodically reported by Daedalus Network Connection Monitor

Proxies and Network Computing

The distillation proxy architecture spans the WWW,
mobile computing, and network computing.

Can scale to "ISP levels" to serve large groups of clients
Complexity is pushed from client to proxy
- Client hardware/software can be simple (e.g. Joel Bartlett, Experience With aWireless WWW Client)
- Automatic adaptation across existing infrastructure (wired PSTN, GSM, etc.)
- Hides WWW "software anarchy" from client
Increased user control over content received
- Control costs on metered services
- Eliminate annoying background images
Enables some clients at least partial access to services they would otherwise be denied
Give away the razor, charge for the blades.

Future Work

What does it mean to "distill" multimedia datatypes? (e.g. Shockwave)
HTML reformatting/segmentation for small displays
True load balancing for scalable proxy services
Trial run with Berkeley Office of Telecommunications Services (PPP provider)
Integration into GloMop, the Daedalus project's proxy service model
Proxy research prototype will soon be available for downloading

Conclusions

Benefits of a distillation-based proxy

Real-time distillation, guided by statistical models, reduces end-to-end latency
Refinement allows explicit bandwidth management
Transcoding to client-friendly representation reduces client software complexity
Content can be optimized for client rendering
Applications include WWW, mobile computing, network computing

Reducing WWW Latency and Bandwidth Requirements by Real-Time Distillation

Latency, Bandwidth, and Content in Today's WWW

Content Targeted for High Bandwidth, Midrange PC's

Existing Approaches

Real-Time Distillation

Highly lossy, real-time, datatype-specific compression

Goal: produce a useful representation that is

Distillation decisions are made and executed by a proxy

Distillation Example: Graphics

Bandwidth Management by Refinement

Distillation Performance: Latency and Compression (14.4 Modem)

Transmission Without Distillation (14.4 Modem)

Distillation adds latency, but reduces end-to-end latency.

Distillation Performance: Workload

Real-Time Adaptation

Goal: Automate distillation decisions based on network conditions.

We are developing distillation-based proxies as part of the Daedalus Wireless Mobile Computing project at UCB.

Other Data Types

PostScript

Amir et al., An Application-Level Video Gateway , ACM Multimedia 95

Pythia, an Implemented WWW Proxy

Proxies and Network Computing

The distillation proxy architecture spans the WWW, mobile computing, and network computing.

Future Work

Conclusions

Benefits of a distillation-based proxy

We expect that value-added proxied services will become increasingly important for WWW access and mobile/network computing.

The distillation proxy architecture spans the WWW,
mobile computing, and network computing.