Performance tradeoffs in structured peer to peer streaming

We consider the following basic question: a source node wishes to stream an ordered sequence of packets to a collection of receivers, which are in KK clusters. A node may send a packet to another node in its own cluster in one time step and to a node in a different cluster in TcTc time steps (Tc>1)(Tc>1). Each cluster has two special nodes. We assume that the source and the special nodes in each cluster have a higher capacity and thus can send multiple packets at each step, while all other nodes can both send and receive a packet at each step. We construct two (intra-cluster) data communication schemes, one based on multi-trees (using a collection of dd-ary interior-disjoint trees) and the other based on hypercubes. The multi-tree scheme sustains streaming within a cluster with O(dlogN)O(dlogN) maximum playback delay and O(dlogN)O(dlogN) size buffers, while communicating with O(d)O(d) neighbors, where NN is the maximum size of any cluster. We also show that this protocol is optimal when d=2d=2 or 3. The hypercube scheme sustains streaming within a cluster, with O(log2(N))O(log2(N)) maximum playback delay and O(1)O(1) size buffers, while communicating with O(log(N))O(log(N)) neighbors, for arbitrary NN. In addition, we extend our multi-tree scheme to work when receivers depart and arrive over time. We also evaluate our dynamic schemes using simulations.

► We construct two streaming schemes based on multi-trees and hypercubes, respectively.
► Two schemes achieve different levels of playback delay/buffer space trade-off.
► Our multi-tree scheme works when receivers depart and arrive over time.
► We evaluate our dynamic schemes using simulations.