  Popular peer to peer streaming media systems such as PPLive and UUSee rely on
periodic buffer-map exchange between peers for proper operation. The buffer-map
exchange contains redundant information which causes non-negligible overhead.
In this paper we present a theoretical framework to study how the overhead can
be lowered. Differentiating from the traditional data compression approach, we
do not treat each buffer-map as an isolated data block, but consider the
correlations between the sequentially exchanged buffer-maps. Under this
framework, two buffer-map compression schemes are proposed and the correctness
of the schemes is proved mathematically. Moreover, we derive the theoretical
limit of compression gain based on probability theory and information theory.
Based on the system parameters of UUSee (a popular P2P streaming platform), our
simulations show that the buffer-map sizes are reduced by 86% and 90% (from 456
bits down to only 66 bits and 46 bits) respectively after applying our schemes.
Furthermore, by combining with the traditional compression methods (on
individual blocks), the sizes are decreased by 91% and 95% (to 42 bits and 24
bits) respectively. Our study provides a guideline for developing practical
compression algorithms.
