Maximizing Resilient Throughput in Peer-to-Peer Network

Bo Liu, Fan Qiu, Yanchuan Cao, Bin Chang, Yi Cui, Yuan Xue

.

DOI: 10.4236/cn.2011.33021                

Abstract

A unique challenge in P2P network is that the peer dynamics (departure or failure) cause unavoidable disruption to the downstream peers. While many works have been dedicated to consider fault resilience in peer selection, little understanding is achieved regarding the solvability and solution complexity of this problem from the optimization perspective. To this end, we propose an optimization framework based on the generalized flow theory. Key concepts introduced by this framework include resilience factor, resilience index, and generalized throughput, which collectively model the peer resilience in a probabilistic measure. Under this framework, we divide the domain of optimal peer selection along several dimensions including network topology, overlay organization, and the definition of resilience factor and generalized flow. Within each sub-problem, we focus on studying the problem complexity and finding optimal solutions. Simulation study is also performed to evaluate the effectiveness of our model and performance of the proposed algorithms.

Keywords

Peer-to-Peer, Resilient, Throughput, Maximizing

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	M. Guo and M. Ammar, “Scalable Livideo Streaming to Cooperative Clients Using Time Shifting and Video Patching,” Proceedings of the International Conference on Computer Communications and Networks, Chicago, 11-13 October 2004.
[2]	V. Padmanabhan, H. Wang and P. Chou, “Resilient Peer-to-peer Streaming,” 11th IEEE International Conference on Networking Protocols, Atlanta, 4-7 November 2003, pp. 16-27. doi:10.1109/ICNP.2003.1249753
[3]	M. Castro, P. Druschel, A. M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, “Splitstream: High-Band Width Multicast in Cooperative Environments,” Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, Vol. 37, No. 5, 2003, pp. 298-313. doi:10.1145/945445.945474
[4]	V. N. Padmanabhan, H. J. Wang, P. A. Chou and K. Sripanidkulchai, “Distributing Streaming Media Content Using Cooperative Networking,” Proceedings of the 12th International Workshop on Network and Operating Systems Support for Digital Audio And Video, New York, 2002, pp. 177-186. doi:10.1145/507670.507695
[5]	K. Sripanidkulchai, A. Ganjam, B. Maggs and H. Zhang, “The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points,” ACM SIGCOMM Computer Communication Review, Vol. 34, No. 4, 2004, pp. 107-120. doi:10.1145/1030194.1015480
[6]	M. Bishop, S. Rao and K. Sripanidkulchai, “Considering Priority in Overlay Multicast Protocols under Heterogeneous Environments,” Proceedings of 25th IEEE International Conference on Computer Communications, Barcelona, April 2006, pp. 1-13. doi:10.1109/INFOCOM.2006.140
[7]	G. Tan and S. Jarvis, “On the Reliability of DHT-Based Multicast,” Proceeding of International Conference on, Computer Communications and Networks, Honolulu, 13-16 August 2007.
[8]	D. Leonard, Z. Yao, V. Rai and D. Loguinov, “On Lifetime-Based Node Failure and Stochastic Resilience of Decentralized Peer-to-peer Networks,” IEEE/ACM Transactions on Networking, Vol. 15, No. 3, 2007, pp. 644-656.
[9]	R. Ahuja, T. Magnanti and J. Orlin, “Network Flows: Theory, Algorithms, and Applications,” Englewood Cliffss, Bergen, 1993.
[10]	K. Wayne, “A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow,” Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Atlanta, 1-4 May 1999, pp. 19-28.
[11]	E. Tardos and K. Wayne, “Simple Generalized Maximum Flow Algorithm,” 7th International Integer Programming and Combinatorial Optimization Conference, Graz, 9-11 June 1999, pp. 1-16.
[12]	K. Wayne and L. Fleischer, “Faster Approximation Algorithms for Generalized Flow,” Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1999.
[13]	Y. Cui, Y. Xue and K. Nahrstedt, “Max-min Overlay Multicast: Rate Allocation and Tree Construction,” IEEE International Workshop on Quality of Service, Montreal, June 2004.
[14]	N. Deo, “Graph Theory with Applications to Engineering and Computer Science,” Prentice Hall Inc., Upper Saddle River, 1994.
[15]	R. Cohen and G. Kaempfer, “A Unicast-Based Approach for Streaming Multicast,” Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Vol. 1, 2001, pp. 440-448. doi:10.1109/INFCOM.2001.916727
[16]	D. Kostic, A. Rodriguez, J. Albrecht and A. Vahdat, “Bullet: High Bandwidth Data Dissemination Using an Overlay Mesh,” Proceedings of the 19th ACM Symposium on Operating System Principles, Vol. 37, No. 5, 2003, pp. 282-297. doi:10.1145/1165389.945473
[17]	J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts, “On-line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling,” Journal of the Association for Computing Machinery, Vol. 44, No. 3, 1997. doi:10.1145/258128.258201
[18]	B. Awerbuch, Y. Azar, S. Plotkin and O. Waarts, “Competitive Routing of Virtual Circuits with Unknown Duration,” Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, 1995, pp. 321-327. doi:10.1145/314464.314508
[19]	B. Awerbuch, Y. Azar and S. Plotkin, “Throughput-Competitive Online Routing,” Proceedings of the 1993 IEEE 34th Annual Foundations of Computer Science, Washington, 1993. doi:10.1109/SFCS.1993.366884
[20]	A. Goel, M. Henzinger and S. Plotkin, “Online Throughput-competitive Algorithm for Multicast Routing and Admission Control,” Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, Vol. 5, 1998.
[21]	Y. Cui, B. Li and K. Nahrstedt, “On Achieving Optimized Capacity Utilization in Application Overlahy Networks with Multiple Competing Sessions,” 16th annual ACM Symposium on Parallel Algorithms and Architectures, Barcelona, 27 - 30 June 2004, pp. 11-19.