Compressing the X Graphics Protocol (Thesis)
Report ID: TR-465-94Author: Danskin, John M.
Date: 1994-11-00
Pages: 130
Download Formats: |Postscript|
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.