Delay and Overhead in the Encoding of Data Sources

A basic property of data sources in interactive applications is burstiness, i.e., short periods of activity followed by long idle periods. In these same applications message delay is the primary performance criterion. The combination of bursty flow and a delay criterion leads to a source encoding problem in which delay plays a central role. A salient feature of this problem is that there is a tradeoff between delay and the number of protocol bits required to represent the state of the source. A simple model of a bursty source is studied with the objective of understanding the relationship between coding efficiency and delay. Two encoding schemes, a block encoding technique and a technique employing flags, are examined in some detail. For both the block encoding and the flag schemes, a significant result is that as the source becomes less bursty, delay grows without bound. This result is obtained in spite of the fact that both schemes are reasonable and in the limit the encoding problem disappears. It also appears that the flag encoding technique has much smaller delay than block encoding.