P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法

摘要

本发明公开了P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法，该方法实现了P2P流媒体系统中高效的缓存替换。首先，当播放的过的视频块从当前普通节点的播放区移除到普通区时，如果普通区已满，则依次计算视频的反馈数值、视频点播需求的可用值、修正因子，并基于反馈机制，计算淘汰指数；如果当前视频的淘汰指数最大则删除该视频块，否则计算最大淘汰指数视频中每一个视频块的缓存价值，删除价值最小的视频块。实施结果表明，本发明所设计的方法可以有效地降低热门视频的冗余副本，并将它们替换为冷门视频的副本，增加了冷门视频在P2P点播系统的副本数量，从而有效降低了服务器压力，提高了节点的缓存利用率。

说明书

技术领域

本发明涉及一种P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法，属于多媒体通信技术领域。

背景技术

随着宽带带宽的升级和互联网的飞速发展、软硬件的不断升级、流媒体的技术快速发展，流媒体服务凭借其良好的娱乐性和社交性受到越来越多的网民欢迎。流媒体技术的进步与发展使得网民在观看视频前，只需要经过短暂的等待之后，即可以一边下载一边观看欣赏所点播的视频节目，从而无须再等到整个视频节目全部下载完毕。显然，流媒体技术给人们欣赏视频节目带来了更好的观看体验。由于对等网络(Peer to Peer，简称P2P)流媒体点播系统具有较好的可扩展性，学术界和工业界的研究人员以及工程师对其进行了深入的研究和研发。目前，基于P2P的流媒体点播系统已经在技术上实现了一定的突破，在国内外取得了丰硕的成果。在P2P网络中，每个节点是对等的，每一个节点可作为客户端(Client)向服务器或者向其他的节点获取视频资源，同时也可作为服务端(Server)给其他对等的节点提供自身节点含有的视频资源。在网络中，每个节点贡献出自己的上行带宽和内存中存储的视频资源，从而使得网络中节点对服务器视频流的需求大大降低，减轻了服务器的负担。

在P2P流媒体点播系统中，流媒体资源都是被分为若干固定大小的分块在对等节点之间相互传输的。每个视频资源的数据块被分享的热度都是有差异的，需要针对数据块缓存提出的分段缓存替换方法，现有主流方法可以分为三种：(1)基于访问时间的缓存替换方法。该方法的主要思想是根据缓存数据的访问时间来选择缓存内容。其中，最近最少使用方法(Least Recently Used，简称LRU)是最典型的一种；(2)基于概率的缓存替换方法。缓存数据的访问频率是该类方法确定缓存的准则。最少使用缓存替换方法(LeastFrequently Used，简称LFU)是该类方法的典型代表；(3)基于访问时间和访问频率的缓存替换方法。其中，最近最小频率的缓存方法(Least Recently Frequently Used，简称LRFU)是最具有代表性的一种。由于以上三种方法只是单独考虑单个节点的缓存替换，缺乏对整个系统的网络状态和其它节点的缓存信息的考虑，因此，现有的P2P流媒体系统在节点缓存管理方法上还存在着一些局限性，值得进一步的研究和改进。

发明内容

本发明目的在于提出一种P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法，解决节点缓存局限性问题。

本发明实现上述目的的技术解决方案是：P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法，其特征在于，所述节点缓存替换方法包括：

步骤1：当刚播放过的视频块S_mp从当前普通节点的播放区移除到普通区时，判断普通区满载状态；如果普通区未满，则视频块S_mp存入普通区，否则执行步骤2，其中所述视频块S_mp指视频m的第p块；

步骤2：从服务器获取视频块S_mp所属视频m在当前时刻t的淘汰指数EI_m(t)，同时获取普通节点普通区中已缓存的每个视频i在当前时刻t的淘汰指数EI_i(t)，选出其中淘汰指数最大的视频，并表示为视频n，i为任意整数；

步骤3：比对淘汰指数，若视屏m的淘汰指数大于视频n的淘汰指数，则从普通节点的缓存中删除视频块S_mp，否则执行步骤4；

步骤4：从服务器获取视频n中每一视频块j的缓存价值data_value_nj，并从中选出缓存价值最小的视频块S_nq，之后将视频块S_nq删除，并将视频块S_mp存入普通区对应的空间实施替换，其中所述视频块S_nq指视频n中的第q块，j为任意整数。

进一步地，步骤2中获取视频i在当前时刻t的淘汰指数的步骤包括：

计算视频的反馈数值,视频i在t时刻的反馈数值用feedback_i(t)表示，计算公式为：

其中，0<λ₁<1，λ₂>1，γ>0，δ表示相邻两个周期服务压力之差，由计算公式得到，其中，表示视频i在t时刻对服务器产生的压力；表示视频i对服务器的平均压力，使用距离当前时刻t的临近Q个周期T来计算视频i对服务器的平均压力；由计算公式得到；

计算视频点播需求的可用值，(Availability to Demand，简称ATD)是P2P系统中用于检测整体缓存状态的关键性指标，通过ATD_i(t)表示在t时刻视频i的缓存整体状态，对于视频i设其被分为k个视频块，由计算公式得到，式中，N_ij(t)表示视频i中第j块在P2P流媒体点播系统中的副本总数，n_i(t)表示当前观看视频i的普通节点总数；

计算修正因子，在t时刻对于视频i的修正因子用CF_i(t)表示，由计算公式得到，其中，n_i(t)表示P2P流媒体点播系统中在t时刻观看视频i的人数，β>1，n_ave(t)表示同系统中观看热门视频的平均人数，由计算公式得到，其中，N_popular表示系统中热门视频的总数，p_popular表示冷热门视频的阈值，p_i为由服务器事先标记好的视频流行度，当满足p_i>p_popular时判定为热门视频；

基于反馈机制计算淘汰指数，视频i在t时刻的淘汰指数用EI_i(t)表示，由计算公式EI_i(t)＝σATD_i(t)×CF_i(t)×feedback_i(t)+(1-σ)EI_i(t-T)得到，其中σ表示反馈灵敏度因子，0<σ<1。

进一步地，步骤4从服务器获取视频n中每一视频块j在t时刻的缓存价值data_value_nj(t)的计算公式为：

其中，request_times_nj(t)表示在t时刻，视频n的第j个视频块被点播的次数，cache_number_nj(t)表示在t时刻，视频n的第j个数据块的副本总数，，这两个量的值都可以从PSN中直接获得；ρ为大小介于0～1的比重因子，主要是用它来防止数据块缓存价值的抖动。data_value_nj(t)表示视频n的第j个数据块在t时刻的缓存价值，data_value_nj(t)值越大，表示视频n的第j个数据块对系统贡献越大，缓存价值越高。

应用本发明创新提出的节点缓冲替换方法，较之于传统三种主流方法，具有突出的实质性特点和显著的进步性：能够有效地降低热门视频的冗余副本，并将它们替换为冷门视频的副本，增加了冷门视频在P2P点播系统的副本数量；并且有效降低服务器压力，提高节点缓存的利用率；在计算淘汰指数时引入反馈机制，使得淘汰指数的更新更加平滑。

附图说明

图1为本发明涉及的基于淘汰指数的节点缓存替换方法的流程图。

图2为全部视频对服务器的压力与周期关系图。

图3为热门视频对服务器的压力与周期的关系图。

图4为冷门视频对服务器的压力与周期的关系图。

图5为服务器压力与节点缓存大小的关系图。

具体实施方式

下面结合说明书附图对本发明创造作进一步的详细说明。

如图1所示，本发明提供了P2P流媒体点播系统中基于淘汰指数的节点缓存替换方法，该方法包括如下步骤：

步骤1：当播放的过的视频块S_mp(视频m的第p块)从当前普通节点(PCN)的播放区移除到普通区时，判断普通区是否已经满；如果普通区未满，则S_mp存入普通区，不做其他操作；否则，执行步骤2；

步骤2：从服务器(PSN)获取视频块S_mp所属视频m在当前时刻t的淘汰指数EI_m(t)，同时获取PCN节点普通区中已缓存的每个视频i在当前时刻t的淘汰指数EI_i(t)，选出其中淘汰指数最大的视频(用视频n表示)，i为任意整数；具体实施过程如下：

(2-1)计算视频的反馈数值；

视频i在t时刻的反馈数值用feedback_i(t)表示，其计算公式如下：

其中，0<λ₁<1，λ₂>1，γ>0，δ表示相邻两个周期服务压力之差，该值由如下公式计算：

其中，表示视频i在t时刻对服务器产生的压力。表示视频i对服务器的平均压力，这里使用距离当前时刻t的临近Q个周期T，来计算视频i对服务器的平均压力。的计算公式如下：

由feedback_i(t)公式知：

①当δ>0且γ大于δ的绝对值时，表明当前周期的视频i对服务压力，与临近Q个周期视频i对服务器的平均压力相比，增幅比较大。此时需要降低EI_i的值，避免持续减少视频i的副本数量，因而此时调整的系数λ₁(0<λ₁<1)。

②当δ<0且γ大于δ的绝对值时，表明当前周期的视频i对服务器压力，与临近Q个周期视频i对服务器的平均压力相比，下降了一定幅度，这意味着，对视频i的在系统节点中的数量调整的力度比较合适，过度的调整并没有发生，此时需要保持调整幅度，故对应该时刻的调整系数为λ₂(λ₂>1)。

③γ小于δ绝对值时，表明当前周期视频i对服务器压力，与临近Q个周期视频i对服务器的平均压力相比，波动比较小，可以保持原来的调整不变，故此时的调整系数为1。

(2-2)计算视频点播需求的可用值；

视频点播需求的可用值(Availability to Demand，简称ATD)是P2P系统中用于检测整体缓存状态的关键性指标；对于视频i，系统通过ATD_i(t)表示系统中在t时刻视频i的缓存整体状态，其计算公式如下：

在这里首先明确，在P2P流媒体点播系统(以下简称系统或P2P系统)中，视频被等大小的分为若干数据块。对于视频i，设其被分为k个数据块。在上式中，N_ij(t)表示视频i中第j块在系统中的副本总数，n_i(t)表示系统当前观看视频i的节点总数。

ATD一定程度反映了系统中缓存的状态，在P2P系统中，通过一定的方法让系统中的视频的ATD保持一致。但是对于那些观看较少的视频，或者某时刻没有人观看的视频，对于ATD有两种处理方式：①让ATD为零，从而使系统中没有节点缓存该视频；②使得ATD为非零值，让系统保存少量该视频的副本。文献^[51]指出，系统中观看较少的视频，ATD的值较大。对于观看比较少的冷门视频，特别是某一时刻没有人观看的视频，本发明采用第二种处理方式，让其ATD为非零值。

(2-3)计算修正因子；

用CF_i(t)表示在t时刻对于视频i的修正因子，该修正因子主要拥有以下性质：

①对于冷门视频，尤其是对于系统中当前没有观看的视频，计算该视频ATD_i时分母几乎等于零，当系统节点中即使有少量该视频的副本，ATD_i的数值将大概率的是一个非常大的数值，因此，对应时刻靠近数值零的值是CF_i一个合理的设计，这样以来EI_i数值不会是一个大的数值，不会被误认为是非常热门的视频，进而降低冷门视频被删除的概率。

②对于热门视频，在系统中缓存副本比较高，计算该视频ATD_i时分子几乎将会很大所以该视频ATD_i大概率的是一个大的数值，此时ATD_i与EI_i设计目的相切合，因此对应时刻CF_i的值应该和视频i的热门程度是成正相关的。

CF_i(t)的计算公式如下：

其中，n_i(t)表示P2P流媒体点播系统中，在t时刻观看视频i的人数，β>1，n_ave(t)表示系统中观看热门视频的平均人数。上式中的n_ave(t)计算公式如下：

其中，N_popular表示系统中热门视频的总数，p_popular表示冷热门视频的阈值，当视频的流行度p_i(由PSN事先标记好)满足p_i>p_popular时，该视频为热门视频；

(2-4)基于反馈机制计算淘汰指数；

用EI_i(t)表示视频i在t时刻的淘汰指数，该指数越大，表示视频i在节点缓存替换时，越容易被替换删除，其计算公式如下：

EI_i(t)＝σATD_i(t)×CF_i(t)×feedback_i(t)+(1-σ)EI_i(t-T)，

其中σ表示反馈灵敏度因子，0<σ<1。

步骤3：比对淘汰指数，若视屏m的淘汰指数大于视频n的淘汰指数，则从普通节点的缓存中删除视频块S_mp，否则执行步骤4；

步骤4：如果视频m的淘汰指数小于普通区中具有最大淘汰指数的视频n，即EI_m(t)≤EI_n(t)，则从PSN中获取视频n中的每一块视频数据块j的缓存价值data_value_nj，并从中选出价值最小的视频块S_nq(如，视频n中的第q块价值最小)，之后将S_nq删除，将S_mp存入普通区。否则，将S_mp从当前PCN节点的缓存中删除。

在本步骤中，计算PSN中获取视频n中的每一块视频数据块j的缓存价值的公式如下：

其中，request_times_nj(t)表示在t时刻，系统中视频n的第j个数据块被点播的次数，cache_number_nj(t)表示在t时刻，系统中视频n的第j个数据块的副本总数，这两个量的值都可以从PSN中直接获得，ρ为比重因子，主要是用它来防止数据块缓存价值的抖动，它的大小介于0～1之间，data_value_nj(t)表示视频n的第j个数据块在t的缓存价值，data_value_nj(t)值越大，表示视频n的第j个数据块对系统贡献越大，缓存价值越高。

本发明的性能评价如下：

为了验证本发明方法的性能，本发明实验使用java编程，以周期(时间)为驱动的方式进行仿真实验。在仿真实验中，所模拟的网络中有一个PTS，一个PSN还有众多节点(PCN)。其中，PTS负责定期更新记录网络中所有节点的信息，同时它也负责为请求节点进行视频资源定位。PSN拥有网络中所有完整的视频，当网络中的请求节点在其它的节点中找不到视频资源时，则请求节点会向PSN获取视频内容。

仿真参数数值仿真参数数值仿真的周期800β3初始节点数目25σ0.5节点上行带宽2Mbpsλ₁0.4视频码率1Mbpsλ₂1.4视频总数400Q10视频长度160块ρ0.5

实验参数如表1所示，网络初始化时有25个节点，之后以每个周期增加25个节点的速度进入网络，直至增加到7000。在仿真中，视频总数400个，视频的流行度服从Zipf分布(与第四章仿真实验使用相同的分布)，视频号越小，其流行度越高，即视频号为0的是这系统中400个视频流行度最高的。每个视频被均分为160个数据块，视频的码率为1Mbps。每个节点的上行带宽2Mbps。这里将本发明的方法和另两种缓存替换方法——最近最少使用缓存替换方法、比例缓存替换方法进行性能对比。

现有文献研究发现，用户观看视频并不是全部从开头开始，有少部分用户喜欢从视频的后面开始观看，所以实验中选定百分之八十的用户从视频的起始点开始观看视频，其它用户随机选择播放时间点，每次播放视频30块左右。令β＝3，即，CF_i(t)在0-3之间变化。通过“二八法则”可知，本系统中有20％的视频被80％的节点观看。此外，我们将0-79号视频定位为热门视频，80-399号视频为冷门视频。

这里进行了两组实验，每组实验都进行了10次，然后把10次结果进行了平均。第一组实验，节点的缓存大小设置为180块，其余的参数不变。第二组实验，节点的缓存大小在50到250块之间变化，其它参数不变。

在第一组实验，分别给出实施三种方法后，冷门视频对服务器的压力与周期的关系(图2)、热门视频对服务器的压力与周期的关系(图3)以及全部视频对服务器的压力与周期的关系(图4)结果。

这里的服务器压力，是指单位时间服务器上传的数据量，如下式所示：

其中，N_r表示服务器(PSN)处理请求的次数，T_block表示每个请求数据块对应的时长(单位秒)，V_R表示系统视频的比特率。

(1)服务器压力的性能比较

图2记录了从第0个周期到第799周期服务器压力的变化。网络的初始化节点个数为25，每个周期增加25个节点，在第280个周期时，网络规模达到设定的7000个节点。从图2可知，在第110周期左右时，三种方法对应的全部视频产生的服务器压力都已经达到了590Mbps左右的最大值，之后在第110至340周期，服务器压力发生了大幅度下滑。产生这种现象主要原因是因为使用了P2P点播的技术。随着时间的向前推进，P2P点播系统中节点数目增加，系统中拥有的视频越来越充足，这样以来，节点之间相互服务的可能性得到大大的提升，从而大幅度减少了去服务器请求视频的次数，最终服务器压力也得到了大幅度降低。在第320个周期以后，图2可以看到，服务器压力比较结果为：基于淘汰指数的缓存替换方法<比例缓存替换方法<最近最少使用方法，这说明本发明提出的基于淘汰指数的缓存替换方法，在降低服务器压力这个指标上，要优于另外两种方法。

虽然从图2中可以看出，本发明提出的基于淘汰指数的缓存替换方法性能优于其它两个方法，但是并没有体现出通过什么样的方法来减轻了服务器压力。因此，在实验过程中，分别统计了冷门视频和热门视频对服务器的压力。

图3给出了热门视频对服务器的压力与周期的关系图。可以看出，三种方法的曲线基本一致，尤其是在第350周期之后，热门视频对服务器压力保持在12Mbps左右。由此可见，最近最少使用方法和比例缓存替换方法中，热门视频对服务器的压力是有限的，而本发明提出的基于淘汰指数的缓存替换方法在经过定义的淘汰指数EI的调整，将系统中热门视频的多余的副本替换删除，使得冷门视频的在系统中视频副本增加后，热门视频并没有增加对服务的压力，这正是基于淘汰指数的缓存替换方法的设计初衷，增加冷门视频在系统节点中的副本占比的同时，热门视频产生的服务器压力基本保持不变。

图4记录了冷门视频对服务器压力的变化。从图中可知，比例缓存替换方法和最近最少使用方法在系统中使用时，服务器的压力主要来自冷门视频产生的压力。然而本发明提出的基于淘汰指数的缓存替换方法在经过不断地调整节点中缓存的分配后，冷门视频产生的服务器压力得到了大幅的下降，这也是服务器压力下降的主要原因。

(2)服务器的压力与节点缓存大小

图5是第二组仿真实验观察统计的结果。该仿真实验，主要是统计第799周期之前的60个周期的服务器压力，然后对这段时间的服务器压力进行平均。

从图5中看出，当节点的缓存大小相同时，本发明所提出的基于淘汰指数的缓存替换要优于其它两个方法。追其根源，本发明提出的基于淘汰指数的缓存替换能够充分利用节点有限的缓存资源，将热门视频的冗余副本转换为冷门视频的副本，从而提高了系统整体的缓存命中率，使得服务器的压力得到降低，提高节点缓存的利用率；在计算淘汰指数时引入反馈机制，使得淘汰指数的更新更加平滑。

上面结合附图对本发明的实施方式作了详细说明，但是本发明并不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。