Are a Few Neighboring Peers Good Enough?

Most peer-assisted media streaming systems have applied a design philosophy that uses a "mesh" topology of peers: each peer connects to a small number of neighboring peers, with which it exchanges state information periodically. Requests for media segments are made to these neighboring peers on- demand. Apparently, with such a "gossiping" design principle, peers do not make decisions based on global knowledge of the entire system, sacrificing system-wide efficiency. If a peer connects to more neighbors, the gap between local and global knowledge is mitigated; however, the overhead of communicating with all neighbors periodically is proportionally higher. In this paper, using theoretical analysis based on a system of difference equations, we show the surprising result that, once the number of neighbors exceeds a very small threshold (typically 5), the peer upload capacity is fully utilized. We demonstrate that such a threshold is not affected by the scale of system, and setting the number of neighbors beyond the threshold does not help alleviate challenges caused by peer churn. Our results imply that the communication overhead of typical "gossiping" protocols can very well be subdued and contained, by using a very small number of neighbors.