Fundamental delay bounds in peer-to-peer chunk-based real-time streaming systems

Speaker: Prof. G. Bianchi Abstract: In this talk we address the following question: What is the minimum theoretical delay performance achievable by an overlay peer-to-peer streaming system where the streamed content is subdivided into chunks? We first start to show that, when posed for chunk-based systems, and as a consequence of the store-and-forward way in which chunks are delivered across the network, this question has a fundamentally different answer with respect to the case of systems where the streamed content is distributed through one or more flows (sub-streams). We then proceed by defining a convenient performance metric, called "stream diffusion metric", which is directly related to the end-to-end minimum delay achievable in a P2P streaming network, but which allows us to circumvent the complexity emerging when directly dealing with delay. We further derive a performance bound for such metric, and we show how this bound relates to two fundamental parameters: the upload bandwidth available at each node, and the number of neighbors a node may deliver chunks to. Quite interestingly, in this bound, n-step Fibonacci sequences play a key role, and appear to set the laws that characterize the optimal operation of chunk-based systems. Finally, we constructively show by means of which topologies and system operation this bound is attainable.