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

Tuesday, October 21st 2008, 4:30pm
302 Building, Room 105


In this talk we address the following foundational 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 fundamental laws that characterize the optimal operation of chunk-based systems. Finally, we provide some initial insights which suggest that this bound is indeed reachable, and as such that this is an ultimate performance limit.

Speaker Bio

Giuseppe Bianchi is full professor at the University of Roma Tor Vergata. Prior to this appointment, he has been with CEFRIEL from 1991 to 1993, Assistant Professor at the Politecnico di Milano from 1993 to 1998, and Associate Professor first at the University of Palermo (1998-2003) and then at the University of Roma Tor Vergata (2003-2006). He spent 1992 as visiting researcher at the Washington University of St. Louis, MO, USA, and 9 months in 1997-1998 as visiting professor at the Columbia University of New York, NY, USA. His research interests span several areas, including Wireless LANs, performance evaluation, privacy and security, and broadband networking in general. He has been involved in several European funded project with coordination roles, and he's currently technical coordinator for the European project PRISM (Privacy-aware secure network monitoring).