Practical algorithm for minimum delay peer-to-peer media streaming

Abstract

Though the existence of a minimum delay peer-to-peer media streaming scheme has been shown (under the name of snowball streaming), no actual algorithm has ever been designed so far, due to the lack of a systematic way to construct the chunk scheduling that achieves the minimum delay bound. Inspired by the growth of interest in building hybrid streaming systems that consist of backbone trees supplemented by other overlay structures, we revisit the minimum delay streaming problem and design practical min-delay algorithms to support the streaming in the backbone trees. What mainly distinguishes our multi-tree push from the conventional ones is an unbalanced tree design guided by the snow-ball streaming, which has a provable minimum delay. We design algorithms to construct and maintain our SNowbAll multi-tree Pushing (SNAP) overlay. Our simulations in ns-2 indicate that our approach outperforms other tree-based mechanisms.