2024年3月17日发(作者：)

龙源期刊网

基于P2P的用户生产内容视频资源查找策

略

作者：李彦 陈卓

来源：《计算机应用》2012年第04期

摘要:现有用户生产内容(UGC)类视频系统通常采用C/S架构设计，导致了视频服务器极大

的带宽压力。提出一种采用对等网(P2P)的在线短视频查找策略——FastSearch，其目的是利用

视频资源之间的关联关系进行视频资源定位，以显著提高点播节点之间的视频分享效率并降低

对视频服务器的带宽需求。实验表明FastSearch具备良好的视频数据源节点查找能力，集成了

该查找策略的短视频系统能有效减少对视频服务器的带宽消耗。

关键词:用户生产内容；对等网；资源查找；社会网络；重叠网

中图分类号: TP319 文献标志码:A

Video resource search policy of user generated content based on P2P

LI Yan1,2*, CHEN Zhuo1

1. College of Computer Science and Engineering, Chongqing University of Technology,

Chongqing 400054，China；2. Engineering Research Center of Mechanical Testing Technology and

Equipment Ministry of Education, Chongqing University of Technology,

Chongqing 400054, ChinaAbstract:

Present User Generated Content (UGC) video system mainly adopt the client/server architecture,

which can result huge bandwidth pressure at streaming server. This paper propose a Peer-to-Peer(P2P)

based online short video search policy-FastSearch. The motivation is utilize the relevancy relationship

between video resources to locate resource, which can improve the sharing efficiency between peers

and decrease the consmumption on streaming searver. Simulation shows that FastSearch has a high

efficient streaming source peers searching ability and can greatly reduce the bandwidth consumption

龙源期刊网

of streaming t User Generated Content (UGC) video system mainly adopts the

client/server architecture, which can result in huge bandwidth pressure on streaming server. This paper

proposed a (P2P) based online short video search policy—FastSearch. It aims to make

use of the relevancy relationship between video resources to locate resource, which can improve the

sharing efficiency between peers and decrease the consumption of streaming server. The simulation

results show that FastSearch has an efficient streaming source peers searching ability and can greatly

reduce the bandwidth consumption of streaming server.

Key words:

User Generated Content （UGC）; (P2P); resource search; social network; overlay

network0引言

NetTube这类用户生产内容(User Generated Content,UGC)视频类分享网站在支撑大量点播

的同时消耗了大量的网络带宽［1-2］。大多数短视频分享网站都采用客户机/服务器架构实

现，以这种方法实现短视频的点播相对简单且当用户规模不大的时候点播响应较快，但其带来

的问题是视频服务器的带宽消耗巨大，网站需要向运营商支付高额的带宽租用费。这一问题导

致目前视频分享网站虽然有很大的点击量，但盈利能力较弱。另外，当访问用户量规模较大的

时候也会使得缓存时间明显增加，用户的体验质量（Quality of Experience，QoE)严重下降。

另一方面，采用对等网(,P2P)技术的视频应用越来普遍，已有的网络视频直播

系统Coolstreaming［3］ 和点播系统PPLive［4］ 都采用P2P的方式实现。由于这类系统具备

良好的可扩展性且视频服务器的带宽占用相对C/S模式大为降低［4］所以被众多视频内容提

供商采用。但和较多的长视频不同的是，UGC类视频分享自身的特点，诸如：UGC类视频通

常视频长度短小;另外，在同一时刻观看同一个视频节目的观众通常并不是很多。这使得节点

之间共享视频流的难度增大。因此，利用P2P技术部署UGC类视频的主要问题是：如何在较

短时间内高效地查找定位到视频源节点。本文通过把用户的点播兴趣和短视频之间具有的关联

特性［5］相结合，提出一种基于P2P技术的UGC视频资源查找策略——FastSearch，重点讨

论FastSearch中节点的点播兴趣偏好度量的方法及高效的UGC视频资源的查找定位策略。

1相关研究工作

在P2P点播方面，国内外学者做了很多研究工作，如微软研究院的Huang等［6］提出在

VoD引入Peer的互助以降低视频服务器开销，在文献［4］中，作者通过对PPLive系统的关

键部件阐述及通过实际系统的实验说明P2P VoD系统的性能。对于P2P VoD的研究主要还是

集中于长视频节目的点播研究上，探讨的主要问题是如何有效支持VCR这类操作及如何实现

优化的预取策略等，这类P2P VoD系统中的视频文件本身没有社会网络特性且在同一时刻观

看同一视频节目的节点数量众多，这些特点都使得P2P VoD和在线短视频分享存在较大的技

龙源期刊网

术差异。对于在线短视频分享方面，文献［1］从实验的角度分析了YouTube这类在线短视频

分享网站的网络流量特点及用户的点播行为，但并没有考虑通过P2P的方式对视频网站的带宽

压力进行优化。文献［5］通过tracking的方式对YouTube进行研究，得出了视频文件之间存

在社会网络(Social Network)的特点，提出了一种采用视频服务器+P2P的方式实现在线视频分

享系统NetTube［5］，通过仿真实验表明引入P2P技术后可以降低服务器带宽消耗约70%。

但作者也谈到NetTube在视频数据源节点的查找方面仍需要更多的研究，特别是当用户没有从

相关视频列表选择其他视频观看时(即前后两个视频的关联度不大)，如何以较低开销查找到缓

存了该视频节目的节点仍不够理想。另外，当缓存满后应该采用怎样的缓存管理策略也需要进

一步研究。

2视频数据源节点查找策略

在UGC视频系统中引入P2P技术的主要目的是通过增加节点之间的数据互享的机会，使

点播节点优先依靠其他在线节点获取视频流，最终降低视频服务器的带宽消耗。因此高效的视

频数据源查找策略非常重要。UGC短视频系统中的查找策略需要面对如下困难。1)视频类应

用具有较强的时间紧迫性，这一特点使得查找算法效率必须较高。如果在线节点中存在部分缓

存了用户所点播的视频v的节点，则需要能够较快地找到这些缓存节点。2)视频源节点的资源

查找开销应该控制在合理范围，这也是NetTube中只采用两跳洪泛的主要原因，但如果洪泛的

节点范围较小，又难以找到较多的数据源节点，因此查找策略面临在查找开销和查找到的数据

源节点的数量上的权衡。3)为了保证用户的点播感受度QoE，在一定时间内如果仍然难以找到

数据源节点，如视频流行度较低则需要及时向视频服务器请求获得视频数据。因此查找策略需

要初步估计在一定查找范围内(TTL)，能够找到部分数据源节点的概率。 第4期

李彦等：基于P2P的用户生产内容视频资源查找策略计算机应用 第32卷2.1查找策略描

述

FastSearch的资源查找策略需要重叠网络(Overlay Network)的支持，并建立在用户点播兴

趣和视频节目的社会特性基础之上，更全面地考虑到了节点实际的点播行为。把用户点播行为

分为两类：第一类称为关联视频点播行为，即用户从与当前正在观看的视频的相关视频列表中

选择下一个观看的视频，这种情况下前后两次点播的视频存在较密切的关联关系；第二类称为

无关联视频点播行为，即用户点播的视频和当前正在观看的视频不属于同一类型的视频，这种

情况下前后点播的两个视频没有在密切的关联关系。这里假设用户的点播行为属于这两种点播

行为之一。

龙源期刊网

另外，一个节点i的邻居应分别属于三种类型，即具有强关联邻居关系的邻居、具有弱关

联邻居关系的邻居和具有社会网络关系的邻居。本文把这三类邻居构成的集合分别称为

SNS(i)、WNS(i)和SocialNS(i)。FastSearch的视频查找策略是一种具有视频关联关系意识的查

找策略，UGC视频系统中视频文件之间存在的社会网络特性使得点播视频的用户之间的点播

行为也呈现一定的关联关系，即用户往往会从那些和当前播放的视频存在一定关联关系的相关

视频中选择一个作为下一个点播的视频［5］。FastSearch的主要利用了这一特性，有偏向发送

查找请求给那些和查找视频具有点播关联关系的节点，而不是简单采用如NetTube所采用的洪

泛的方法查找。FastSearch的查找策略可以看作是一种有偏向的Random Walk查找，向邻居发

送的一个查找请求即是一个“Walker”。使用Random Walk的方法使得查找开销得到控制，而有

偏见的选择节点使得查找命中率得到显著的提升。

在节点i访问FastSearch并建立邻居关系（包括建立三种类型的邻居关系）的时候，节点

间同时需要交换自己的缓存视频信息列表(VideoList)。经过和邻居间的视频列表信息交换，节

点i则能够知道每个邻居节点当前所缓存的视频信息。另外，节点i看完当前视频并选择下一

个观看的视频假设为Vin，把Vin相关联视频Vin,1,…,Vin,j,…,Vin,k构成的关联视频集合定义

为RVListip,这里假设每个视频的关联视频个数为k，其中Vin,j表示Vin的第j个关联视频。根

据保存的邻居视频列表，节点i可以知道邻居节点中那些缓存了Vin,1,…,Vin,j,…,Vin,k中的部

分视频。假设节点i的m个邻居组成的集合为NSeti={nbi1,…,nbij,…,nbim}，邻居nbij(1≤j≤m)

缓存了Vin,1,…,Vin,j,…,Vin,k中的视频个数表示为Bnumij(0≤Bnumij≤k)而满足Bnumij≠0的节

点组成集合为RSeti,查找策略会选取RSeti中的节点并发送跳数为TTL的查询请求。另外，节

点i会同时向RSeti中的邻居节点发送视频的关联关系视图

VRMap={Vin|Vin,1,…,Vin,j,…,Vin,k}。RSeti中的节点在收到查询请求后，会把TTL减1，如

果不为零则按照如上的方式，把查询Vin的请求消息有偏向地发送给那些缓存了

Vin,1,…,Vin,j,…,Vin,k中一个或多个视频的邻居节点。请求转发查找结束的条件为TTL为零或

者邻居节点中没有任何一个缓存了的查询请求。

另外，节点i会同时向RSeti中的邻居节点发送视频的关联关系视图

VRMap={Vin|Vin,1,…,Vin,j,…,Vin,k}。RSeti中的节点在收到查询请求后，会把TTL减一，如

果不为零则按照如上的方式，把查询Vin的请求消息有偏向地发送给那些缓存了

Vin,1,…,Vin,j,…,Vin,k中一个或多个视频的邻居节点。请求转发查找结束的条件为TTL为零或

者邻居节点中没有任何一个缓存了Vin,1,…,Vin,j,…,Vin,k中的一个或多个。

图1表示了FastSearch中具备视频关联关系意识的查找策略的运行情况示例。节点i点播

了视频v2，同时存在关于v2的视频关联关系视图VRMap={v2|v3,v4,v5,v6,v7}。节点i的三个

邻居中N2缓存了和v2存在关联关系的v3和v7，而N3缓存了v2及和v2存在关联关系的

v3。节点i在req请求消息中记录v2的关联视图和TTL后，把消息发送给N2和N3，如图

龙源期刊网

1(a)。N2由于自己没有缓存v2，则把TTL减1，不为零则继续发送请求给邻居，即图1(b)所

示。N3可以直接回复节点i，表示可以向节点i提供v2的视频流，同时当TTL不为零的时候

也同时向自己的邻居N8转发该查询请求，如图1(c)所示。

FastSearch的查找策略具有视频关联关系意识，当TTL不为零的时候，始终把查找请求有

偏向地进行转发，转发的节点具备两种特点之一:1)缓存了要查找的视频；2)缓存了要查找的视

频存在关联关系的视频。而对于那些没有缓存和点播视频有任何关联关系视频的节点，

FastSearch的查找策略回避了向这类节点的转发查询请求，这里利用的思想就是UGC类视频

系统存在的社会网络性质，点播了视频v的节点具有很大概率点播与v存在关联关系的视频

［5］。查找算法的伪码如下：

该查找算法主要把查找数据源节点分成三种情况考虑:第一种情况是节点选择点播的视频v

是节点最感兴趣的视频类型T(v)=Tfav(Ni),则节点同时通过向自己基于兴趣邻居中的强关联邻

居和基于社会特性建立起来的邻居发送查找视频v的请求。第二种情况是视频v不属于节点最

感兴趣的视频类型即T(v)!=Tfav(Ni),节点需要确定自己保存了到类型为T(v)的簇的连接，也即

保存有到T(v)类型的节点的弱连接，如果有这样的弱连接则向这种类型的弱连接邻居发出查找

v的请求。节点同时向基于社会特性建立起来的邻居发送查找请求。第三种情况是经过前面的

查找算法仍然无法找到视频数据源节点则只能向Tracker服务器请求获取正在播放或者缓存了

v的节点。

2.2视频流行度的估计

FastSearch中，节点之间交换视频的关联关系视图VRMap不仅帮助节点实现基于关联关

系的视频源查询，同时节点通过对多个视频之间的关联关系的分析还能够得到视频流行度的估

计(Video Popularity Estimation)，这有助于FastSearch更有效地预取流行度高的视频，使得预取

的视频被用户点播的概率得到较大提高。

通过图2说明对视频流行度的估计，图3中节点i在一段时间t内收到其3个邻居N1、N2

和N3发送的四个视频关联关系视图，分别为

VRMapN1→i={k|b,c,w,v},VRMapN2→i={f|e,m,b,c}和

VRMapN3→i={a|b,f,e,d},VRMapN3→i={b|a,k,f,w},则节点i能够记录下各个视频的关联关系

为：a:b,f,e,d; b:k,w,m,u,a,f; c:f,k; w:k,b; d:a; e:f; m:b; v:k。可以看到，在这段时间内，节点i可以

分析出各视频b和其他视频的关联关系是最多的，也说明视频b的流行度最高。图片

图2节点建立视频流行度的估计关系2.3查找跳数TTL的确定

龙源期刊网

在查找算法里多次调用了参数不同的SearchSP(T,v)函数，其主要作用是向不同类型的邻居

节点请求查找视频v，如果邻居缓存了v则向请求的节点返回响应，如果没有缓存则继续向邻

居的邻居进行查找。这里需要重点考虑的一个问题是如何确定查找跳数TTL(hop)。在NetTube

中，简单地设置查找跳数TTL为2跳，目的是为了降低Flooding带来的开销。而在实际情况

下，节点对点播视频v的查找跳数TTL存在如下几个特点：1)TTL和视频v的“流行度”密切关

联，“流行度”越高的视频被点播节点缓存的概率也越大，因此在TTL较小的情况下能达到较

好的查找效率；2)TTL和类型为T(v)的簇的局部紧密程度相关。簇中节点的邻居数较少则局部

紧密度也就较小，因此适当增加TTL不会带来较大的网络开销。文献［5，10］通过大量实验

数据得出在线视频分享中视频的点播次数和“流行度”排名基本满足Zipf分布。假设节点单播的

视频v的流行度排名为k，而FastSearch中所有视频文件数量为M，Zipf分布是指数特性参数

为S。则根据Zipf分布的性质，节点点播流行度排名为k的视频v的概率可表示为：

f(k;s,M)=1/ks∑Mn=1(1/ns)=1ksHM,s(1)

HM,S为谐参数(Harmonic number)，HM,S=∑Mk=11ks，设S=1时，HM,1=∑Mk=11k=ln

M+γ，γ是roni系数，值为0.5772156649。通过式(3)可以看到排名越靠前(k越小)

则节点点播了该视频的概率越大。另外设在线的点播节点数为N，那么在线节点中点播并缓存

视频v的节点数Nk可粗略估计为：

Nk=N·f(k;s,M)=Nk(ln M+γ)(2)

因此节点i要查找到视频v需要访问的节点数量为:

Nv=「「

通过式(5)也可以看到如果视频v的流行度越高则需要访问较少的节点就可以找到缓存了该

视频的节点。另外，还需要考虑的是类型为T(v)的簇的紧密程度，这里采用文献［11］中的方

法，对一个属于类型为T(v)兴趣簇的节点j其局部簇系数可表示为

为节点j的邻居

集合;|Γj|为节点j的邻居的总数;|E(Γj)|表示Γj集合中实际的连接总数;C2Nbj表示Γj集合中

可能产生的连接总数，CCj越大就表示簇的紧密程度越大。再假设FastSearch中一个节点的强

邻居节点个数为x，那么在TTL跳内可以访问到的T(v)类型簇的节点个数为∑TTLt=1(x′)t，其

中x′=x·(1－CCj)。所以有：

∑TTLt=1(x′)t≥Nv(4)

其中:Γj

龙源期刊网

TTL≥logx′((x′－1)Nvx′+1)(5)

FastSearch通过式(2)～(5)粗略求出一个“流行度”排名为k的视频v的查找跳数TTL。由于

FastSearch按照节点的主要点播兴趣偏好把节点进行了分簇，并把视频文件之间的关联考虑进

去。所以实际需要的TTL值通常比式(5)求出的理论值更小就可以达到较好的查找效率。

2.4查找策略的性能分析

假设节点i点播的视频v的流行度Pv,和视频v关联的视频个数为M个，而每个节点平均

有N个邻居节点。另外，定义第l层节点到第l+1层节点的查询请求转发表示请求消息增加1

跳，如图1(a)中节点i向N2和N3发送查询请求为第1跳，而N2转发请求消息给N4,N5和

N6及N3转发消息给N8均属于第2跳。Pik,j(1≤k≤N)表示节点i的第k个邻居节点在第j跳能

够找到视频v的源节点的概率。如果节点间在没有视频关联关系信息的时候，在第j跳能够找

到视频v的概率为pv，即只与流行度相关。而在邻居节点间具备邻居缓存的视频列表，并有

关联意识的进行查询时第j跳能够找到视频v的概率不仅和pv相关，同时还和第j－1跳的节

点所缓存的关联视频个数有关。给出如下条件概率Pj, 表示在第j－1跳的节点缓存有λ个和视

频v相关联的视频的条件下(具备关联关系)，如果把查询消息转发给该节点则在第j跳成功查

找到视频v的概率：

P jnbi = P(Fnbi j > 0|B j-1i = λ) =

在式(6)中：B j－1i表示第j－1跳的某个节点i缓存的与v相关的视频个数为λ；F jnbi表

示节点i把查询消息转发给自己的邻居节点即第j跳，能够找到视频v的个数；Mv表示和视频

v相关联的视频个数；Sv表示当前在线的n个节点中缓存了视频v的节点集合；|Sv|表示缓存

了视频v的节点的数量。式(7)中pv则表示视频v的流行程度。显然，能够查找到视频v的概

率和不仅和视频v自身的流行程度相关同时还和视频关联关系的紧密程度相关，如果节点i缓

存的和视频v相关的视频个数越多，则表明i的邻居节点缓存了越多的和v相关的视频，λ越

大则表明下一条邻居节点那里越容易找到视频v。

假设FastSearch中一个节点的平均邻居节点个数为k，而节点i的邻居节点中如果有θ(θ

下面对比在k个邻居节点中任意选择θ个发送查找请求的查找效率。当不可考虑视频之间

的关联关系，也即节点i发送k个查询消息给各个邻居节点。由于不考虑关联关系，查找成功

龙源期刊网

查找概率只和视频v的流行度pv相关。因此在k个邻居处查找到θ个缓存了视频v的源节点

概率为:

Pj′=P(Fj=θ)=pθv(1－pv)n－θ(10)

而－pv)n－θ>1，也即FastSearch中通过有选择性地发送

θ个查询消息比任意选择θ个发送的查找成功率更高。3实验仿真

本文采用OverSim系统［7,12］对FastSearch仿真，在关联度较大的时候，通过Flooding

策略和FastSearch算法通常都可以得到较好的资源命中率。FastSearch的主要优势是能够在视

频关联度不大的时候可以获得可接受的视频查找效率。所以，这里重点比较前后两次视频点播

的视频节目在没有强关联性的时候的查找效率。通过图3的对比可以看到FastSearch的查找效

率显著优于NetTube这类采用Flooding策略的典型系统，在这种情况下IShare的平均查找效率

基本达到了60%，而部分情况下NetTube却基本无法直接通过P2P的方式找到源节点而必须借

助于服务器的帮助，而这显然又增加了服务器的压力。

图片

图3视频关联度较小时查找视频源节点的百分比

实验对服务器的带宽消耗也进行了比较，对比了

FastSearch、NetTube和C/S架构时视频服务器的带宽消耗。图4中可以看到C/S架构的带

宽消耗最大，在同样数量的用户点播请求下达到了接近4Gbps。FastSearch比NetTube有了更

好的改善，能够节约75%的带宽消耗，这是通过进一步增加节点间的数据共享实现的。

图片

图4视频服务器的带宽消耗对比

4结语

本文提出了一种基于P2P的在线视频资源查找策略，该策略在前后两次点播的视频资源的

关联关系较小的时候仍然可以通过较小的资源开销获得较大的资源查找效率。通过实验仿真表

龙源期刊网

明了FastSearch比现有的系统在资源查找效率上具有更优的效率。下一步，将继续通过在现实

系统中部署FastSearch策略并进一步对系统加以完善。

参考文献:［1］

GILL P, ARLITT M, LI Z, et al. YouTube traffic characterization:A view from the edge［C］//

ACM,2007:15-28.

［2］

CORBETT C. Peering of video［EB/OL］. ［2006-09-10］

/mtg.0606/pdf/.

［3］

ZHANG XINYAN, LIU JIANGCHUAN, LI BO， et al. CoolStreaming/DONet: A

overlay network for live media streaming［EB/OL］.[2011-04-

01]./～jcliu/Papers/.

［4］

YAN HUANG, FU T Z J, CHIU D.M,et al. Challenges, design and analysis of a

system［C］// SIGCOMM’08: Proceedings of the ACM SIGCOMM 2008 Conference on

Data Communication. New York: ACM,2008:375-388.

［5］

CHENG XU, LIU JIANCHUN. NetTube: Exploring social networks for short video

sharing［C］// Proceedings of the 28th IEEE Conference on Computer Communications. [S.l.]: IEEE,

2009: 1152-1160.

［6］

HUANG CHENG, LI JIN, ROSS K W. Can Internet be profitable?［C］//

and Protocols for Computer Communications. New York: ACM, 2007:133-144.

［7］

龙源期刊网

BAUMGART I, HEEP B, KRAUSE S. OverSim: A scalable and flexible overlay framework for

simulation and real network applications［EB/OL］.[2011-09-

01]./doc/p2p09_.

［8］

XU K, LI HAITAO, LIU JIANGCHUAN,et al. PPVA: A universal and transparent

accelerator for interactive online video sharing［C］

Quality of Service. [S.l.]: IEEE, 2010:1-9.

［9］

Euclidean distance［EB/OL］.［2011-03-09］. /wiki/Euclidean_distance.

［10］

CHA M, KWAK H, RODRIGUEZ P. I Tube, You Tube, Everybody Tubes: Analyzing the

world’s largest user generated content video system［C］

SIGCOMM Conference on Internet Measurement. New York: ACM, 2007:1-14.

［11］

HUI K Y K, LUI J C S, YAU D K Y. overlay P2P networks: Construction and

handling dynamic flash crowd［J］. Computer Networks, 2006,50(15):212-221.

［12］

BAUMGART I, HEEP B, KRAUSE S. A P2PSIP demonstrator powered by OverSim［C］//

P2P’07: Proceedings of the Seventh IEEE International Conference on Computing.

Washington, DC: IEEE Computer Society, 2007:243-244.