延迟优化的内容分发技术研究

发布时间：2018-04-13 00:06

本文选题：内容分发 + 镜像服务器　；参考：《中国科学技术大学》2016年博士论文

【摘要】：内容分发网络(Content Delivery Network, CDN)作为网络中缓解大量并发访问引起的拥塞问题的有效技术,得到了国内外学术界和产业界的广泛关注。在内容分发网络中,内容被复制并存储在多个镜像服务器中,这使得内容可以快速地被终端用户访问,大大降低了终端用户的平均请求延迟。由于更多的镜像服务器会带来更大的部署和维护成本,合理地部署镜像服务器对于内容分发网络至关重要。另外,镜像服务器的容量是有限的,如何选择镜像内容分发到各镜像服务器中,直接决定了内容分发网络的网络性能。基于内容分发网络中现有的研究成果,本文分别从镜像服务器部署和镜像内容分发两个方向研究了内容分发网络中的相关问题,以降低网络中的平均请求延迟。在镜像内容分发问题中,从静态内容分发方法和动态内容分发方法两方面进行了研究。其中,对于动态内容分发方法,本文结合无线Mesh网络和无线融合网络的特征,分别设计了相应的内容分发机制。本文的主要研究内容及贡献如下四个方面。一、基于网络中请求的统计特性与镜像服务器的服务模型,研究了内容分发网络中的镜像服务器部署方法,以降低网络中的平均请求延迟,提高CDNs应用的网络性能。每个的用户请求被模拟为独立泊松分布,而镜像服务器被作为M/M/1排队模型。在给定请求率、镜像服务器的服务率、最大可部署的镜像服务器数量和服务器的请求等待时间期望值上界的条件下,我们所研究的问题是从待选位置中选出一个子集来部署镜像服务器,通过最小化网络中正在传输的请求数与镜像服务器队列中等待的请求数之和,达到网络中平均请求延迟的最优化。我们对该问题进行了形式化定义,并证明了其NP困难性。禁忌搜索算法和拉格朗日松弛算法被用于解决该问题,其中禁忌搜索算法引入禁忌列表来避免重复搜索,拉格朗日松弛算法可以获得较好的近似比。实验证明,我们所提出的算法均能获得较低的平均网络时延,并有效地用于实际CDNs的镜像服务器部署。二、内容被划分为多个内容对象,对于每个内容对象,将其热度定义为该内容对象的请求在所有请求中所占的百分比。根据内容对象的热度信息,我们可以将内容预分配到各个镜像服务器上,用户请求便可被定向至最近的缓存有所需内容对象的镜像服务器。我们既考虑了内容的热度,也考虑了镜像服务器的服务能力,通过合理的模型构建,对基于内容热度的静态镜像内容分发问题进行了形式化的定义。由于该问题的NP困难性,本文提出了两个启发式算法：贪心移除算法和禁忌搜索算法,用于得到可行的静态镜像内容分发方案。最后,仿真实验数据显示,我们的方法能够以较高的概率得到可行的镜像内容分发方案,且禁忌搜索算法能够大大降低CDNs中的平均请求延迟。三、针对无线Mesh网络中的内容镜像分发问题,结合内容对象的分布密度与内容热度之间的最优关系,考虑到Mesh路由器的服务模型,提出了一个全新的动态分布式四阶段内容分发算法,以适应无线Mesh网络环境。首先,依据无线Mesh网络的分布式特点,对网络拓扑使用划分算法进行分布化。然后,根据内容对象的热度信息,计算出每个内容对象所需的镜像数目。在网络拓扑划分的基础上,结合网络中的请求模型和服务模型,使用分布式的算法生成内容镜像的分发策略,以降低网络中的平均请求时延。最后,采用协作式的内容分发方式,将内容镜像分发到各个Mesh路由器。仿真实验证明,该算法可在不明显增加网络负载的情况下,有效地降低网络中的平均请求时延。四、研究了结合广播网络和4G/LTE的无线融合网络中基于推送的动态内容分发,内容对象通过广播和4G/LTE蜂窝网络单播两种方式推送到终端用户。在这样的网络模型下,热门内容对象通过广播的方式,推送给网络覆盖范围内的所有终端用户：其余的内容对象通过4G/LTE蜂窝网络,根据用户的需求发送至终端用户。基于这样的内容分发流程,我们设计了高效的基于BCSA算法的无线融合网络的内容分发机制,摒弃了以往优先将最热门的内容资源进行广播的方案,使用了近似算法,合理地对广播的内容对象进行选择,优化广播内容请求的总带宽。在蜂窝网络部分,我们对缓冲队列的长度与网络延迟和丢包率的关系进行了研究。最后,通过仿真实验对基于BCSA算法的无线融合网络的效果进行了实验。实验结果证明本文所提出的内容分发机制能够大大地降低4G/LTE的带宽消耗,降低网络的平均时延。
[Abstract]:Content distribution network (Content Delivery Network, CDN) effective technology as to relieve the congestion problem caused by a large number of concurrent access, has been widespread concern in academia and industry. In the content distribution network, the content is copied and stored in a mirror server, which makes the content can quickly be terminal user access, greatly reducing the average request terminal user delay. Because more mirror server will bring greater deployment and maintenance costs, reasonable deployment of the mirror server for content distribution network is vital. In addition, the mirror server capacity is limited, how to select the image content distributed to the mirror server, directly determine the performance of the network content distribution network. Content distribution network based on the existing research results, this paper from the mirror server deployment and image content distribution Two directions on issues related to content distribution network, in order to reduce the network delay. The average request distribution problem in the mirror in the content distribution method and dynamic content from the static content distribution method two aspects were studied. Among them, the dynamic content distribution method, combining with the characteristics of wireless Mesh networks and wireless network integration and designed the corresponding content distribution mechanism in four aspects. The main contents and contributions of this paper are as follows. First, the statistical characteristics of network service model in the request from the mirror server based on the research content distribution network in the mirror server deployment method, to reduce the average request in the network delay, improve the network performance of CDNs application. Each user request is modeled as independent Poisson distribution, and the mirror server as M/M/1 queuing model. The request rate in a given, the mirror server. The service rate, the mirror server number and server maximum deployment request waiting time upper bound for the conditional expectation, we study the problem is to select a sub set from the candidate position to deploy the image server by being transmitted in the network is minimized the number of requests and mirror like waiting for the server requests in a queue and the number of the average request latency, network optimization. We reached a formal definition of the problem, and prove its NP problem. The tabu search algorithm and Lagrange relaxation algorithm is used to solve this problem, the tabu search algorithm is introduced to avoid repeated search of tabu list, Lagrange relaxation algorithm can obtain better approximation ratio. Experiments show that our proposed algorithm can obtain the average network delay is low, and effectively used in CDNs image server deployment. Two, the content is divided As a content object for each content object, will define the heat as a percentage of the content object request for all requests. According to the contents of the object heat information, we can be content pre assigned to each image on the server, the user requests can be set to have the required content object to the nearest cache the mirror server. We not only consider the content of the heat, also considered the mirror server service ability, through constructing reasonable model of distribution static image based on heat content are defined formally. Because the NP difficulty of the problem, this paper proposes two heuristic algorithms: greedy algorithm and remove tabu search algorithm for static image content distribution scheme is feasible. Finally, simulation experiments show that our method can be feasible with high probability in the mirror Content distribution scheme, and the tabu search algorithm can greatly reduce the average delay in the CDNs request. Three, according to the image content in wireless Mesh network distribution problems, combined with the optimal relationship between content objects and contents of heat distribution density, taking into account the service model of Mesh router, the paper proposes a new four stage dynamic distributed content distribution algorithm, in order to adapt to the wireless Mesh network. Firstly, based on the distributed characteristics of wireless Mesh networks, the network topology distribution using partitioning algorithm. Then, according to the contents of the object heat information, calculate the number of image content of each desired object. On the basis of the network topology division, combination model and service request in the network model, distribution strategy algorithm to generate the image using the distributed content, in order to reduce the average request in the network delay. Finally, using collaborative content The content of hair, mirror is distributed to all Mesh routers. Simulation results show that the algorithm can be without significantly increasing network load conditions, effectively reduce the average request in the network delay. Four, the distribution of dynamic content push based on wireless integrated network broadcast network and 4G/LTE, through the content object broadcast and unicast 4G/LTE cellular network in two ways to end users. In such a network model, popular content object by means of broadcast, pushed to the network covering all terminal users within the scope of the object: the rest of the content through a 4G/LTE cellular network, according to the needs of users to send to the terminal users. This is based on the contents of flow distribution and we design efficient wireless network fusion algorithm BCSA based content distribution mechanism, instead of priority will be the most popular content resources for broadcast Using the scheme, approximation algorithm, reasonably to broadcast content object selection, optimization of the total bandwidth request. The broadcast content in a cellular network, we on the buffer queue length and network latency and packet loss rate were discussed. Finally, through the simulation experiment of BCSA algorithm of wireless integrated network based on the results. The experimental results show that the proposed content distribution mechanism can greatly reduce 4G/LTE bandwidth consumption, reduce the average delay of the network.

【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP393.02

【相似文献】