一种基于时移电视系统的副本放置策略*

韩国栋，朱一戈

（国家数字交换系统工程技术研究中心，河南 郑州 450002）

时移电视[1](Time-Shifted Television)作为IPTV的一种，允许用户进行暂停、快进和后退等操作，也可以选择几天前的电视节目，是一种极具吸引力的服务。不同于一般的网络电视，时移电视需要对每个用户分配一个信道，不能通过组播的方式将节目数据推送给用户。同时，由于电视信道所需带宽较高[2]，现有内容分发网 CDN(Content Distribution Networks)的体系结构难以满足业务要求，对服务提供者提出了挑战。

P2P技术有效打破了CDN中代理服务器的C/S模式。网络中的节点既是用户又是服务器，使用户能从最近的对等节点中下载相应流式数据，从而有效避免热点服务器过载,减少电视频道切换响应时延[3](Zap Response Time)。

副本放置技术常用来解决这种热点问题。通过对热门副本进行有策略的放置，减轻相关热点资源节点的负载，缩短请求消息搜索路径，提高消息搜索成功率，降低请求响应时延。P2P网络副本放置方法分为三种：服务端副本放置方法、客户端副本放置方法和路径放置方法。参考文献 [4]将纯P2P网络归纳为损失模型（loss network model），将文件按热、中、冷三种类型放置到各个节点中，从而实现各节点上行带宽使用率的最大化。参考文献[5]在结构化P2P网络的基础上，提出了一种最优副本放置算法,有效平衡了性能与开销之间的关系。参考文献[6]通过研究现有P2P网络上运行的IPTV业务的提高方法，指出了一系列缓存管理和副本放置方法。另外，参考文献[7]也对P2P上的流媒体业务进行了分析和建模。但是，现有的研究存在以下问题：首先，现有算法大都是基于P2P存储系统，以整个文件为基础进行处理，不符合流式传输的数据存储方式；其次，没有考虑到不同数据类型的差别，单纯地将数据分为热点数据和冰点数据，降低了冷门节目的服务质量。

本文针对时移电视系统中的副本放置问题，提出一种混合副本放置策略。通过分析IPTV编码方式和流式数据传输特性,考虑网络拓扑对放置策略的影响，以及负载均衡等要求,自适应地将数据片放置在节点中,就近为用户提供服务,从而有效提高用户体验度和系统性能。

1 问题分析

1.1 系统模型

本文分析的时移电视系统的结构中，源服务器RS(Resource Server)通过组播的方式将内容推送到各地的代理服务器VHO(Video Hub Office)。本地各设备(如机顶盒、计算机和手机等）间通过无结构P2P网络连接，分享节目数据。VHO中存储着所有当前电视节目内容数据，并通过分层编码技术（Layered Encoding）和多描述编码技术 MDC(Multi-description Coding)，将不同质量的视频内容传送到不同用户的设备中。

本文主要关注时移电视节目数据在系统中的放置问题。由于所有电视数据都已存储在VHO中，因此本文的数据放置问题可进一步简化成流式数据在P2P网络中的管理问题。

1.2 副本放置问题分析

P2P网络中的副本放置问题是一个NP完全问题（NP-Complete）[8]。为了协调全局负载均衡和请求的响应时延最小化两种优化目标，本文考察节点的能力（带宽大小和存储容量）以及节点之间的距离，提出近似最优解决方案。

(1)负载均衡问题

设网络中所有节点的集合由V表示,共计n个节点，其中节点 i记作 Vi。

定义1：节点Vi的负载Li，表示节点响应用户请求，分享数据所带来的带宽使用代价等。设节点Vi中存储着数据片集合 Xi，每个数据片的访问次数为 fx，则负载Li可表示为：

这样，负载均衡度可以表示为：

目前，大多数P2P系统中的查询消息都是通过流言机制查询来实现的。因此，通过复制技术，有计划地将副本放置在路由节点，能够在提高消息搜索成功率的基础上控制整个系统的流量，提高网络利用效率。

(2)最小化响应时延问题

影响用户请求响应时延的因素包括消息搜索成功率以及节点之间的互协作性。好的副本放置方案能够使用户快速而成功地搜索到所需的数据，同时能够就近获取以实现最小化响应时延。

定义 2：节点 Vi与节点 Vj的距离di,j。节点 Vj中有数据片，而节点 Vi上没有相应数据，则di,j表示节点 Vi需要从节点Vj获取相应数据的跳数。则节点Vi需获取为存储数据的距离di为：

在查询消息路由算法一定的情况下,节点Vi接收查询消息的能力和两方面有关系：(1)节点在网络中所处的位置。节点连接度越大其查询消息接受的概率就越大[9]，转发的通讯量就更多。这样，节点获得的信息就更加全面，能提高消息搜索成功率。(2)路由器周围用户节点的活跃程度，即区域用户在线率。因为，一旦询问周围用户节点拥有所需数据，则该请求消息搜索成功。此时，节点Vi收到查询消息的概率就较小。

2 混合副本放置方法

由于IPTV数据与一般的文件数据不同,流式数据在系统中有一定的存活时间，同时数据量较大。因此，其副本放置方法和普通P2P文件分享系统的副本放置方法有一定差别。

2.1 IPTV数据特性

一般说来，一个通过数据压缩过的视频包含以下三类帧：I帧、P帧和B帧。其中，I帧包含视频起始信息，用户收到这种帧不要更多的信息就可以直接解码出相关视频信息。这类帧的好处在于能够更快地完成电视频道转换（zapping）任务，因而有必要多复制此类帧来减少时延。然而，I帧的大小远远大于其他两类帧，因而也需要更大的存储空间和带宽来实现传输通信。典型的视频数据结构如图1所示。可以看到,电视节目的传送数据帧中，B帧所需开销最小，其传输的频率最高。

通过上述分析可以发现，对各个频道及其节目的数据帧进行合理的复制，进而放置到靠近用户的位置，是平衡用户请求的消息搜索成功率和副本放置开销之间关系的一种有效途径。

2.2 混合副本放置策略

在查询消息路由算法一定的条件下，节点Vi收到的查询消息数量由其覆盖的节点数决定，即该节点通过泛洪，在TTL的限制下，转发该节点查询消息的节点数量。设网络中平均连接度为K。当K=1时，节点Vi接收的查询消息转发次数为：

其中，di为节点Vi的连接度。当某一消息成功搜索到副本的位置，则响应该消息。另外，当连接度增大时，某一节点可能收到两次节点Vi洪泛的查询消息。这样，该节点收到的第二次查询消息会被丢弃。以此类推，网络中节点数一定，平均连接度越高，其查询消息的能力就越弱。此时，当K=k时，节点Vi所能收到的节点数为：

由此可见，节点Vi的连接度越大，其接受查询消息的能力就越强。若将热度较高的节目数据放置在该节点上，则消息搜索成功率较高，从而实现较低的请求响应时延和较小的节目初始化时延。

以此为依据，并结合负载均衡、节点距离以及IPTV编码的特点，本文提出一种针对时移IPTV系统的混合副本放置策略，将数据片分为两类，并做不同的处理：

(1)实时数据片的放置。为了实现更小的初始化时延及频道切换响应时延，需要适当增加I帧的副本数。同时，为了不使冷门节目初始化时延过长，节目之间I帧的比例差值不应过大。另外，对于B帧和P帧，可根据节目点播的热点区域进行区域性放置。具体流程如图2所示，当系统加入一个实时数据片时，首先判断该数据片是否为I帧。若是I帧，则根据人工输入的放置概率沿传输路径放置，路由节点的连接度越大放置的概率越高。当被放置节点的缓存空间已满时，利用LRU为该副本腾出相应空间。反之，若该数据片为B帧或P帧，则计算该帧在本节点被访问的并发数，若超出阈值OT，则发送一个副本放置到发送距离需要该内容最多的热点区域最近的路由器节点上。若此节点缓存空间已满，则采用LRU为该副本腾出相应空间。

图2 实时数据片放置示意图

(2)过期数据片的放置。鉴于实时数据片已经占用了很大一部分缓存空间，过期数据片所能提供的缓存空间相对减小，因此选择其放置策略更要慎重。首先要解决选择哪一个数据片副本需要进行放置，以及缓存空间已满时应该采取怎样的缓存管理策略。用户节点有两个选择查找到需要的过期数据片，以实现快进、快退等操作。①通过洪泛的方式进行搜索；②直接到代理服务器中查找相应数据片。第一种方法虽然能够分担代理服务器的负载，减少请求时延，但是加重了网络负担，且存在消息搜索成功率低的问题。因此，对于过期数据片，可通过代理服务器进行查找。若该内容在节点服务器中的并发数超过OL，且用户节点搜索失败，则将目标数据片放置在沿路连接度最大的路由节点中。若此节点缓存空间已满，则采用LRU为该副本腾出相应空间。

(3)缓存数据管理。在时移IPTV系统中，每一个数据在一定时间后可用度就大大减少，需要对这些数据进行定期处理，以提高缓存利用率。

设置数据片生存时间，使各类数据片的生存时间各有不同，其中实时数据片的生存时间应该大于过期数据片的生存时间,以满足用户短时间暂停或快退的需要。

3 仿真及结果分析

3.1 仿真环境

仿真采用Power law拓扑作为模拟拓扑。拓扑包括1 000个节点，其中包括一个代理服务器，100个路由器节点,其余为用户节点。每个路由节点缓存空间为36 GB，用户节点通过洪泛的方式获取所需节目的相关数据。网络中节点平均连接度为4,设置150套电视节目，同一节点不存在同一数据片对象。用户节点以相同的概率发起查询消息获取随机的节目。

3.2 数据分析

图3显示了在IPTV系统中节点通过使用洪泛的查询消息路由算法进行搜索，各放置策略对数据片的搜索命中率的影响的比较。图中横坐标为单个路由节点缓存空间与整个数据库内容大小的比值。TTL的值为2。数据表明，在同一网络条件下，采用混合副本放置策略的消息搜索成功率较高。当缓存空间增加时，随机放置策略下的消息搜索成功率也有增加，但是由于其副本放置的随机性，使得性能的提高不是很稳定。

图4显示了各策略的路由节点缓存空间占用情况的比较。可以看到，随机副本放置策略作为一种贪婪策略，总是随机地选择数据内容将缓存空间填满。这样的好处在于，搜索成功率随着缓存空间的增大而提高。然而，随机地选择数据内容不适合IPTV系统这样数据更新较快的环境，且这种主动而又周期性地盲目数据更新更加重了网络开销。

时移电视具有数据量大，数据更新频率高等特点。本文针对时移电视系统中的副本放置问题，从IPTV数据流格式特点出发，提出了一种混合副本放置策略。通过分析传输时延以及消息搜索成功率与副本放置的关系，根据节点连接度放置数据片，达到提高热点数据片搜索成功率的效果。同时，分析IPTV数据帧特点，合理分配放置概率，以减小节目初始化时延以及频道切换时延。最后给出了混合副本放置策略。仿真表明，该策略能够在较少的缓存空间下有效提高消息搜索成功率，降低请求时延，提高系统性能。

[1]Liu Yaning,SIMON G S.Distributed delivery system for time-shifted streaming systems[C].2010 IEEE 35th Conference on Local Computer Networks,Denver,CO,USA,2010:276-279.

[2]POPESCU A,KOUVATSOS D D,REMONDO D,et al.Content distribution over IP:developments and challenges[J].Network Performance Engineering,2011,5233:979-987.

[3]BEJERANO Y,KOPPOL P V.Improving zap response Time for IPTV[C].INFOCOM 2009,IEEE,Rio de Janeiro,2009:1971-1979.

[4]TAN B,MASSOULIE L,Optimal content placement for peer-to-peer video-on-demand systems[C].IEEE INFOCOM 2011,shanghai,2011:694-702.

[5]Rao Weixiong,Chen Lei,Fu Waichee,et al.Optimal resource placement in structured peer-to-peer networks[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(7):1011-1026.

[6]BIERACKI A.Methods of QoS improvement for P2P IPTV based on traffic modelling[C].2010 International Conference on Complex,Intelligent and Software Intensive Systems,2010:445-450.

[7]Gao Peng,Liu Tao,Chen Yanming,et al.The measurement and modeling of a P2P streaming video service[J].Networks for Grid Applications,2009,2:24-34.

[8]Li Zhe,SIMON G.Time-Shifted TV in content centric networks:the case for cooperative in-network caching[C].ICC2011:IEEE International Conference on Communications,Kyoto,Japan,2011:1-6.

[9]冯国富,张金城,顾庆,等.一种基于覆盖网络拓扑的无结构P2P主动复制策略[J].软件学报,2007,18(9):2226-2234.