在基于P2P的流媒体系统中CDN服务器负载优化算法

张 惊

同济大学软件学院，上海 201804

1 背景介绍

随着高清视频的普及，VOD系统的运行成本越来越高。降低VOD的成本成为一个重要的问题。如Lu[1]所述，VOD系统往往是采用P2P与CDN相结合的方式来减缓系统的成本。

图1

其中P2P技术可以利用用户的上传带宽，有效地降低了传输压力。但是P2P网络本身稳定性较差，且Free rider的问题存在使得P2P带宽的不足，单纯的P2P网络无法满足VOD系统的带宽要求。因此，我们需要CDN来进行补充。

CDN则可以解决最后一公里问题，有效降低访问延迟，并且其带宽充足。在CS架构下，使用CDN进行辅助传输可以在提升用户体验的同时，有效地降低传输的成本。但是CDN相对于P2P网络来说价格依然较为昂贵，如何降低CDN的使用成本也成为了一个重要的问题。

在传统的CDN技术中，CDN服务器是缓存全部的数据。但是视频的体积较大，在每一个节点中都保存视频的副本会对CDN的造成较大的存储压力。因此，CDN节点的服务器会缓存部分数据，通过相邻节点的协助共同完成请求的处理。除此以外，我们还可以通过控制CDN服务器内的缓存数据量，动态平衡CDN的运营成本与请求处理的效率。

在这个情况下，如何设计CDN节点服务器所缓存的数据以提升CDN服务器所能处理的请求数量，也即提升CDN节点服务器的缓存命中率成为了一个重要的问题。我们在这里提出了一个基于马尔科夫链的缓存预测算法，以提升缓存命中率的算法。

本文下面将阐述并验证我们的算法。在第三部分中，我们将阐述我们算法的思想与原理。之后，在第四部分，我们根据原理设计一个优化CDN性能的算法。在第五部分我们将使用仿真实验验证的算法。

2 相关工作

在基于P2P的VOD系统中，P2P的传输策略是一个重要的课题。P2P的传输策略直接决定了P2P网络的性能，以及与P2P网络协同工作的CDN所面对的数据请求。

在P2P网络中，Peer之间的传输数据分为三个步骤。首先，是Peer在尚未缓冲的数据中，选择一部分尚未完成缓冲的数据向其它Peer请求。在Bittorrent等P2P网络中，传输的数据被分成了多个等大的piece。在这里，我们称呼这个步骤的算法为piece选择算法。其次，是Peer选好了piece之后，在邻居Peer当中选择一个处理该piece请求的Peer。这里，我们称这一步的算法为Peer选择算法。最后，接到请求的Peer会决定是否处理这个请求。若Peer不打算处理该请求，则称之为阻塞算法。有不少文献在这三个算法上有所研究。

在piece选择算法方面，传统的P2P网络采用的是rarest first算法来选择piece。Rarest first算法能够很好地提高P2P网络的鲁棒性，但是却无法适应流媒体传输中边下边播的需求。因此，Abdelhalim 等[2]采用了滑动缓冲窗口的设计。Peer会在缓冲播放进度前方一定区域内的划定一个要缓冲的piece的窗口，并提前进行缓冲。这个窗口会随着视频的播放进度前进而前进。

在优化Peer选择策略的方向中，以往的作者主要从Peer之间的数据量的差异与Peer之间传输延迟、物理位置等方面进行考虑。Liang[2]引入了BPB算法。这个算法根据Peer的缓冲进度，为Peer选择缓冲进度相似的邻居Peer进行传输。Wen[3]则进一步地考虑了Peer的缓冲窗口，将BPB算法与缓冲窗口相结合。这样就避免了缓冲大量数据的Peer的上传带宽无法满足其他Peer的请求，而缓冲数据量较少的Peer有剩余带宽无法利用的问题。

Mushtaq[4]，Ahmed[5]，Abdelhalim[6]等 人 在 处 理P2P传输视频的时候，不仅仅考虑Peer缓冲进度的相似性，还综合了Peer之间的带宽、距离、RTT等特性进行考虑。Xie[7]等人则设计了P4P的概念，Peer优先选择处于同一个ISP内部的Peer传输数据，这样一方面可以降低Peer之间的传输延迟，另一方面可以降低跨ISP的数据传输，降低Peer之间的传输对ISP造成的压力，构成了对ISP友好的P2P网络。

而在与CDN结合的算法中，Lu[1]则考虑到CDN服务器与Peer的可靠性的区别，给予缓冲窗口中不同的piece不同的优先级。

由于传输过程中，Peer会根据其邻居Peer的特性进行选择。因此，结构化的网络由于容易控制受到了在线流媒体系统的欢迎。Ahmed[5]，Zhang[8]采用了多层的结构，根据Peer所能够提供的数据特性，将Peer划分至不同的层中，层内的Peer优先互相传输。

除此以外，在使用CDN的网络中，Zhan[2]设计了一套使用CDN+P2P的网络，并在其中设计了分层的CDN。不同层的CDN之间互相协作，实现了良好的扩展性与性能。

3 P2P网络

1）概述。

我们的算法要在有限的CDN服务器存储空间的情况下，尽量保证CDN服务器的对Peer的请求的处理能力，因此我们需要尽可能地提高CDN服务器的缓存的数据的命中率。而CDN服务器的缓存命中率则可以使用下式计算：

其中，IC(inCache)、SRM与I都是长度为T的向量，每一个元素与视频数据中的一个piece相对应。其中，IC每一个元素均为布尔值，只取0或者1，元素为1表示相应的piece被CDN服务器缓冲了，元素为0表示相应的piece没有被CDN服务器缓冲。而SRM的元素则是代表CDN服务器接收到的对应piece请求数量。向量I所有的元素都为1。

CDN服务器的存储空间有限，则IC向量中只有有限个元素为1。因此我们要提高Cache的命中率，应该缓存请求最多的那些piece。而如何构造IC向量，也即在CDN服务器选择哪些piece进行缓存就是我们算法研究的核心问题。

在以Bittorrent为代表的P2P软件当中，为了方便将数据交由不同的Peer进行传输。原始的数据被划分为了多个等大或近似等大的piece。在我们的传输视频的算法中，我们假设每个Piece所包含的帧数量是一致的。我们按照Peer当前视频所播放的帧所属的piece，将Peer分为T+1个状态，其中最后一个状态是指Peer完成播放的状态。我们使用一个状态空间为[1，T+1]的离散随机过程来表示Peer在播放过程中的状态转移。使用随机变量X表示Peer当前播放的帧所在的Piece。

2）P2P的数据传输算法。

在Peer播放视频过程中，Peer的请求分别由CDN与P2P网络处理。由前边所述，Peer在请求数据过程中进行了Piece选择算法，Peer选择算法与阻塞算法三个步骤。

由于流媒体系统要求做到边下边播，因此下载需要做到顺序下载，因此Piece选择算法会依赖于Peer当前的播放进度。如Sheu[9]等所做的，在基于P2P的传输视频的流媒体系统中，Peer在piece选择过程中，不仅仅缓冲即将解码的piece，而是会在当前播放进度前建立一个滑动缓冲窗口，选择这个窗口内部的piece进行预缓冲，滑动缓冲窗口的情况如下图所示。

图2

在上图中，黑色部分代表了已经完成解码的piece，蓝色的是当前正在解码的piece，而绿色的则是在缓冲窗口内的piece。

缓冲窗口的使用是为了避免带宽波动带来的播放卡顿。我们设这个窗口的长度为w。piece选择算法要为piece选择一个邻居Peer或者CDN服务器处理请求。在Lu[1]和张勇[12]等人设计的算法当中，Peer选择算法要根据piece在播放前所剩余的缓冲时间为其选择不同质量的Peer进行处理。Piece的剩余缓冲时间可以使用变量ΔT，如下图所示。

实践教学是高校教学环节的重要组成部分，它的独特功能和作用，是其它教育环节无法替代的，高等学校实践教学是在教师指导下，学生在特定的环境中,通过自身努力完成教育目标的教学过程。通过实践环节教学，可以加深对课程理论教学内容的理解；给学生提供实践与理论相结合的空间，提高学生对知识学习兴趣，增强学生自主学习的积极性；提高学生的实践动手能力；启发学生高昂的创新意识。安徽理工大学电气工程及其自动化专业实践教学内容主要包含有课程实验、认识实习、生产实习、课程设计、实训、毕业设计与毕业实习、创新能力拓展项目等。

图3

由上图可以得知，ΔT只取决于Piece在滑动缓冲窗口当中的次序，与Piece在整个视频数据中的次序无关。而由此，我们可以使用一个T*(T+1)的矩阵PS来表示Peer的选择结果。矩阵的第i行表示X=i的情况下，Peer向CDN服务器请求每一个数据段的概率。而我们可以得知PS矩阵如下所示。

图4

在Lu[1]和张勇[12]等人设计的算法当中，Peer根据ΔT的值，会将数据交由不同的Peer处理或者CDN处理。ΔT越小，则在该piece的数据的缓冲时间越少，为了保证视频播放不发生卡顿，其对传输的质量要求越高。因此ΔT越小，向CDN请求该piece的概率越高。因此，在图4当中下式成立。

3）视频播放中的随机过程。

正常情况下，用户在观看视频的过程中，视频的播放进度是按照时间顺序连续变化的。而网络等原因导致的播放卡顿，其概率取决于终端与服务器之间网络链路的丢包率、带宽拥塞等网络环境。而这些网络问题在视频播放的时间内变化的可能性相对较低，我们可以将该概率视为定值。而用户的VCR操作则是基于视频内容的，也就是指取决于当前进度所播放的视频内容。因此，客户端的视频进度的变化只取决于当前的播放进度，其无后效性满足马尔科夫链的成立条件。由此我们可以将客户端视频播放的随机过程看作是马尔可夫过程。

该马尔科夫过程的状态空间为[1，T+1]，其中最后一个状态表示视频播放完成。而播放完成的节点不会向其它状态跳转，该状态是一个吸收壁。我们可以用一个长度为T+1的向量p表示Peer的状态分布。而该马尔科夫链的初始状态是Peer初次进入在线视频网络是所处的状态。在线视频网络中，终端加入网络时，其视频的播放进度必然是处于视频的第一个piece中。因此，Peer的初始情况下的状态概率分布p必然是{1，0，0...0}。

我们可以使用向量p计算一个Peer向CDN请求数据段的概率分布，如下式：

在上式中，向量pr是一个长度为T的向量，其第i个元素表示Peer向CDN服务器请求第i个piece的概率。而CDN服务器所接受到的数据段请求可以用下式计算：

我们设一个Peer的播放进度状态转移矩阵为ST(State Transmit)。该矩阵ST为的矩阵。则我们可以得到如下的状态转移矩阵。在下面的矩阵当中，元素pi，j代表该Peer从第i个状态转移到第j个状态的概率。

图5

在这里，我们设一个Peer在k时刻的状态X的概率分布为p(k)，则有下式：

在播放过程中，Peer可能正常播放视频，也可能进行VCR操作，亦或者因为网络的原因而发生卡顿。其中，视频正常播放是高概率性事件，而VCR以及网络原因的视频卡顿是低概率事件。在这里，我们不考虑属于低概率事件的VCR操作与网络状况所引起的Peer状态变化。则可以得到的Peer的ST矩阵如下式所示：

图6

由于Peer的状态分布p的初始状态的概率分布是{1， 0， 0...0}，以及图（5）的矩阵的特性，Peer的状态X在发生状态变化时遵循下式：

则一个Peer在时刻t请求第i个数据段的概率bi满足如下式：

上式中，bi不为0的条件是确保第i个数据段在Peer的缓冲窗口内。在整个P2P系统中，CDN服务器所收到的第i个数据段的请求数量可以用下式计算：

其中，nj(t)是t时刻X为j的Peer的数量。我们可以知道nj(t)的特性如下式所示：

则bi的计算公式可以做如下的变换：

由上式，我们可以根据t时刻的第i个数据段请求量，预测t+1时刻的第i+1个数据段请求量。我们可以继续简化上式。

而由ps的性质，我们可以知道：

因此，bi(t)远远大于psT。我们可以在上式中忽略psT，其式子可以改为下式：

由这个式子，我们可以使用当前时刻的数据请求量来估算下一个时刻除第一个数据段以外的数据段的请求量。

而对于第一个数据段的请求量预测取决于对新加入的Peer数量的预测。在传统的Bittorrent以及Chang[11]所设计的视频传输系统中，Peer加入网络开始播放之前，首先都需要进行包括向Tracker服务器注册在内的初始化过程。我们可以通过统计处在初始化过程中的Peer数量来预测下一个时刻X为1的Piece的数量。

4 缓存替换算法

我们的替换算法的目的是尽可能提高缓存命中率，因此，我们需要预测未来的请求数量最多的piece。由前面的式子所述，我们可以通过当前时间段内每一个piece的请求数量，估算下一个时刻的piece请求分布。我们设CDN服务器能够给我们的算法的存储空间可以存储N个piece。我们对第1到第T-1个piece的请求量进行排序，然后选择请求量最多的N个Piece。我们设这些Piece的序号组成一个集合C(t)。则我们可以得到集合S(t+1)满足下式。

则S(t+1)就是我们预测得到的下一个时刻CDN所接受的请求最多的数据段的集合。而CDN在下个时刻缓存这些数据段就可以有效地提升缓存的命中率。

我们的算法只需要记录当前阶段的piece请求分布就可以。而Peer的特性与我们的算法无关。我们算法不必了解整个P2P网络的全局信息，因此不需要额外的控制信息，不会对传输性能造成额外的负担。而且我们的算法也不需要Peer端有额外的适配逻辑，可以与Peer的各种传输策相适应，有良好的可扩展性。

我们算法的计算过程分为统计piece数量与piece请求排序两部分。其中统计piece数量这一部分的计算量是与请求数量NR有关的，其时间复杂度是O(NR)的，而空间复杂度则是O(T)的。而排序算法则是与视频的piece数量有关。同一个视频副本，其piece分割是不变的，因此排序的运算复杂度是恒定的O(Tlog(T))。因此，算法对CDN服务器的运算压力并不大。

5 实验设计

在使用CDN服务器辅助传输数据的P2P网络中，系统会有一个中心服务器，保存完整的数据请求，并将视频数据分发给各个CDN服务器。而各个CDN服务器则缓存视频数据，并将数据分发给各个终端。CDN服务器是分布于不同的ISP不同的物理地区中，以降低数据在ISP之间进行长途传输所产生的延迟以及对ISP网络所产生的压力。

我们在仿真实验中，将Peer分成了多个组，每一个组作为一个独立的ISP。每个组内的Peer互相传输的延迟较低，而组之间的传输延迟较高。每个组内有一个CDN服务器。除此以外，我们还设计一个在线媒体的中央服务器。中央服务器存储了完整的视频副本。整个P2P网络中的Peer在向服务器发出请求的时候，首先向自己所在的ISP的CDN服务器发出请求。若CDN服务器没有缓存请求所要求的piece，则Peer转向中央服务器发出请求。

作为对比，我们将我们的缓存替换算法与经典的LRU等算法做比较，统计不同的算法下缓存的命中率。

在实验过程中，Peer加入P2P网络采用了泊松分布，该泊松分布的。而Peer在播放完成后到离开P2P网络的时间则采用了指数分布来模拟。而Peer所能缓冲的增强层数量则是平均分布。实验中传输的SVC视频分为4层。每一种Peer的上行带宽则设定为下行带宽的一半。

我们的模拟环境是在NS3模拟器的基础上运行。Peer之间的传输协议则是由流行的Bittorrent协议修改而来。

在这里，请求成功地在CDN服务器缓存中找到所需要的数据的概率被称为缓存命中率。缓存命中率体现了我们的算法对缓存的预测的准确率。

我们在CDN服务器上存储了整个视频副本的一定比例的数据。我们分别试验了存储30%、50%、70%的情况的结果。实验结果如图所示。在图中，棕色的线是我们的算法的结果。而蓝色的线则是LRU算法的运算结果。图中绿色的线则是代表了存储率的标准线。

图7

图8

图9

从图中可以看到，随着存储率的降低，由于覆盖的数据段的减少，LRU算法越来越无法体现其预测的效果，命中率越来越差，逐渐低于标准线。而我们的算法则依然能够保持较好的命中率，多数情况下都能够比标准线要好。

这是因为LRU算法在替换的时候，根据其所存储的数据的请求记录来决定移除的数据。而随着存储空间的减少，LRU所存储的数据令越来越少，其所能够依据的请求记录也越来越少。因此，其性能会随着存储空间的减少而下降。

而我们的算法则是从全局出发，根据CDN接收到的整体的请求分布情况来决定数据的交换。因此，存储空间的大小并不会对性能造成影响。

因此，我们的算法相对于传统的缓存替换算法LRU有更好的预测性能。

[1]Lu Z， Gao X， Huang S， etal. Scalable and reliable live streaming service through coordinating CDN and P2P[C]. Proceedings of the International Conference on Parallel and Distributed Systems -ICPADS， 2011.

[2]Zi’ao Zhan， Xu Q. A Stochastic Push Scheme of Streaming Media Partial Content Based on P2P[J].Journal of Networks， 2012， 7(10).

[3]Liang C， Fu Z， Liu Y， etal. Incentivized Peer-Assisted Streaming for On-Demand Services[J].IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS， 2010， 21(9):1354-1367.

[4]Wen Z， Liu N， Yeung K L， etal. Closest Playback-Point First: A New Peer Selection Algorithm for P2P VoD Systems [C]. Global Telecommunications Conference (GLOBECOM 2011)，2011.

[5]Mushtaq M， Ahmed T. Smooth Video Delivery for SVC based Media Streaming over P2P Networks[C].2008 5th IEEE Consumer Communications and Networking Conference，2008.

[6] Ahmed T， Mushtaq， M. P2P Object-based adaptivE Multimedia Streaming[J]. Journal of Network and Systems Management， 2007， 15(3):289-310.

[7]Abdelhalim A，Ahmed T，WalidKhaled H，etal.Using Bittorrent and SVC for efficient video sharing and streaming[C]. Computers and Communications(ISCC)，2012.

[8]Xie H，Yang Y R，Krishnamurthy A，etal.P4p:provider portal for applications[C].Proceedings of the ACM SIGCOMM 2008 conference on Data communication，2008.

[9]Zhang G， Yuan C. Self-Adaptive Peer-to-Peer Streaming for Heterogeneous Networks Using Scalable Video Coding[C]. International Conference on Communication Technology Proceedings， 2010.

[10]Sheu T， Wang Y. Dynamic Layer Adjustments for SVC Segments in P2P Streaming Networks [C]. Computer Symposium (ICS)， 2010 International， 2010.

[11]李斐.基于网络编码的P2P分层流媒体传输架构研究[D].电子科技大学， 2012.

[12]Chang H，Shih Y，Ya-Yueh Shih，Yuan-Wei Lin.CloudPP:A Novel Cloud-based P2P Live Video Streaming Platform with SVC technology[C].2012 8th International Conference on Computing Technology and Information Management，2012.

[13]张勇，何娜娜，夏海轮.移动P2P流媒体中的数据调度算法[J].吉林大学学报（信息科学版），2010，28（6）.