网络服务系统的动力学建模与分析研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
本世纪初,随着对等网络(peer-to-peer, P2P)技术在因特网上广泛应用,其良好的扩展性以及较高的资源利用率等优点影响着网络技术的发展,网络发展的趋势也从集中式系统逐步向分布式系统过渡。如今,文件共享、即时通信、社交网络以及在线视频点播等网络服务系统遍布网络,影响着人们的生活、工作以及学习等各个方面。以BitTorrent为代表的P2P文件共享系统通过充分利用其中各用户节点的带宽资源、存储空间来实现文件的共享,而以在线视频点播(如优酷、土豆以及爱奇艺等)为代表的流媒体服务系统通过采用内容分发网络(Content Distribution Network, CDN)技术将服务部署到距离用户仅有“一跳”的网络边缘,并通过采用P2P技术加强边缘服务器之间的交互,从而可以提高服务质量、增大系统吞吐量和降低服务提供商部署成本。本文将着重研究网络服务系统中两种典型系统:BitTorrent和流媒体服务系统。通过分析研究这两种系统的结构、主要流程以及主要影响因素,并将各因素进行数学描述,建立其动力学模型,描述系统的动态演化过程,并进行具体的模型分析以揭示影响系统演化的各因素之间的相互关系以及对系统整体性能的影响,为网络服务系统的研究、设计以及实现提供理论支持。
     本文首先分析了BitTorrent和流媒体服务系统的结构、主要流程以及影响它们动态演化的主要因素,然后分别对这两种系统进行动力学建模,并在动力学模型的基础上,对流媒体服务系统的稳定性进行讨论。本文的主要工作与创新性表现在以下几个方面:
     第一,建立了BitTorrent文件共享系统的动力学模型。BitTorrent文件共享系统是P2P系统的典型应用,用户在享受下载的同时还向其他用户提供上传,充分体现P2P系统的对等性和交互性。以往针对BitTorrent的建模研究着重于全系统范围内的节点数目的变化,将影响系统变化(尤其是节点数目的变化)的主要因素归结于带宽资源的限制,忽略了其他因素对于BitTorrent系统的影响,本文采用在较小尺度上针对BitTorrent系统中单个节点的动态演化过程进行建模分析,将影响BitTorrent用户之间交互演化过程的硬件条件、文件属性、用户行为以及算法策略等因素进行数学描述,建立其动力学微分方程模型。该模型能够准确描述各因素对于BitTorrent系统中节点间交互过程的影响,同时也反映了各因素之间的相互影响关系。
     第二,建立了流媒体服务系统的动力学模型。传统的针对流媒体服务系统的研究侧重于单纯算法策略的研究,而忽略了系统自身的演化过程以及这些算法策略之间的相互影响。本文首先对流媒体服务系统结构进行抽象化描述,用虚拟服务节点代表流媒体服务系统覆盖网络中的边缘服务子系统,进而将流媒体服务系统抽象成一个由虚拟服务节点组成的逻辑网络;然后分析影响虚拟服务节点与用户以及与其他虚拟服务节点交互过程中的影响因素,主要包括硬件条件、用户行为、服务属性以及算法策略等因素,并将这些影响因素进行数学描述,建立流媒体服务系统的动力学微分方程模型。该模型能够准确刻画用户接入到服务系统,以及服务子系统之间的交互过程,并能够反映各因素之间的相互关系以及他们对于系统整体性能的影响。
     第三,提出了流媒体服务系统中边缘服务子系统的状态稳定性判据。边缘服务子系统距离用户仅有“一跳”之遥,是直接面向用户的服务提供者,其稳定性将直接影响用户的体验。本文从边缘服务子系统的整体性以及其运行实际意义出发,定义了边缘服务子系统的稳定性状态,并在边缘服务子系统的动力学模型的基础上,分析得到了边缘服务子系统状态的稳定性判据。
     第四,提出了一种基于边缘服务子系统状态稳定性判据的接入控制算法。接入控制是边缘服务子系统的重要组成成分,控制着用户行为对于系统的影响。本文在上述稳定性分析的基础上,对流媒体服务系统提出了一种接入控制算法。当服务请求到达时,首先判断边缘服务子系统当前状态的稳定性,若当前状态为稳定状态,则接入请求;否则拒绝接入直到当前状态变为稳定状态。
The P2P (peer-to peer) technology has been influencing the development of the Internet with its good extensibility and effective utilization of resources since its emer-gence in the beginning of the21st century. The development of the Internet began to shift focus from the centralized system to the distributed system. The network service systems, such as file-sharing, instant messaging, social network and streaming service system, have changed the way people live, work, and study. One example is the P2P file-sharing system, with the BitTorrent software as a typical one, which makes full use of users'resources including bandwidth and storage space to share files. Another one is the streaming service system represented by the video-on-demand systems such as Youku, Tudou and iQiYi. The system distributes services to the edge of the Internet by adopting the CDN (content delivery network) technology. Furthermore, by strengthen-ing the interaction between proxy servers using the P2P technology, the stream service system can improve the quality of services (QoS), expand the throughput of the system and reduce the running cost of the network service providers. This dissertation focuses on the two typical network service systems, which are BitTorrent and network stream-ing service system. Structures, main working process and influencing factors of the two systems are analyzed in the dissertation. The influencing factors are mathematically ex-pressed by a series of differential equations. By setting up a dynamic model comprising of the differential equations, the dissertation analyses the evolution of the systems and influence of the factors on the systems as well on each other. The model can work as theoretical support for the study, design, and application of the network service systems.
     In the dissertation, the structure, main processes and the influence factors of the BitTorrent and streaming service system are analyzed, then the dynamic models are set up to describe the evolution of the BitTorrent and streaming service system. Further-more, we discuss the stability of streaming service system based on the dynamic model. The contribution of this dissertation are listed in the following part.
     Firstly, a novel dynamic model of BitTorrent P2P file-sharing system is proposed in this thesis. Users of the BitTorrent system, which is a typical application of P2P system, not only download the file but also upload the file to others. This reflects the character of parity, interaction, good extensibility of P2P. The past research put their attention on the evolution of the downloaders'and seeds'number in the BitTorrent sys-tem, and assumed that the main factor influence the evolution is the users'bandwidth, while other influencing factors have been ignored. Instead of studying the macroscopic characteristics of the whole system, the author models one single node in the BitTorrent. The factors that influence the interaction between nodes in the BitTorrent are expressed in mathematical forms, and a dynamic model is set up to describe the interaction be-tween the users of the BitTorrent system in an accurate manner, and also to analyze the influence of the factors on one another.
     Secondly, a dynamic model of the streaming service system is proposed. The tra-ditional research for the streaming service systems placed emphasis on the algorithms and ignored the interaction between the algorithms. The streaming service system can be seen as a logical network, which is composed of virtual service nodes that repre-sent the streaming service subsystem. Then the factors, such as hardware, user be-havior, algorithms, etc. are analyzed and expressed in mathematical forms. Then the dynamic model of the streaming service system is set up to describe the interaction between clients and the virtual service nodes and also between virtual service nodes. Inter-relations of the influencing factors can also be revealed by the analysis.
     Thirdly, a criterion for the stability of the streaming service system is proposed in this thesis. The service subsystem is at the edge the Internet, which serve the users directly. The stability of the subsystem influence the user experience directly. We con-sider the subsystem as a whole and analyze the actual conditions, and then define the stability of the streaming service system. Furthermore, based on the model already set up, the criterion for stability of the streaming service system can be gained through analysis.
     Lastly, an admission control policy based on the stability criterion of the streaming service system is proposed. The admission control policy is a dominant factor in decid-ing whether the users'requests can be admitted by the system. Based on the stability criterion, the author designs an admission control policy under which users'requests will be admitted when the system is stable and rejected when the system is unstable.
引文
[1]Hendrik S, Klaus M. Internet Study 2008/2009[OL].2009, http://www.ipoque.com/sites/default/files/med iafiles/documents/internet-study-2008-2009.pdf.
    [2]Jie L, Andreas A, Viktor N, et al. A Five Year Perspective of Traffic Pattern Evolution in a Residential Broad-band Access Network[C]. Proceedings of Future Network and Mobile Summit 2012, Berlin, GER:IEEE Com-puter Society,2012.1-9.
    [3]中国互联网信息中心.中国互联网络发展状况统计报告[OL].2014, http://www.cnnic.net.cn/hlwfzyj/h lwxzbg/hlwtjbg/201403/P020140305346585959798.pdf.
    [4]Umar J,Italo C, David C,et al. PoiRoot:investigating the root cause of interdomain path changes[C]. Proceed-ings of ACM SIGCOMM Computer Communication Review 2013, New York, USA:ACM,2013.183-194.
    [5]G L. Make data useful[OL].2014, http://sltes.google.com/site/glinden/Home/StanfordDataMining.2006-11-28.ppt,.
    [6]WangJ. A sruvey of web caching schemes for the internet[C]. Proceedings of ACM SIGCOMM Computer Communication Review 1999, New York, USA:ACM,1999.36-46.
    [7]Rizzo L, Vicisano L. Replacement policies for a proxy cache[J]. IEEE/ACM Trans. Networking,2000, 8(2):158-170.
    [8]Athena V, George P. Content delivery networks:status and trends[J]. IEEE Internet Computing,2003,7(6):68-74.
    [9]George P, Athena V. Insight and perspectives for content delivery networks[J]. Communications of the ACM-Personal information management,2006,49(1):101-106.
    [10]Salvatore S, Cecilia M, Mirco M, et al. Track globally, deliver locallyimproving content delivery networks by tracking geographic social cascades[C]. Proceedings of WWW'll, Hyderabad, IND:ACM,2011.457-466.
    [11]Wessels D, Claffy K. ICP and the Squid web cache[J]. IEEE Journal on Selected Areas in Communications, 1998,16(3):345-357.
    [12]Shim J, Scheuermann P, Vingralek R. Proxy cache algorithms:design, implementation, and performance[J]. IEEE Trans. Knowledge and Data Engineering,1999, 11(4):549-562.
    [13]陈贵海,李振华.对等网络:结构、应用与设计[M].北京:清华大学出版社,2007.
    [14]Ion S, Robert M, David K, et al. Chord:A scalable peer-to-peer lookup service for internet applications[C]. Proceedings of SIGCOMM'01, San Diego, USA:ACM,2001.149-160.
    [15]Sylvia R, Paul F, Mark H, et al. A scalable content-addressable network[C]. Proceedings of SIGCOMM'01, San Diego, USA:ACM,2001.161-172.
    [16]BitTorrent. [OL], http://www.bittorrent.com/.
    [17]BitComet. [OL], http://www.bitcomet.com/index-zh-cn.php.
    [18]FlashGet. [OL], http://www.flashget.com/cn/.
    [19]uTorrent. [OL], http://www.utorrent.com.
    [20]Johan P, Paeel G, eta. A measurement study of the bittorrent peer-to-peer file-sharing system[M]. Netherlands: Delft University of Technology,2004.
    [21]Hyung O, Song H. Metafile-Based Scalable Caching and Dynamic Replacing Algorithms for Multiple Videos Over Quality-of-Service Networks[J]. IEEE Trans. Multimedia,2007,9(7):1535-1542.
    [22]James W, Philip Y. Fragmental Proxy Caching for Streaming Multimedia Objects[J]. IEEE Trans. Multimedia, 2007,9(1):147-156.
    [23]Wei T, Echehard S, Muhammad M, et al. Proxy Caching for Video-on-Demand Using Flexible Starting Point Selection[J]. EEEE Trans. Multimedia,2009, 11(4):716-729.
    [24]Nong X, Yingjie Z, Fang L, et al. Dual queues cache replacement algorithm based on sequentiality detection[J]. Science China Information Sciences,2012,55(1):191-199.
    [25]Kun-Lung W, Philip S Y, Joel W. Segmentation of multimedia streams for proxy caching[J]. IEEE Trans. Multimedia,2004,6(5):770-780.
    [26]Jun L, Zhenjing C. Sliding-window caching algorithm for streaming media server[C]. Proceedings of ICIS'2009, Seoul, Korea:ACM,2009.1152-1159.
    [27]UmaMaheswari D, Ramana P, Malolan C, et al. On the Partial Caching of Streaming Video[C]. Proceedings of IWQoS'2012, volume 4, Coimbra, POR:IEEE,2012.
    [28]Bram C. Incentives build robustness in BitTorrent[C]. Proceedings of Workshop on Economics of P2P Systems, volume 6, Berkeley, CA, USA,2003.
    [29]Orlie B, Arun A. Comparison and analysis of measurement and parameter based admission control methods for Quality of Service (QoS) provisioning[C]. Proceedings of MILCOM'2010, San Jose, CA:IEEE,2010. 184-188.
    [30]Arieh G, Zvi R. A restricted complete sharing policy for a stochastic knapsack problem in B-ISDN[J]. IEEE Trans. Communications,1994,42(7):2375-2379.
    [31]Frederick L, Jelena M, Samuel C. Comparison and analysis of measurement and parameter based admission control methods for Quality of Service (QoS) provisioning[C]. Proceedings of 7th International Conference on Computer Communications and Networks, Lafayette, LA:IEEE,1998.584-593.
    [32]Chuan-Ching S, Yuan-Bin H, Pey-Jiuan H. Dynamic Preemption Call Admission Control Scheme Based on Markov Decision Process in Traffic Groomed Optical Networks[J]. IEEE/OSA Journal of Optical Communi-cations and Networking,2011,3(4):300-311.
    [33]Yi-Hsien T, Wu E K, Gen-Huey C. An Admission Control Scheme Based on Online Measurement for VBR Video Streams Over Wireless Home Networks[J]. IEEE Trans. Multimedia,2008,10(3):470-479.
    [34]Yanbing L, Man M. Survey of Admission Control Algorithms in IEEE 802.lle Wireless LANs[C], Proceedings of FCC'2009, WuHan, CHN:IEEE,2009.230-233.
    [35]Ellen H. Round-robin scheduling for max-min fairness in data networks[J]. IEEE Journal on Selected Areas in Communications,1991,9(7):1024-1039.
    [36]Manolis K, Stefanos S, Costas C. Weighted round-robin cell multiplexing in a general-purpose ATM switch chip[J]. IEEE Journal on Selected Areas in Communications,1991,9(8):1265-1279.
    [37]赵辉,何连跃.基于异构分布式存储系统的动态反馈负载均衡技术[J].计算机研究与发展,2009,46:322-327.
    [38]Networks P. [OL].2014, http://www.proceranetworks.com/index.php.
    [39]Demetris A, Michalis P, Nick N, et al. Monitoring three National Research Networks for Eight Weeks:Observa-tions and Implications[C]. Proceedings of IEEE Network Operations and Management Symposium Workshops 2008, Salvador da, Bahia:IEEE,2008.153-156.
    [40]Gregor M, Anja F, Vern P, et al. On dominant characteristics of residential broadband internet traffic [C]. Pro-ceedings of ACM SIGCOMM conference on Internet measurement, NY, USA:ACM,2009.90-102.
    [41]Kenjiro C. Trends in Japanese Residential Traffic[OL].2014, http://www.iijlab.net/-kjc/papers/isoc-bwp anel.pdf.
    [42]Craig L, Scott IJ, et a. Internet inter-domain traffic[C]. Proceedings of ACM SIGCOMM'2010, NY, USA: ACM,2010.75-86.
    [43]Jian-Guang L, Qian Z, Yun T, et al. A Trace-Driven Approach to Evaluate the Scalability of P2P-Based Video-on-Demand Service[J]. IEEE Trans. Parallel and Distributed Systems,2009,20(1):59-70.
    [44]Michael Z, Kyoungwon S, Yu G, et al. Characteristics of YouTube network traffic at a campus network-Measurements, models, and implications[J], Computer Networks,2009,53(4):501-514.
    [45]Soam A, Brian S, Peter P. Characterizing user access to videos on the World Wide Web[C]. Proceedings of SPIE Multimedia Computing and Networking 2000, San Jose, CA:SPIE,2000.130-141.
    [46]Kunwadee S, Bruce M, Zhang H. An analysis of live streaming workloads on the internet[C]. Proceedings of SIGCOMM'2004, Taormina, ITA:ACM,2004.41-54.
    [47]Hyung O, Song H. Metafile-Based Scalable Caching and Dynamic Replacing Algorithms for Multiple Videos Over Quality-of-Service Networks[J]. IEEE Trans. Multimedia,2007,9(7):1535-1542.
    [48]Zipf K. Human Behavior and the principle of least effort:an introduction to human ecology [M]. Oxford, England:Addison-Wesley Press,1949.
    [49]Lee B, Pei C, et a. Web caching and Zipf-like distributions:evidence and implications[C]. Proceedings of INFOCOM'1999,NY,USA:IEEE,1999.126-134.
    [50]Kim K, Song Y, Han Y. ZipfAllocation:an algorithm for static allocation of movies in a cluster of video servers[J]. Software:Practice and Experience,2011,41(6):695-716.
    [51]Kaihui L, Changqiao X, Yuanhai Z, et al. Optimal Prefix Caching and Data Sharing strategy[C]. Proceedings of IEEE International Conference on Multimedia and Expo 2008, Hannover, GER:IEEE,2008.465-468.
    [52]Gaurav A, Gaurav K, Divyashikha S. Optimal Prefix Caching and Data Sharing strategy[C]. Proceedings of CCSEIT'2012, India:ACM,2012.689-693.
    [53]D L, J C, JH K, et al. LRFU:A Spectrum of Policies that Subsumes the Least Recently Used and Least Frequently Used Policies[J]. IEEE Trans. Computers,2001,50(12):1352-1361.
    [54]Michael E, Tibor S, al. Knapsack problem-based piece-picking algorithms for layered content in peer-to-peer networks[C]. Proceedings of AVSTP2P'2010, Firenze, ITA:ACM,2010.71-76.
    [55]Johan P, Pawel G, Dick E, et al. The Bittorrent P2P File-Sharing System:Measurements and Analysis[C]. Proceedings of IPTPS'2005, NY, USA:Springer Berlin Heidelberg,2005.205-216.
    [56]M I, Guillaume U K, et a. Dissecting BitTorrent:Five Months in a Torrent's Lifetime[C]. Proceedings of 5th International Workshop on Passive and Active Network Measurement 2004, Antibes, FR:Springer Berlin Heidelberg,2004.1-11.
    [57]John G, David R. Ext ract ing Value from Chaos[OL].2014, http://www.emc.com/collateral/analyst-repor ts/idc-extractingvalue-from-chaos-ar.pdf.
    [58]崔春生,李光,吴祈宗.基于Vague集的电子商务推荐系统研究[J].计算机工程与应用,2011,47(10):237-239.
    [59]廉捷,周欣,曹伟,刘云.新浪微博数据挖掘方案[J].清华大学学报(自然科学版),2011,51(10):1300-1305.
    [60]Pieter N, Michiel H. Mining Twitter in the cloud:A case study[C]. Proceedings of the 2010 IEEE 3rd Interna-tional Conference on Cloud Computing, Miami, USA:IEEE,2010.107-114.
    [61]Greg L, Brent S, Jeremy Y. Amazon.com recommendations:item-to-item collaborative filtering[J]. IEEE Internet Computing,2003,7(1):76-80.
    [62]Liang E, Soe-Tsyr Y. Where's the Money? The Social Behavior of Investors in Facebook's Small World[C]. Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM2012, Istanbul, Turkey:IEEE,2012.158-162.
    [63]奚宏生.随机过程引论[M].中国科学技术大学出版社,合肥,安徽,2009.
    [64]殷保群,奚宏生,周亚平.排队系统性能分析与Markov控制过程[M].中国科学技术大学出版社,合肥,安徽,2004.
    [65]Lu S, Yin B.Guo d. Admission control for P2P-based Media Delivery Network[C]. Proceedings of CCC'2010, Beijing, CHN:IEEE,2010.1494-1499.
    [66]Fushou L, Baoqun Y, Jing H, et al. Admission control with elastic QoS for video on demand systems[J], International Journal of Automation and Computing,2012,9(5):467-473.
    [67]巫旭敏,殷保群,黄静,郭东.流媒体服务系统中一种基于数据预取的缓存策略[J].电子与信息学报,2010,32(10):2440-2445.
    [68]巫旭敏.分布式服务系统基于分层的存储资源管理研究[D]:[博士][D].中国科学技术大学,2012.
    [69]Ye T, Di W, Kam N. Modeling, Analysis and Improvement for BitTorrent-Like File Sharing Networks[C]. Proceedings of INFOCOM'2006, Barcelona, Spain:IEEE,2006.1-11.
    [70]S N, B L, A B, et al. The state of peer-to-peer simulators and simulations[C]. Proceedings of ACM SIG-COMM'2007, volume 37. ACM,2007.95-98.
    [71]Fall K, Varadhan K. The network simulator ns-2[OL].2014, http://www.isi.edu/nsnam/ns.
    [72]Weishuai Y, Nael A G. GPS:a general peer-to-peer simulator and its use for modeling BitTorrent[C]. Proceed-ings of MASCOTS'2005, Atlanta, USA:IEEE,2007.425-432.
    [73]James K, Keith R.计算机网络:自顶向下方法与Internet特色.机械工业出版社,2005.
    [74]Vishal M, Wei-Bo G, Don T. Stochastic Differential Equation Modeling and Analysis of TCP-Windowsize Behavior [C]. Proceedings of Performance'1999, Istanbul, Turkey,1999.
    [75]Dongyu Q, R S. Modeling and performance analysis of BitTorrent-like peer-to-peer networks[C]. Proceedings of SIGCOMM'2004. ACM,2004.367-378.
    [76]Dongyu Q, Weiqian S. Global stability of Peer-to-Peer file sharing systems[J]. Computer Communications, 2008,31(2):212-219.
    [77]Lei G, Songqing C, et a. Modeling, Analysis and Improvement for BitTorrent-Like File Sharing Networks[C]. Proceedings of INFOCOM'2006, Barcelona, Spain:IEEE,2006.1-11.
    [78]Minglu L, Jiadi Y, Jie W. Free-Riding on BitTorrent-Like Peer-to-Peer File Sharing Systems:Modeling Anal-ysis and Improvement[J]. IEEE Trans. Parallel and Distributed Systems,2008,19(7):954-966.
    [79]Baoqun Y, Dong g, Jing H, et al. Modeling and analysis for the P2P-based media delivery network[J]. Mathe-matical and Computer Modelling,,2012,55(3-4):1529-1539.
    [80]Petar M, David M. Kademlia:A Peer-to-Peer Information System Based on the XOR Metric[C]. Proceedings of IPTPS'2002:Peer-to-Peer Systems, MA, USA:Springer Berlin Heidelberg,2002.53-65.
    [81]Ruchir B, Jan M, Pei C, et al. Improving Traffic Locality in BitTorrent via Biased Neighbor Selection[C]. Proceedings of ICDCS'2006, Lisboa, Portugal:IEEE,2006.66.
    [82]Bo L, Yi C, et a. Locality-Awareness in BitTorrent-Like P2P Applications[J]. IEEE Trans. Multimedia,2009, 11(3):361-371.
    [83]Stevens B, Arnaud L, Walid D. Pushing BitTorrent locality to the limit. Computer Networks,2011,55(3):541-557.
    [84]Xiaonong L, Baoqun Y, et a. Admission control scheme for distributed service systems based on model and prediction[C]. Proceedings of CCC'2012, Hefei, CHN,2012.5518-5523.
    [85]朱里越,杨坚,胡晗,奚宏生.多业务流媒体服务系统的自适应服务组合算法[J].小型微型计算机系统,2011,31(9):1702-1706.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700