A Preferential Attachment Model for Tree Construction in P2P Video Streaming

• Marcio N. Miranda UFAL
• Daniel R. Figueiredo UFRJ

Abstract

Tree-based peer-to-peer (P2P) video streaming systems rely on a video dissemination tree to deliver video to peers. In order to offer good quality of service, two fundamental aspects should guide the construction of the video dissemination tree: low node degree and short distances to the server. In this paper, we propose a very simple growth process to construct the video dissemination tree. Our generative model is based on the preferential attachment principle, where preference is given in terms of node quality. The proposed model has a single parameter to weigh the relative importance of node degree and node distance on assessing node quality. We investigate our model through simulations and find that surprisingly good video dissemination trees are usually generated. In particular, topological properties of generated trees are never extreme and average tree quality is mostly comparable (and sometimes superior) to carefully designed dissemination trees. Our results indicate that the proposed model is capable of self-organizing nodes into good trees under various assessments of node quality.

References

Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1):47–97.

Banerjee, S., Lee, S., Braud, R., Bhattacharjee, S., and Srinivasan, A. (2004). Scalable resilient media streaming. In Proc. of ACM International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV).

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science, 286:509–512.

Bonald, T., Massoulié, L., Mathieu, F., Perino, D., and Twigg, A. (2008). Epidemic live streaming: optimal performance trade-offs. In SIGMETRICS’08: Proc. of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pages 325–336.

Carra, D., Lo Cigno, R., and Biersack, E. (2007). Graph based analysis of mesh overlay streaming systems. IEEE Journal on Selected Areas in Communications (JSAC), 25(9):1667–1677.

Hei, X., Liang, C., Liang, J., Liu, Y., and Ross, K. (2007). A measurement study of a large-scale P2P IPTV system. IEEE Transactions on Multimedia, 9(8):1672–1687.

hua Chu, Y., Rao, S. G., Seshan, S., and Zhang, H. (2002). A case for end system multicast. IEEE Journal on Selected Areas in Communications (JSAC), 20(8):1667–1677.

Kumar, R., Liu, Y., and Ross, K. (2007). Stochastic fluid theory for P2P streaming systems. INFOCOM 2007: Proc. of the 26th IEEE International Conference on Computer Communications, pages 919–927.

Li, B., Yik, K., Xie, S., Liu, J., Stoica, I., Zhang, H., and Zhang, X. (2007). An empirical study of the Coolstreaming system. IEEE Journal on Selected Areas in Communications (JSAC), 25(9):1627–1639.

Liu, J., Rao, S., Li, B., and Zhang, H. (2008a). Opportunities and challenges of peer-to-peer internet video broadcast. Proceedings of the IEEE, 96(1):11–24.

Liu, Y., Guo, Y., and Liang, C. (2008b). A survey on peer-to-peer video streaming systems. Peer-to-Peer Netw Appl, 1(1):18–28.

Sevim, V. and Rikvold, P. A. (2006). Effects of preference for attachment to low-degree nodes on the degree distributions of a growing directed network and a simple food-web model. Phys. Rev. E, 73(056115).

Small, T., Liang, B., and Li, B. (2006). Scaling laws and tradeoffs in peer-to-peer live multimedia streaming. In MULTIMEDIA’06: Proc. of the 14th annual ACM international conference on Multimedia, pages 539–548.