【作者】 史佩昌；

【导师】 王怀民；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2012， 博士

【摘要】 托管在远程位置并通过互联网或专用网络访问的任何应用程序或服务实质上都是一种云服务。有些云服务在向地理分布用户传递的过程中会伴有大量网络流量产生，例如占互联网流量绝大比重的Web类服务和流媒体类服务等。此类大流量云服务（以下统称云服务）的数据和用户规模呈指数增长，云服务用户体验需求和访问行为复杂性在不断提升。云计算概念出现之前，为了保证Web类和流媒体类等服务质量，该类服务的传递通常使用构造于“尽力而为”互联网之上的内容分发网络（Content Delivery Networks, CDN）。然而，在多样化云服务规模化发展和大量蜂拥行为涌现的情况下，CDN已经越来越难以满足云服务按需弹性可扩展的需求，提高CDN资源利用率与保证云服务用户质量之间的矛盾日益尖锐。本文基于对云服务传递系统中实际存在问题的分析，发现如下与确保云服务用户质量并最大化CDN资源利用率之间尖锐矛盾相关的几个问题：(1)“适应性”问题，为追求资源统计复用，多业务(即云服务)通常采用共享资源的方法，该方法容易导致多业务因抢占资源而互扰，CDN很难通过自适应调节的方式解决因多业务互扰而导致服务质量和资源利用率下降的问题；(2)“经济性”问题，蜂拥热点超过CDN单节点缓存能力导致用户访问缓存命中率低，在缓存成为新瓶颈的情况下，传统以带宽为瓶颈参数的动态资源分配方法难以实现相同资源利用率情况下确保更多用户服务质量的问题；(3)“可扩展性”问题，蜂拥云服务导致其聚合资源需求频繁超过CDN服务能力上限， CDN难以实现在其资源总量不变的前提下保证过载部分用户的服务质量；(4)“公平性”问题，CDN资源通常被优先分配给受关注度高的蜂拥云服务，在CDN的资源需求接近其服务能力上限的情况下，CDN难以确保受关注度低的云服务传递资源需求和用户服务质量。针对上述问题，本文的主要研究工作和贡献：（1）面向激增蜂拥的多业务部署方法激增蜂拥是指云服务资源需求由远低于其可用资源的水平快速跃升为远高于其可用资源水平的一类蜂拥。针对“适应性”问题，本文提出了兼顾CDN资源统计复用最大化和最大程度避免蜂拥云服务互扰的多业务共存的部署方法MACE(Multiple Applications Co-Exist)。根据不同云服务资源需求的统计规律MACE方法在对现有云服务进行分类的基础上，提出了静态资源分配、动态资源补充和资源预留等自适应调度的核心机制。MACE被应用于大规模真实CDN并进行了6个月的性能测量与评估。与传统多业务共享带宽方法相比：系统资源利用率提高近20%；统计意义上与系统效率成反比的平衡系数由12%降低至5%；因CDN不同类型业务间资源互扰引起的投诉数降低为0。（2）蜂拥热点关联的CDN资源动态分配算法针对“经济性”问题，本文将CDN服务器资源的动态分配问题建模为考虑缓存瓶颈参数的多维设备选址问题(Multidimensional Facility Location Model,MFLM)。MFLM问题是一个NP完全问题，本文提出通过增加必要的前提假设和约束改变，针对CDN中流式、下载式流媒体和各种软件升级包下载等类型应用的逻辑子服务器网络动态构造的特例，给出以多缓存协同和Peer辅助为核心的服务器选择算法。在提出评估MFLM启发式算法的性能指标和性能分析模型基础上，本文对MFLM求解算法的性能进行了全面的评估分析。（3）面向缓增蜂拥的CDN服务能力适度扩展算法针对“可扩展性”问题，本文提出了动态适度终端辅助的方法(DynamicModerate Peer-assisted Method，DMPM)。DMPM主要针对云服务聚合资源需求以缓慢的速度增长至不低于CDN系统服务能力的一类缓增蜂拥。DMPM采用时间序列预测方法和径向基神经网络预测方法预测和决策了何时以及多少服务器负载需要通过终端辅助的方法被分担，并设计了一种适度提高CDN可扩展性的新型P2P机制。本文更进一步的使用从真实CDN系统收集的日志数据作为测试集来评估了预测方法的精度和DMPM方法的有效性。（4）蜂拥效应抑制的弹性覆盖网络构造方法本文将CDN中大部分甚至全部资源都被分配给蜂拥云服务而非蜂拥云服务资源需求难以保证的现象称为蜂拥效应。针对云服务蜂拥效应下的“公平性”问题，本文以VoD为研究对象提出了基于CDN的P2P覆盖网的弹性构造方法ECM（Elastic Construction Method），有效的提高了受关注低的云服务传递质量。ECM通过将多个CDN节点内请求访问相同内容的用户有序协同构造P2P覆盖网，实现利用Peer资源辅助CDN提高其服务能力扩展性的目的。ECM以扩大覆盖网边界的方式解决Peer资源稀疏问题，考虑了传统P2P流媒体骨干网流量负载过重的问题，提出了就近弹性构造P2P覆盖网的思想。模拟实验表明与在单个CDN节点内进行覆盖网络构造相比，ECM提高了用户请求接受率约41%；与传统无CDN基础设施的纯P2P系统相比，明显降低跨骨干网络流量。综上所述，本文针对云服务规模化发展形势下实际云服务传递系统CDN所面临的新挑战，研究了与云服务蜂拥现象相关的若干关键技术，对于实现高效的云服务传递具有重要的理论意义和应用价值。更多还原

【Abstract】 Any application or service that is hosted at a remote location and accessed via theInternet or private networks are essentially acloud service. Some cloud services willaccompany with a large number of network traffic generated in the process of deliveringto geo-distributed end-users, e.g., the online services of Web and streaming whichaccount for the vast proportion of Internet traffic. The scale of data and users of suchSaaS cloud services (hereinafter referred to as cloud services) with heavy traffic hasgrown exponentially, the end-users’ experience and the complexity of end-users’accessing hehavior have been rised. Before the advent of the concept of cloudcomputing, in order to ensure the Quality of Services (QoS) of the Web and streamingservices, Content Delivery Network (CDN), which is constructed over the “Best Effort”Internet, has been used to deliver them. However, in the case of the diversified cloudservices presenting large-scale development and a large number of Cloud services’Flash crowd Phenomenon (CFP) emerged, CDN has become increasingly difficult tomeet the demand of the elastic scalability of cloud services. The contradictions betweenimproving the CDN resource utilization and ensuring the QoS of end-users havebecome increasingly acute.On the basis of analyzing the existenced problems of the actual cloud servicesdelivery systems, This paper extracts the following problems related to the sharpconflict between the QoS ensured and the CDN resource utilization Maximized.(1)“Adaptivity” problem, usually shared resources is used to pursue maximization ofstatistical multiplexing among multi-applications (i.e., cloud services), however themethod easily leads to multiple applications be mutual interference for seizing sharedresources. CDN is difficult to adaptive regulation to resolve the decline of QoS andresource utilization for mutual interference aomong multiple applications.(2)“Economy” problem, popular contents caused by CFP exceed the available cachingability and lead to the accessing cache hit rate declined, which refers to that cacheresources has become a new bottleneck. On the condition, the traditional dynamicresources allocation method, which only considers bandwidth resources as thebottleneck parameter is difficult to ensure more end-users with guaranteed QoS underthe same resources utilization ratio.(3)“Scalability” problem, CFP leads to theaggregated resource demand exceeding the upper bound of CDN service capacityfrequently. CDN is difficult to guarantee the QoS of the end-users resulting in theoverload.(4)“fairness” problem, CDN resources are usually priority assigned to thecloud services with high concern which refers to CFP happens. Therefore, when theresource demand is approaching the upper limit of CDN service capacity, CDN isdifficult to satisfy the resource demand of cloud services with low concern and ensure the QoS of the end-users. In response to these challenges, the main researchworks and contributions are listed as the following:(1) Surge CFP-oriented deployment method for multiple applicationsSurge CFP refers to a class of flash crowd that when it happens the resourcesdemand of cloud services from far below the level of service capacity instantly jumpmuch higher than the level of the service capacity. In response to the “adaptivity”problem, this paper presents Multiple Applications Co-Exist (MACE) method whichoffers a tradeoff between the CDN resource statistical multiplex maximized andavoiding multiple applications mutual interference maximized. According to the statisticlaw of cloud services’ resources demand, MACE classified multiple applications intodifferent types and the key mechanisms resource static allocation, dynamic supplementand resource reserved mechanism etc. were proposed, which can be scheduledadaptively. MACE was applied to a real large scale CDN infrastructure as well as6-month measurement and analysis were given. Compared with traditional method ofmultiple applications sharing bandwidth, the bandwidth utilization is increased by about20%, the balance coefficient which is inversely proportional to the efficiency of thesystem statisticaly is decreased from12%to5%, and the number of complaint eventsaffecting the dependability of CSDN services caused by multiple applications’mutual-interference has been dropped to0.(2) the dynamic allocation model of edge resources associated with popular contentgenerated by CFPIn response to the “economy” problem, this paper formulated the dynamicallocation problem of edge resources into Multidimensional Facility Location Model(MFLM), considering the cache resource as the bottleneck resource. MFLM is aNP-Complete problem, a heuristic algorithm on the basis of increasing some necessaryassumptions and constraints violation were roposed in this paper. The key of thealgorithm is multi-cache coordination and Peer-assisted, which is in response to thespecial case of the dynamic construction of logial sub server overlay network forstreaming and file sharing applications etc. On the basis of the performance metrics andperformance analysis model proposed for the heuristic algorithm of MFLM, we gave acomprehensive evaluation of the performance of the algorithm.(3) Slow CFP-oriented “peak clippling” moderatelyIn response to the “scalability” problem, Dynamic Moderate Peer-assisted Method(DMPM) was presented. DMPM is mainly response to the slow growth CFP whichrefers to the resources demand increased to not less than the level of the service capacitywith slow speed. DMPM adopted time series analysis method and radial basis functionneural network to predict and decide when and how much CDN server loads need to be offloaded, and a novel P2P mechanism were designed to improve the scalability ofCDN. Furthermore, we use the real traces collected from an actual CDN entity toevaluate the accuracy of the two prediction method as well as the effectiveness of theDMPM.(4) The elastic construction method for overlay network with CFP effect restrainedMost or all of CDN resources are allocated to CFP and the resources demand ofcloud services with low concern are usually difficult to be satisfied. The phenomenon iscalled CFP effect. In response to the “fairness” problem under CFP effect, This paperused the VoD application as the research object and presented Elastic ConstructionMethod (ECM) for P2P VoD overlay based on CDN. ECM used the Peer-assistedmethod to achieve improving the scalability of CDN, since ECM ordered the peers indifferent CDN node who were accessing the same content collaboratively to constructP2P overlay. ECM solves the peer resource scarce problem through elastic scales theconstruction scope of P2P overlay. Meanwhile in order to solve the overloading of thebachbone network traffic generated by P2P streaming, ECM chosen the scale path basedon the distances among CDN nodes. From the simulation, compared with isolatedoverlay construction inside a single CDN node ECM improves the acceptance ratio ofend-users’ requests by41%while compared with pure P2P system without on the basisof CDN infrastructure, the traffic crossing backbone has been cut down obviously.In summary, for the new challenges caused by the cloud services development oflarge-scale, this paper give some researches about many key technologies related withCFP, which has important theoretical and actual significance in achieving efficientdelivery of cloud services with guaranteed QoS.更多还原