Skip navigation

P2P Streaming Over Dynamic Random M-Regular Graphs

Event Date: January 26, 2012
Speaker: Joohwan Kim
Speaker Affiliation: Coordinated Science Laboratory
University of Illinois
Sponsor: Communications, Networking, Signal & Image Processing
Time: 2:00 PM
Location: EE 317
Contact Name: Professor Xiaojun Lin
Contact Phone: (765) 494-0626
Contact Email:

We are motivated by the problem of designing simple distributed algorithms for P2P (peer-to-peer) streaming applications that can achieve high throughput and low delay, while allowing the neighbor set maintained by each peer to be small. We present an algorithm which requires each peer to maintain a list of M incoming and M outgoing edges, where the edges are randomly selected by taking advantage of peer churn. The minimum cut in the resulting graph topology is shown to have the maximum possible capacity. This shows that it may be possible to achieve the maximum streaming capacity even when each peer only transmits to and receives from Θ(1) neighbors. Further, we show that the distance between any two peers in the network is Θ(log N), with high probability, where N is the number of peers in the network. From this result, we show that the proposed algorithm can achieve a streaming delay of Θ(log N) when the streaming rate is less than a half of the maximum capacity.  Simulations indicate that Θ(log N) delay is still achievable for a higher streaming rate.


This is a joint work with Prof. R. Srikant at the University of Illinois at






Dr. Joohwan Kim received the B.S. degree from Yonsei University, Seoul, Korea, in 2004, and the M.S. degree and the Ph. D degree from Purdue University, West Lafayette, IN, in 2006 and 2010, respectively. He is currently a post-doctorate research associate of the Coordinate Science Laboratory at the University of Illinois at Urbana-Champaign. His research interests range over a variety of fundamental problems in wireless and wireline networks. He is currently interested in the development of efficient P2P streaming systems.