Compressing the X Graphics Protocol (Thesis)

Abstract:

This dissertation is about compressing networked graphics for
transmission across low bandwidth networks like phone lines and
wireless networks. It concentrates on the X Window System Version 11
(X) because X is the most widely available networked window system
today. The dissertation is divided into three main sections:
The first section describes a system for tracing the X protocol, the
traces gathered, and an analysis of the results. The traces were
analyzed by breaking the protocol down into discrete instructions or
messages, and analyzing the frequency and network resource
requirements of these messages. This analysis has resulted in
preliminary results in 4 areas: the relative importance of X messages,
how X usage changes during different application stages, differing
application idioms for accomplishing similar tasks, and the size
distributions of X messages and groups of X messages. Some of these
results have architectural implications for network protocols and
implementations.
The second section examines the performance of the Xremote protocol,
which was designed as part of a product by Network Communications
Devices Inc. (NCD). The Xremote protocol is a compressed
transformation of the X Window System protocol, designed to
efficiently implement X connections across relatively slow serial
lines. Using an Xremote simulator and 11 traces of X sessions, I found
that Xremote's overall compression ratio is 2.4:1.
Text based applications commonly see about 2.5:1 compression,
geometric applications achieve about 1.7:1 compression
and image based document previewers achieve about 2.5:1.
The third section introduces a new technique for compressing
structured data. Embodied in the Higher Bandwidth X (HBX) protocol,
this technique results in 7.5:1 compression across the trace suite,
for about 3 times the performance of Xremote. HBX works by parsing X
messages into individual fields and applying statistical modeling and
arithmetic coding to individual fields of X messages. HBX typically
achieves 5:1 compression on geometric data, between 10:1 and 20:1
compression on image based document previewing, and over 5:1
compression on text based applications.
It seems likely that the techniques used in HBX will prove
applicable to compressing network headers, object code, RPC
traffic and other structured data.