摘要
由于缺乏有效的激励手段,传统的P2P (Peer-to-Peer)网络普遍存在着搭便车现象以及“公共物品的悲剧”等问题,严重影响了网络的健壮性及可用性。因此,如何构建和设计合理的激励机制成为了当前P2P网络研究中的一个热点问题。在P2P文件共享系统中,基于博弈论的激励机制有效地抑制了搭便车行为,但该机制容易引起whitewashing现象;而在P2P流媒体系统中,当前的激励机制没有综合考虑节点的贡献以及对资源的需求程度,因而出现了系统资源的不公平调度等问题。因此,研究P2P网络中的激励机制,具有重要的学术意义和应用价值。
针对上述问题,本文以文件共享系统和流媒体系统为研究对象,以经济学中的博弈理论为指导,对P2P网络中的激励机制进行了分析和研究。一方面,针对P2P文件共享系统中的whitewashing问题,引入完全信息、博弈中的均衡选择博弈模型对P2P网络进行建模,该博弈模型的优势在于它不依赖于统一的行动信号,使其过程可更有效地模拟P2P网络中节点的随机请求;此外,均衡选择博弈具有多个均衡解,其最大最小策略在系统保持均衡的状态下能有效的解决新加入节点的下载请求问题,弥补了传统激励模型的不足。模拟实验表明,所提激励机制可有效促进系统资源的公平分发,同时提高了节点对网络的贡献度,有效地约束了自私节点的行为,保障了节点和系统的效用。
另一方面,针对流媒体系统中文件播放实时性、节点传输有序性等特点,本文以不完全信息博弈的相关理论为指导对P2P流媒体系统中的激励问题展开研究。特别地,引入一级密封价格拍卖机制对系统的激励模型进行分析和建模,使系统中的服务节点根据请求节点的贡献度以及所申请资源的紧急程度,响应其资源请求。最后,我们对CoolStreaming系统进行了改进和优化,加入了激励模块。实验结果表明,所提激励模型可有效提升流媒体系统中资源调度的效率,保障了节点的服务质量。
As lacking of effective incentives, there exist some ubiquitous problems such as free-riding and'the tragedy of the commons'phenomenon in the traditional P2P (Peer-to-Peer) network which seriously affect the network's robustness and availability. Therefore, how to design and construct efficient incentive mechanism has became one of the hotspot issues of P2P studies. The game theory has been proved to be effectively restrained the free-riding phenomenon in the file sharing system. However, the incentives based on game theory can lead to whitewashing problem. Also in P2P streaming media system, the current incentive mechanism is insufficient in satisfying the requirement for resources, and the node's contribution is neglected. As a consequence, there will be some problems such as unfair scheduling of resources etc. Thus, it has a great academic significance and application value that doing research on the incentive mechanism in P2P networks.
Based on the above issues, this thesis analysis the incentive mechanism in P2P network using game theory of economics as guide, and studies of file sharing system and streaming media system as background. On one hand, the equilibrium selection game model of the complete information game is introduced to solve the whitewashing problem. The advantage of this model is that it does not dependent on unified action signals, which makes its process more efficient for simulating the random request of the network node. Moreover, this system has more than one strategies, which the maxmin strategy compensates the deficiency of the traditional incentive system by resolving the new joined node's download request while keeping the system's equilibrium. Simulation experiments shows that this incentive mechanism is not only able to promote the fair distribution of the system resources, it is also increased the contribution of the nodes by restrain the selfish nodes and ensures the system utility.
On the other hand, according to the real-time request of playback time and the sequential transmission of media file, this thesis studies on the incentive mechanism in streaming media system with incomplete information game as guide. Especially, the first-price sealed big auction is introduced to modeling the incentive mechanism which makes the resources distribution according to the level of the node's contribution and the urgency of the resource request. Finally, we has improved and optimized the CoolStreaming system, and added the incentive module. The result of the experiment indicates that the proposed incentive mechanism is able to enhance the scheduling efficiency, and ensure the QoS of the nodes.
引文
[1]Adar E, Huberman B."Free riding on Gnutella"[C], First Monday,2000,5(10):32-35.
[2]Gnutella. Available at:http://www.gnutella.com/.
[3]D. Fudenberg, J. Tirole. "Game Theory"[M], MIT Press, Cambridge MA,1991.
[4]Napster. Available at:http://www.napster.com/.
[5]BitTorrent. Available at:http://bittorrent.com/.
[6]Emule. Available at:http://www.emule.com/.
[7]Golle.P, K.Leyton-Brown I.Mironov. "Incentives for Sharing in Peer-to-Peer Networks"[C], In Proceedings of ACM Conference on Electronic Commerce,2002.
[8]J.Ioannidis, S.Ioannidis, A.Keromytis V.Prevelakes, "Fileteller:Paying and getting paid for file storage"[C], In Proceedings of Financial Cryptography, March 2003.
[9]Landon P. Cox, Christopher D. Murray, Brian D. Noble. "Pastiche:making backup cheap and easy"[C], In Proceedings of the 5th Symposium on Operation Systems Design and Implementation. Dec.2002.
[10]taobao. Available at:http://www.taobao.com/.
[11]Qixiang Sun, Hector Garcia-molina. "SLIC:A Selfish Link-Based Incentive Mechanism for Unstructured Peer-to-Peer Networks"[C], In Proceedings of International Conference on Distributed Computing Systems,2004:506-515.
[12]Chunqi Tian, Zou Shihong, Wang Wendong. "An Efficient Attack-Resistant Trust Model for P2P Networks"[J], In International Journal of Computer Science and Network Security,2006, 6(11):251-258.
[13]Yu-mei Liu, Yang Shou-bao, Guo Lei-tao. "A Distributed Trust-based Reputation Model in P2P System. Software Engineering"[C], In Proceedings of Artificial Intelligence, Networking, and Parallel/Distributed Computing. Tailand:IEEE Computer Society,2007:294-299.
[14]V. Pai, K. Kumar, K. Tamilmani, V. Sambamurthy, A. E. Mohr. "Chainsaw:Eliminating Trees from Overlay Multicast"[C], In Proceedings of IPTPS, New York, USA, Feb.2005:127-140.
[15]Bram Cohen. "Incentives Build Robustness in BitTorrent"[C], In Proceedings of IPTPS,2003.
[16]Seung Jun, Mustaque Ahamad. "Incentives in BitTorrent induce free riding"[C], In ACM SIGCOMM,2005.
[17]Yun Tang, Lifeng Sun, Meng Zhang, Shiqiang Yang, Yuzhuo Zhong. "A Novel Distributed and Practical Incentive Mechanism for Peer to Peer Live Video Streaming"[C], In Proceedings of the International Conference on Multimedia Computing and Systems,2006:1533-1536.
[18]D.Levin, K.LaCurts, N.Spring. B.Bhattacharjee. "BitTorrent is an Auction:Analyzing and Improving BirTorren's Incentives"[C], In ACM SIGCOMM, Seattlem, WA, USA,2008.
[19]Thomas Silverston, Olivier Fourmaux, Jon Crowcroft. "Towards an Incentive Mechanism for Peer-to-Peer Multimedia Live Streaming Systems"[C], In Peer-to-Peer Computing,2008: 125-128.
[20]A. Habib, J. Chuang. "Incentive mechanisms for peer-to-peer media streaming"[C].In International Workshop on Quality of Service,2004.
[21]Michal Feldman, John Chuang. "Overcoming free-riding behavior in peer-to-peer systems"[C], In ACM SIGecom Exchanges,2005,4(5):41-55.
[22]X. Zhang, J. Liu, B. Li, T.-S. P. Yum. "CoolStreaming/DONet:A Data-Driven Overlay Network for Efficient Live Media Streaming"[C], In IEEE INFOCOM, Miami, USA, Mar.2005.
[23]Stephen P. Boyd, Arpita Ghosh, Balaji Prabhakar, Devavrat Shah. "Gossip algorithms:design, analysis and applications"[C], In IEEE INFOCOM,2005:1653-1664.
[24]Ferguson D. "P2P File Sharing-the Evolving Distribution Chain"[C], Presentation at the 1st Annual P2P Media Summit, Washington, USA, Jun.2006.
[25]C. Lv, P. Cao, E. Cohen, Kai Li, S. Shenker. "Search and replication in unstructured peer-to-peer networks"[C], In Proceedings of International Conference on Supercomputing,2001.
[26]Sean Rhea, Brighten Godfrey, Brad Karp, John Kubiatowicz, Sylvia Ratnasamy, Scott Shenker, Ion Stoica, Harlan Yu. "OpenDHT:a public DHT service and its uses"[C], In ACM SIGCOMM Conference,2005:73-84.
[27]Chu Y, Rao S G, Zhang H. "A case for end system multicast"[C], In ACM Sigmetrics, Santa Clain, California,2002:1-12.
[28]End System Multicast. Available at:http://esm.cs.cmu.edu/.
[29]Edoardo Mollona, Gian Paolo. "CoopNet:an Agent-based model to Explore Knowledge Integration and Free Riding in Large Organizations"[M], Published in 2008.
[30]V. N. Padmanabhan, K. Sripanidkulchai. "The Case for Cooperative Networking"[C], In Proceedings of the First International Workshop on Peer-to-Peer Systems, Cambridge, MA, USA, March,2002.
[31]M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron, A. Singh. "SplitStream: High-bandwidth content distribution in a cooperative environment"[C], In Proceedings of the International Workshop on Peer-to-Peer Systems, Berkeley, CA, February,2003.
[32]J. Jannotti, D. K. Gifford, K. L. Johnson, M. F. Kaashoek, J. W. O'Toole Jr. "Overcast:reliable multicasting with an overlay network"[C], In Proceedings of the Fourth Symposium on Operating System Design and Implementation, October,2000.
[33]Alfarez Abdul-Rahman, Stephen Hailes. "Supporting Trust in Virtual Communities"[C], In Proceedings of International Conference on System Sciences, Hawaii,2000.
[34]Q. Sun, D. C. Sturman. "A Gossip-Based Reliable Multicast for Large-Scale High-Throughput Applications"[C], In Proceedings of International Conference on Dependable Systems and Networks, July,2000.
[35]Xiaofei Liao, Hai Jin, Yunhao Liu, Lionel M. Ni, Dafu Deng. "AnySee:Peer-to-Peer Live Streaming"[C], In IEEE INFOCOM,2006.
[36]PPLive. Available at:http://www.pplive.com/.2008.
[37]PPStream. Available at:http://www.ppstream.com/.
[38]SETI@home. Available at:http://setiathome.berkeley.edu/.
[39]OICQ. Available at:http://www.qq.com/.
[40]MSN. Available at:http://messenger.msn.com/.
[41]Skype. Available at:http://www.skype.com/.
[42]P. Golle, K. Leyton-Brown, I. Mironov, M. Lillibridge. "Incentives for sharing in peer-to-peer networks"[C], In Proceedings of ACM Conference on Electronic Commerce,2001.
[43]Y. B. Tang, H. M. Wang, W. Dou. "Trust Based Incentive in P2P Network"[C], In Proceedings of the IEEE International Conference on E-Commerce Technology for Dynamic E-Business, Beijing, China, September 2004.
[44]Roslan Ismai A. J, Colin Boy. "A survey of trust and reputation systems for online service provision"[R], In Decision Support Systems,2007,2(43):618-644.
[45]eBay. Available at:http://www.ebay.com/.
[46]Chrysanthos Dellarocas. "The digitization of word-of-mouth:promise and challenges of online feedback mechanism"[C], Management Science,2003,10(49):1407-1424.
[47]Sepandar D. Kamvar, Mario T. Schlosser, Hector Garcia-molina. "The Eigentrust algorithm for reputation management in P2P networks"[C], In Proceedings of World Wide Web Conference Series,2003:640-651.
[48]Chiranjeeb Buragohain, Divyakant Agrawal, Subhash Suri. "A Game Theoretic Framework for Incentives in P2P Systems"[C], In Proceedings Conference of Peer-to-Peer Computing,2003: 48-56.
[49]Nash J. "Equilibrium points in n-person games"[C], In Proceedings of the National Academy of Sciences,1950:48-49.
[50]Nash J. "Non-cooperative games"[C], In Proceedings of Annals of Mathematics,1951:286-295.
[51]张维迎.博弈论与信息经济学[M],上海人民出版社,2005.
[52]Drew Fudenberg,Jean Tirole博弈论[M],中国人民大学出版社,2004.
[53]肖条军.博弈论及其应用[M],上海三联书店,2004.
[54]Eric Rasmusen博弈与信息:博弈论概论[M],韩松,张倩伟,庞立永等译,中国人民大学出版社,2009.
[55]R. T. B.Ma, S. C., M. Lee, J. C. S. Lui, D. K. Y. Yau. "A game theoretic approach to provide incentive and service differentiation in P2P networks"[C], In Proceedings of the Joint International Conference on Measurement and modeling of Computer Systems. New York, NY, USA,2004:189-198.
[56]K. Lai, M. Feldman, I. Stoica, J. Chuang. "Incentives for cooperation in peer-to-peer networks"[C], In Proceedings of Economics of P2P systems,2003.
[57]M. Feldman, K. Lai, I. Stoica, J. Chuang. "Robust incentive techniques for peer-to-peer networks"[C], In Proceedings of ACM Conference of Electronic Commerce,2004.
[58]A. Blanc, Y. K. Liu, A. Vahdat. "Designing incentives for peer-to-peer routing"[C], In IEEE INFOCOM,2005:374-385.
[59]T. B. Ma, S. C. M. Lee, J. C. S. Lui, D. K. Y. Yau. "Incentive and service differentiation in P2P networks:a game theoretic approach"[C], In IEEE/ACM Transactions on Network, Oct.2006, 14(54):978-991.
[60]O. Loginova, H. Lu, X. H. Wang. "Incentive schemes in peer-to-peer networks"[C], Published in B. E. J. Theoretical Econ.,2(9),2009.
[61]Thomas Bocek, Michael Shann, David Hausheer, Burkhard Stiller. "Game Theoretical Analysis of Incentives for Large-scale, Fully Decentralized Collaboration Networks"[C], In Proceedings of IEEE International Symposium on Parallel and Distributed Processing,2008.
[62]Minaxi Gupta, Paul Judge, Mostafa H. Ammar. "A reputation system for peer-to-peer networks"[C], In Proceedings of the International Workshop on Network and Operating Systems Support for Audio and Video,2003.
[63]余一娇,金海.对等网络中的搭便车行为分析与抑制机制综述[J],计算机学报,1(31),Jan2008.
[64]H. Deshpande, M. Bawa, H. Garcia-Molina. "Streaming live media over peer-to-peer network"[R], Technical report, Stanford University,2001.
[65]S. Banerjee, B. Bhattacharjee, C. Kommareddy. "Scalable Application Layer Multicast"[C], In ACM SIGCOMM, Pennsylvania, USA, Aug.2002.
[66]D. A. Tran, K. A. Hua, T. T. Do. "A Peer-to-Peer Architecture for Media Streaming"[J], In IEEE Journal on Selected Areas in Communications,2004,1(22):121-133.
[67]N. Magharei, R. Rejaie. "PRIME:Peer-to-Peer Receiver-Driven Mesh-based Streaming"[C], In IEEE INFOCOM, Alaska, USA, May.2007.
[68]Guang Tan, Stephen A. Jarvis. Daniel P. Spoonet. "A Payment-based Incentive and Service Differentiation Mechanism for Peer-to-Peer Streaming Broadcast"[C], In Proceedings International Workshop on Quality of Service,2006:41-50.
[69]A. J. Ganesh, A.-M. Kermarrec, L. Massoulie. "Peer-to-Peer membership management for gossip-based protocols"[C], In IEEE Transactions on Computers, Feb.2003.
[70]Y. Cui, D. Li, J. Wu. "Impact of Buffer Map Cheating on the Streaming Quality in DONet"[C], In Proceedings International Conference on Computational Science,2007:817-824.
[71]NS2. Available at:http://www.isi.edu/nsnam/ns/.
[72]GT-ITM. Available at:http://www-static.cc.gatech.edu/projects/gitim/.
[73]Figueiredo D, Shapiro J, Towsley D. "Incentives to promote availability in Peer-to-Peer anonymity systems"[C], In Proceedings of the 13th IEEE International Conference on Network Protocols, Boston,2005:110-121.
[74]N. Semret, R. R.-F. Liao, A. T. Campbell, A. A. Lazar. "Pricing, Provisioning and Peering: Dynamic Markets for Differentiated Internet Services and Implications for Network Interconnections"[J], In IEEE Journal on Selected Areas of Communications, Dec 2000.
[75]Richard T. B. Ma, Sam C. M. Lee, John C. S. Lui, David K. Y. Yau. "Incentive and service differentiation in P2P networks:A Game Theoretic Approach"[C], In IEEE/ACM Transactions on Networking,2006,5(14):978-991.
[76]路卫娜.开放网络环境中的激励机制研究[D],中国科学技术大学博士学位论文,2009.
[77]Kun Tao, Weihan Zhang, Hai Zhong, Xuejie Zhang. "A Fair Allocation and Sharing Incentive Approach in P2P Network Based on Supervising Game"[C], In Proceedings of ICWMMN2010, 2010:339-343.