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的流行度最高。图片 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）