作者：李丹
互联网的飞速发展和普及使得网络服务由主要提供文本和图像的Web多媒体内容逐渐转变为提供音视频等含有更多丰富信息的多媒体内容，同时流媒体技术也随之流行起来并应用于各式各样的多媒体服务中，如视频点播、直播、视频会议、远程教学、网络视频等。但是流媒体对象的数据量比文本内容要大很多，需要大量的存储空间以及更高要求的网络带宽，由此产生的流媒体传输时延会严重影响用户体验质量。为了减少用户访问的响应时间，研究者提出采用代理缓存技术，将用户需要的内容放置在离用户最近的地方。
由于流媒体对象数据量巨大，采用全文缓存的方法很难取得理想的缓存效果，而前缀缓存策略虽然可以节省缓存空间，也可以有效缩短用户访问的启动时延，但随着用户访问时进行交互式操作的增多，前缀缓存策略的效果将会变差。为了提高缓存策略的适应性，研究者提出了均匀分段和指数分段等分段策略，其基本思想是将流媒体内容沿着播放时间分成若干个片段，并以此作为存储和置换的基本单元，缓存粒度的减小给缓存算法带来了更大的灵活性，并且也在一定程度上提高了缓存效率。
基于分段的缓存策略虽然提高了缓存性能，但是精细的分段粒度也增加了系统需要管理的片段数量和缓存置换次数。传统的均匀分段和指数分段方法仅按照简单的函数关系来对流媒体进行分段，没有充分地考虑到流媒体自身的一些特性，例如外部流行度和内部流行度等，因此其分段效果在很多情况下并不理想。参考文献[9]的研究表明，如果能针对流媒体的一些特性对其分段策略进行优化设计，能有效地提高分段的性能。本文在现有分段缓存研究的基础上，根据命中率和存储的流媒体片段流行度之间的关系，提出了一种基于最佳分段点估计的流媒体非均匀分段方法，该方法首先统计出进行全文缓存时的缓存临界外部流行度以及每个流媒体对象的内部流行度，并对该临界外部流行度与最佳分段点流行度之商随存储占比的变化曲线进行拟合，然后对最佳分段点进行估计，并将流媒体对象以最佳分段点为分割点分成两个片段。仿真结果表明，与其他分段策略相比，本文提出的策略在相同命中率的前提下可以显著减少总分段数量，并且在总分段数相同的前提下可以获得更好的命中率。
2 流媒体流行度特点
缓存空间是有限的，如何利用有限的空间使缓存的流媒体片段价值最大是分段算法的中心思想，而流行度是衡量流媒体价值的重要指标。流行度被广泛用于描述流媒体的流行程度，常常使用流媒体文件被访问的次数作为流行度的定义。根据流行度所描述范围的不同，进一步细分为外部流行度和内部流行度。外部流行度是指流媒体对象之间的流行程度，描述的是流媒体文件的整体流行度大小，而内部流行度是流媒体对象不同播放时间片段上的流行程度。流媒体对象之间的外部流行度会有明显的差异，每个流媒体的内部流行度也会因用户的个人喜好产生不均匀的分布。本文以2013年1-5月的中国电信股份有限公司广东分公司(以下简称广东电信)IPTV系统的点播访问日志为依据，分别对以上两种流行度的特点进行了分析，并研究了各个存储占比情况下的最佳分段点。
2.1 流媒体流行度分布
流媒体的外部流行度常使用Zipf分布或广延指数分布进行刻画，用户的访问具有很强的倾向性，少数的热门影片往往占有大量的用户请求，也就意味着大多数的低流行度影片是不会被缓存的，对于这部分影片一视同仁地细分段显然会大大增加无谓的分段管理成本。
研究者还发现，近一半的用户请求不会播放完整个影片，而是在影片结尾之前就提前终止请求，因此同一流媒体内部不同区段之间也存在着流行度的差异，用户常常会通过观看影片的初始部分，以确定是否有兴趣继续观看，于是造成影片的内部流行度会随着播放时间而逐渐递减。以每分钟一个区段计算影片的内部流行度．400部影片内部流行度与播放时间的关系如图1所示，影片起始部分的流行度会有一个快速下降的过程，这是用户的浏览行为造成的，而后流行度以较平稳的趋势逐渐减小。由图1可以看出，内部流行度是非均匀的，也就意味着外部流行度高的流媒体对象也很可能会有内部流行度非常低的部分，而且每个影片的内部流行度的变化也有所差别，传统的分段算法，例如均匀分段，往往不依据或者只单纯依据外部流行度的高低对影片进行分段而忽略了每个影片的内部流行度变化，具有一定的局限性，不能充分利用流媒体对象的流行度信息。
2.2存储占比与最佳分段点
不同流媒体对象之间的外部流行度和流媒体对象的内部流行度都存在着访问频度的差异，由于存储空间有限，每段流媒体通常可以分为存储部分和非存储部分。假设可以对流媒体进行无限精细度的分段，本文进一步分析了在不同存储占比下，命中率最高时视频是否被存储的分界点流行度下限，如图2所示。由图2可知，最佳分段点上的流行度下限随着存储占比的加大而逐渐变小，这是由于存储占比越大，缓存空间也越大，可以缓存更多的影片内容，从而使得临界点处的影片分段流行度变得越小。
根据以上对流媒体流行度的分析，发现由于用户请求有着比较强的倾向性，影片之间以及影片内部的流行度分布常常是不均匀的，内部流行度有着随播放时间增加逐渐降低的特点，而流行度又是影响命中率的直接因素，如果能够直接根据分段点下限值将影片分成两段，那么就能从根本上提高命中率，并且减少分段数量。
3基于最佳分段点估计的流媒体分段策略
由于高流行度的视频往往占整个视频总数的少部分，且视频之间的流行度具有较大差异，视频内部的流行度也具有分布不均的特点，因此尽量缓存流行度高的片段是提高命中率和缓存利用率的有效方法。从理论上分析了缓存的流媒体片段流行度与命中率之间的关系以及将影片分成两段的分段点下限值的估计方法，并在此基础上提出了一种基于流媒体对象内部分段点估计的新分段策略。
3.1 缓存的片段流行度对命中率的影响
字节命中率(byte hit ratio，BHR)是指缓存中命中的数据量与用户请求的总数据量的比值，表示如下：
其中，CBR代表缓存命中的数据量，UTD代表请求的总数据量。
设流媒体对象内部流行度的计算基本粒度为Rb byte，即统计流媒体对象分割为Rb byte片段时的每个片段的流行度。设
为所有视频的基本粒度片段的集合，其中，Ⅳ为缓存视频总数，纯为第i个视频的第i个片段，ri为第i个视频的片段总数。当存储空间有限时，只能存储部分视频片段，设中7为缓存中的视频片段集合，则：
假设视频的内部流行度P(cpq)在短暂的时间里是不变的，那么
也是不变的，则
越大，BHR就越大，即缓存中的视频片段流行度越大，字节命中率越大。
3.2最佳分段点的估计模型
本文按视频的流行度大小排序进行缓存，设所有视频片段的集合为
，其中Ⅳ为视频总数，尬为第i个视频的片段数，c为第i个视频的第J个片段。缓存空间为C时，被缓存的视频片段集合依然设为西’，那么不被缓存的片段集合则为
。
若不对视频进行分段，即全文缓存的情况下，所有视频集合则为
，则缓存临界点处的视频外部流行度Pe满足：
其中，
为视频
的长度。
对视频进行分段，并逐渐减小分段长度f，当2减小到1个单位数据量长度时，缓存临界点处的视频片段流行度就是最佳的分段点内部流行度下限值P：
由以上分析可知，临界点处视频片段流行度随着分段长度f的减小逐渐向Po靠近，本文以广东电信IPTV系统2013年12月的实际用户点播访问日志对只和P之间的关系进行建模分析。图3为存储占比变化时，视频进行全文缓存时的临界外部流行度与最佳分段点处的内部流行度的比值k的变化情况。由图3可知，k的值随着存储占比的增加呈现着逐渐增加的趋势，并且七与存储占比的关系可以使用多项式分布模型进行拟合。设存储占比表述为c，则：
其中，a，a2，…，a+，为n阶多项式模型参数，可获得最佳拟合曲线。
式(8)所表述的模型对不同存储占比下3阶和5阶多项式的拟合情况如图4所示，3阶多项式的拟合决定系数R2=0.963 76,5阶多项式的拟合决定系数R2=0.998 57，两者的决定系数都接近1，说明两种多项式的结合效果都比较好，从图4中也可以看出，该模型可以比较好地刻画k与存储占比之间的关系，并且多项式的阶数越高拟合效果越好，也就是说只要获得视频完整缓存情况下的临界流行度就可以估计出最佳的分断点处内部流行度阈值，而完整缓存的视频不需要进行分段，计算复杂度较小，只要获得所有视频的外部流行度信息就可以很容易得到。
3.3分段策略
利用第3.2节中分析的估计内部分段流行度阈值方法，将每个视频分成高流行度段和低流行度段两个片段，可以大大减少视频总的分段数目，同时也可以保证比较好的命中率。
本文提出的分段策略分为5个步骤，具体过程如下。
(1)数据统计
设定一个合理的流行度统计周期T，并统计待估计周期T’的前一个周期T和前两个周期T内的所有视频的内部和外部流行度。
(2)建立内部流行度阈值估计模型
·根据式(5)和式(6)，计算得到周期T的完整缓存情况下的临界流行度Pc2和周期T的最佳的视频内部分段流行度Po,。
·根据式(7)，对不同存储占比下的完整缓存的临界流行度与最佳分段流行度曲线之商k=Pc2/Po,进行拟合，得到参数a，a2，…，a的值。
(3)内部流行度阈值估计
·根据式(5)计算得到周期T在完整缓存情况下的临界流行度Pc,。
·根据式(8)：
_，计算得到不同存储占比下周期T’的估计分段流行度Po。
(4)分段
根据估计的分段流行度Po，对周期T’内的所有视频分成两个片段：内部流行度高于Po的内容部分为一个片段，低于P的部分为另一个片段。
(5)重新分段
由于视频的流行度会随着时间的推移而不断变化，每个周期对已有旧视频进行检测，如果视频现有的分段点阈值与最佳分段点阈值相差达到一定程度则对该视频进行重新分段。
本文的分段策略依据流行度对命中率的重要性，并对最佳的内部分段点进行估计，充分利用了视频的外部和内部流行度信息，一方面直接针对命中率进行了提高，另一方面也大大减少了总的分段数量。
4实验结果
本文的实验数据采用广东电信IPTV系统2013年12月流行度前400的电影类视频真实点播访问日志，共有8 000条记录。采用字节命中率和总分段数对分段策略进行性能评估，其中总分段数对系统管理的复杂度有直接影响，而字节命中率可以有效地比较各个分段策略所消耗的网络流量。仿真实验采用2013年12月1-15日的数据对2013年12月下半月的视频最佳分段点进行估计，并对比了采用3阶多项式估计最佳分段点时，本文的分段策略与均匀分段策略相同总分段数下的命中率大小以及相同命中率下的总分段数大小。
4.1 相同总分段数情况下的字节命中率比较
图5为相同总分段数情况下，不同分段策略的字节命中率比较结果。本文的分段策略命中率基本上达到了最佳分段点分段时的命中率，并与均匀分段策略相比明显呈现出更好的命中率，这是由于最佳分段点估计分段策略充分利用了实际内部和外部流行度特征，并对分段点处内部流行度进行了良好的估计，不仅提高了字节命中率．还可以减少用户访问时延并节省了网络流量以及缓存空间资源。
4.2相同命中率情况下的总分段数比较
表2为相同命中率情况下，不同分段策略的总分段数大小比较结果。在各个存储占比大小下，本文的分段策略的总分段数都远远低于均匀分段策略，这是由于本文的分段策略根据最佳分段点估计值对视频进行分段，每个视频最多分为2段，在保证命中率的同时也可以获得分段数的减少，从而节省了系统的分段管理成本。
5 结束语
本文对流媒体的内部和外部流行度进行了分析，并基于流行度对命中率的重要性，提出了基于最佳分段点估计的流媒体非均匀分段策略。通过对流行度建模分析，利用流媒体的外部流行度对最佳分段点的内部流行度进行估计，将视频最多分成两段，达到了减少总分段数目的目的，同时由于增强了流媒体对象对流行度的适应性，也获得了较好的命中率。实验结果表明，对比于传统的均匀分段策略，本文分段策略可以在相同总分段数的情况下提高字节命中率，节约缓存资源以及网络带宽，也可以在相同命中率情况下大大减少总分段数，降低系统分段管理成本。本文所提方法的局限性在于估计最佳分段点时假设内部和外部流行度在一定时间内保持不变，然而实际中无论外部还是内部流行度都是动态变化的，因此在估计最佳分段点时考虑流行度变化的特点将有望能进一步提高本文方法的性能。
6摘要：
针对命中率随存储的流媒体片段流行度变化的特征，提出了一种新的基于最佳分段点估计的流媒体非均匀分段方法，根据不同存储大小下的流媒体外部分界流行度对其内部最佳分段点进行估计，进而把每个视频分成高流行度段和低流行度段两个片段。实验结果表明，与均分分段相比，该方法能减少流媒体的片段数，提高缓存命中率。
