2015, Vol. 26
2. 北京邮电大学 计算机学院, 北京 100876
2. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
在过去的十几年中,P2P网络得到了快速的发展,并成为Internet的重要组成部分.实现资源的有效搜索,使用户能够有效地共享网络资源,是P2P网络的重点研究内容.P2P网络按照拓扑和共享内容的组织方式分为结构化P2P网络和非结构化P2P网络.结构化P2P网络[1-4]中,每个对象对应一个关键字,通常采用分布式哈希表DHT(distributed Hash table)的方式,实现每个关键字和节点的一一对应.结构化的P2P网络能够以较低的搜索开销实现对资源的有效搜索.但结构化P2P网络不支持多关键字的语义搜索,同时,对比于非结构化P2P网络,当网络中节点频繁地加入和退出时,将会产生大量的维护开销[5],从而限制了结构化P2P网络的应用.相反地,非结构P2P网络以自适应的网络组织方式、支持多关键字语义搜索、对网络的动态变化有鲁棒性等特点[6]被广泛地应用和研究.如Gnutella[7],KaZaA[8]和Skype[9].
在非结构P2P网络中,主要采用泛洪的技术对所需要的资源进行简单的拉网式搜索.这种方式搜索覆盖广、搜索的成功率高、搜索的延迟低.但搜索过程中产生了大量的冗余消息,吞噬了大量的网络带宽资源.如在被广泛应用的Gnutella[6]网络中,采用基于TTL(time to live)的flooding算法对资源进行有效的搜索,对网络的动态变化有较好的适应性.但研究[10]显示,这种类型的网络所产生的网络流量占网络总流量的50%以上.并且在Gnutella网络中,当TTL=7时,flooding算法中产生的消息中有70%的消息是冗余消息[11].为降低非结构P2P网络中大量的带宽消耗,很多改进的方法被提出[12-15],如expanding ring[12]、双向随机漫步搜索机制[15]等.这些方法有效地降低了非结构P2P网络所产生的网络消耗,缩短了搜索延迟时间,提高了对资源的搜索成功率,特别是对于热点资源的搜索更为有效.但是这些方法对于网络中存在的稀有资源的搜索是低效的.正如相关的研究[16]显示:尽管在被广泛应用的Gnutella网络中,符合搜索要求的稀有资源在网络中存在,但是仍然有18%的搜索得不到任何响应,不能有效获得存在于网络中的查询所需要的资源.
与Gnutella结构相似的网络中,对稀有资源的搜索也存在搜索的低效性,并花费了大量的网络开销,搜索时间被延迟,不能为用户提供及时、有效的网络服务[17].因此,有效地提高稀有资源的搜索性能、更好地满足用户对资源共享的需求,是非结构P2P网络完善搜索性能的一个主要方面.
本文对稀有资源的搜索所涉及的相关问题进行了研究,目的是以最小的带宽消耗和存储消耗、较低的网络覆盖,实现对稀有资源搜索成功率的提高.同已有的对稀有资源的研究方法[18]不同,本文的主要思想是:在搜索的过程中构建局部搜索环境,采用主动搜索机制对稀有资源进行主动的搜索和识别,获取稀有资源的局部需求信息;依据用户对稀有资源的需求信息对稀有资源进行按需求复制,有针对性地提高稀有资源在网络中的流行度,并对其进行有效复制,从而提高稀有资源的流行度和查询点击率.
本文第1节介绍相关工作.第2节介绍稀有资源主动搜索与复制机制,并给出相关概念.第3节给出稀有资源的搜索与更新策略,并对所采用的数据结构进行描述.第4节通过大量的仿真实验验证稀有资源主动复制与搜索机制的性能,并与其他方法进行性能对比分析.第5节对全文进行总结,并对未来的工作进行展望.
1 相关工作在非结构P2P网络中,对资源的有效搜索是一个重点的研究问题.很多有效的搜索机制被提出 [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25],最典型的搜索方式是泛洪[6]和随机漫步 [12, 13, 14, 15].泛洪算法是将查询发送给所有的邻居节点,由于泛洪算法产生了大量重复的消息和重复的查询,消耗了大量的网络负载.一些改进的方法被提出,如expanding ring[12].尽管expanding ring方法产生了较少的消息,但是它也产生了额外的带宽消耗,特别是对稀有资源的搜索,产生的额外消耗更多.对比泛洪算法,随机漫步搜索算法[13, 14]在每一跳的消息传递过程中,将查询消息只传递给随机选择的邻居节点或在社区内的节点.标准的随机漫步策略是每次仅随机选择一个邻居节点传递消息.对比expanding ring等搜索方式,标准的随机漫步极大地降低了消息的产生,但是这种策略延长了搜索的时间.为了降低这种搜索延迟,文献[19]通过提高漫步者(walker)的数目,给出K漫步随机搜索机制.每个查询节点随机选择K个邻居传递一个消息,而后,每个邻居节点按照自己的随机漫步方式进行搜索.模拟实验显示:如果K漫步随机搜索方式在第S步获得资源,那么标准漫步将在第KS步获得资源.文献[20]从控制冗余消息的产生出发,提出了一种受限搜索机制RFSA,有效地控制了网络开销.尽管这些方法有效地控制了冗余消息的产生,降低了P2P搜索的网络开销,但由于其对目标对象搜索存在的盲目性,仍然产生了大量的无用搜索,消耗了网络的带宽资源.
为降低搜索的盲目性,进一步减少网络开销,提高对资源的搜索性能,很多的启发式搜索算法被研究[21-25]. APS[21]算法是一种流行的K随机漫步的概率化的搜索机制,也是一种自适应、带宽有效和易于实现的非结构P2P搜索算法.该方法使用先前搜索信息的反馈来概率地引导未来的搜索.在APS方法中,每个节点维护一个索引表,用于记录每个邻居对于每个被请求的资源的先前搜索成功率.算法依据该成功率,概率地选择那些先前对被请求资源搜索成功率高的邻居节点传递消息,使得搜索向着最可能到达目标节点的方向进行.相关的成功率将依据节点对该查询是否成功地返回而被动态地更新.PQR[22]算法是一种新的查询路由机制,用于改进非结构P2P网络的查询性能.在PQR中,设计了一种新的数据结构叫轨迹增益向量(traceable gain matrix,简称TGM),用于记录在成功路径上的每个节点对查询的增益值.通过TGM,能够优化查询路径的有效选择,从而提高查询点击率并产生较低的带宽消耗.文献[23]依据拓扑感知和基于兴趣的链接构建智能覆盖P2P网络,基于Gossip交换方法对一个社区内节点的文件索引表进行交换,提出一种混合自适应搜索机制.该机制在每个本地社区拥有足够多的节点时,利用资源的流行度,能够提高搜索的性能,但其忽略了对稀有资源的考虑.在SPUN[24]中,对于一个被查询的对象和一个给定的邻居节点,每个节点使用RSRs(relative success ratios)记录沿着路径的相关成功率的向量值信息,包含了更多的启发式决策信息,为资源的搜索提供更有效的指导.PQBCF算法[25]依据P2P网络搜索过程中节点的参与度和重要度,给出节点的中间中心度的描述,选择具有较大中间中心度的节点来实现资源的高效搜索.这些方法均利用先前的成功搜索信息获得对未来相同资源或重复查询的有效引导,因此这些方法对热点资源的搜索或重复资源的搜索非常有效,但是对于稀有资源的搜索是低效的.而对比于盲目搜索机制,这些启发式的搜索算法将查询更有效地引导到目标节点,降低了无用搜索的产生,减少了网络带宽的消耗,这说明历史的相关搜索信息对资源的搜索是有效的.本文中,基于启发式的搜索机制,将从先前的搜索中获得的信息引入到稀有资源的识别和复制策略上,从而实现在搜索过程中动态地以较低的带宽消耗和存储消耗对稀有资源进行按需求有效的复制,从而提高稀有资源的查询成功率.
通过复制技术提高资源的副本占有率,是有效改进资源查询成功率的另一重要方法 [26, 27, 28, 29, 30].目前存在的复制技术主要是在查询获得成功后,通过在查询需求点或沿成功查询路径的资源复制方式提高资源在网络中的流行度,从而提高对资源搜索的成功率.这些复制技术多采用被动的复制策略,并在查询获得成功的前提下才能实施复制,因此对于那些容易搜索到的资源有更好的复制率,从而使越流行的资源越被更多地复制.而对于很难搜索到的稀有资源的复制是低效的.文献[26]提出了一种低开销的主动文件复制策略,基于节点的存储能力,将文件复制到物理相近的节点上.这种方法以较低的维护消耗提高了文件复制的性能.在iDARE[27]中,将文件的数据块复制到网络中比较稳定的服务节点上,这种策略对网络结构的动态变化有更好的适应性.文献[28]提出了一种平方根的目标对象复制策略,将目标对象复制到搜索所经过的节点数目平方根个节点上,这种策略能够改进对流行资源的搜索性能.文献[29]从查询性能和P2P网络中节点资源配置行为之间存在的相互关系和P2P节点之间资源配置行为的交互作用出发,采用博弈的方法对资源副本进行网络配置,获得较低的冗余度,但未提及对稀有资源的分配.为解决P2P应用所带来的网络流量压力,文献[30]基于P2P网络中的骨干节点或骨干链路,依据缓存部署过程中P2P流量分布和缓存存储状态的动态变化对P2P网络中资源进行部署,获得较好的效果,但对骨干节点或骨干链路的识别需要额外的开销.以上复制策略更多的是基于资源被成功搜索后进行复制,对流行资源有效;但对于稀有资源,由于其在网络中存在较少的副本,因而搜索的成功率较低,从而使其获得了更少的复制机会.因此对稀有资源,很难通过这些复制方式提高其副本数量.
在主要针对稀有资源搜索的研究中,研究者通常使用先前的复制策略对稀有资源进行复制.如在文献[31]
中,当节点连接到P2P网络时,它主动将自己所拥有文件的参考安置在被随机选择的$O(\gamma \sqrt n )$个邻居节点中.这
种策略能够改进稀有资源的搜索性能,但是其产生了很大的通信开销;并且在动态变化的P2P网络中,要获得整个网络的信息是很困难的.文献[32]给出了一种自适应的全文本复制策略,将流行度相对较低的节点进行复制,力求获得较高的搜索性能,复制策略将对象复制到被称之为网络路由的节点上.这种复制策略提高了搜索点击率,降低了搜索延迟.但是在这种方法中依据心跳(heartbeat)的方式对副本进行维护,而忽略了对对象需求的考虑,从而造成网络中较少被访问的或基本不被访问的稀有资源也会被更多的复制,产生了更多的复制消耗和存储消耗.对比于全文本复制策略,基于索引的复制策略更能节省资源的复制开销.文献[33]针对稀有资源搜索,给出了一种基于两跳索引复制的受限超级节点随机漫步技术SCRW(supernode-constrained random walk),并提出了3种两跳索引复制策略:全复制、平方根复制和常量复制.在SCRW中,节点总是将查询随机地传递给一个超级节点.尽管这种策略提高了稀有资源的搜索性能,但是该方法在P2P网络获得超级节点的过程中将产生大量的网络开销.文献[18]给出了一种稀有资源的主动复制技术PR,由于很难获得一个资源的整体流行度,采用随机漫步的方式对节点上的资源进行自搜索,通过探测函数值proactiveProbe(i,R)确定资源的稀有性.采用节点对自身所拥有资源的需求阈值,确定是否对资源进行搜索并复制.这种方式能够有效地降低对稀有资源进行探测和复制所产生的额外的网络开销.PR通过采用提高稀有资源副本率的方式有效地提高了稀有资源搜索的成功率,但是在PR策略中,节点依据自身资源的需求特性对资源进行周期性的探测,其实质仍为该资源被点击的前提;如果该资源在一段时间内未被点击,就无法获得其需求.因此,PR策略的本质仍是基于成功查询的.文献[34]提出了一种基于局部需求特征的副本优化选择算法,利用了局部需求信息以及局部需求信息和整体需求信息的比较完成副本的放置,获得良好的搜索性能.由于在非结构P2P网络中很难获得整体的信息,因此本文在文献[34]研究的基础上,在非结构P2P网络中构建了局部搜索环境,基于稀有资源很难被访问到的特点,依据每个节点的局部需求信息与点击情况对未被点击过的资源进行周期性的探测,以确定其是否为稀有资源.在确定其为稀有资源的前提下,依据局部需求信息对资源进行按需求有效的复制.
2 稀有资源主动搜索与复制机制资源的搜索是非结构P2P网络的重点研究问题,已有的方法 [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]对热点资源的搜索获得了较好的性能,但对稀有资源的搜索其性能需要提高.通过对稀有资源的有效复制,能够在有限的搜索延迟限制内提高对稀有资源的搜索效率.本节主要通过对对象流行度、对象需求度的讨论,给出在搜索过程中所产生的局部搜索需求度、局部对象流行度等相关概念,并构建局部搜索环境,明确稀有资源定义,给出基于局部需求的稀有资源主动搜索复制策略.
2.1 相关概念设P={p1,p2,…,pi,…}是网络中节点的集合,1≤i≤n,n是网络中节点的总数目,即,n=|P|.O={o1,o2,…,ok,…}为网络中所有不同资源(文件或对象)的集合,1≤k≤m,m是不同资源的个数.设对象ok在网络中拥有rk个副本,R为网络中资源的总数,则$R = \sum\nolimits_{k = 1}^{k = m} {{r_k}} $为网络中对对象ok的查询的数目,Q为所有查询的数目,则$Q = \sum\nolimits_{k = 1}^{k = m} {{q_k}} .$
定义1(对象流行度(副本的覆盖率)). 时间$\Delta $t内,对象ok在网络中拥有rk个副本,假设同一对象在同一节点上不重复复制,那么网络中有rk个节点拥有该对象.则对象ok的流行度pok表示为
| $p{o_k} = \frac{{{r_k}}}{n},p{o_k} \in [0,1]$ | (1) |
定义2(对象需求度). 时间$\Delta $t内,网络中对象ok的查询数目为qk,则对象ok需求率qok可表示为
| $q{o_k} = \frac{{{q_k}}}{Q},q{o_k} \in [0,1]$ | (2) |
在网络的搜索过程中,总希望能够依据用户对对象的需求,在网络中适当的位置布置相应的副本数量,从而提高搜索的成功率和用户的满意率.但由于P2P网络的动态特性,获取网络的全局信息是非常困难的.因此,很难依据定义1和定义2对对象的流行度、需求度进行判定.文献[18]采用随机探测的方式对资源进行稀有性的周期性探测,仅通过拥有该资源节点本身所获得的稀有资源的需求进行节点的复制决定.这种由探测节点本身依据其本身所拥有稀有资源的需求进行判定的方式其本质仍然是基于该资源被点击的前提,而节点所拥有的稀有资源在多数情况下是很少能被点击的.因此,这种依据探测节点本身所拥有的稀有资源的需求信息来决定对该资源的探测与判定,会漏掉多数的稀有资源.另一方面,单个节点的需求并不能反映网络对该稀有资源的真实需求.在已有的启发式搜索方法的研究[20-24]中,通过先前搜索信息的记录获取了对未来搜索的有效引导信息,提高了搜索的性能.这些研究为我们提供了有利的启发:一方面,获取网络的整体信息是困难的;另一方面,通过稀有资源拥节点的信息代替整体的需求是片面.因此采用与搜索相关的局部信息获得对稀有资源的需求信息,克服了单点片面的缺点;同时,与搜索相关的局部信息更具有时效性,更适合于不断变化的P2P网络环境.下面给出相关的场景设置和相关的局部信息度量.
设sqk为节点ps发起任意一对对象ok的搜索,并在节点pt处结束查询(被点击或失败).Ps={ps,…,pi,…,pt}为搜索sqk所经历的节点的集合,Ps是P的一个子集,即,Ps$ \subset $P.基于搜索sqk,Ps和Ps中每个节点上所记录的信息构成本文对对象ok搜索的局部信息环境L.Os={os,…,oi,…,ot}为Ps中每个节点上所存储的不同对象的集合,Os$ \subseteq $O.sri为对象oi在L中的副本个数,Rs为在L中的所有资源的副本的个数,则有$Rs = \sum\limits_{{o_i} \in Os} {s{r_i}} $.sqi为在局部环境L中对对象oi的查询的数目,Qs为所有查询的个数,则有$Qs = \sum\limits_{{o_i} \in Os} {s{q_i}} $.依据定义1和定义2,得到局部环境L下,对象的局部流行度、局部需求度等相关概念.
定义3(对象的局部副本流行度(局部副本覆盖度)). 时间$\Delta $t内,设同一对象在同一节点上不重复复制,对象oi在L中的局部流行度为
| $lp{o_i} = \frac{{s{r_i}}}{{|Ps|}},lp{o_i} \in [0,1]$ | (3) |
定义4(对象的局部需求度). 时间$\Delta $t内,在L中,对象oi的查询数目为sqi,则对象oi在L中的需求率lqoi表示为
| $lq{o_i} = \frac{{s{q_i}}}{{Qs}},lq{o_i} \in [0,1]$ | (4) |
定义5(对象的节点点击度). 时间$\Delta $t内,在节点p处,设对象oi的请求查询点击数目为pqi,节点p处的所有对象查询点击数目为pq,则对象oi的节点点击度ppoi可表示为
| $pp{o_i} = \frac{{p{q_i}}}{{pq}},pp{o_i} \in [0,1]$ | (5) |
定义6(对象的节点需求度). 时间$\Delta $t内,在节点p处,设对象oi的请求查询失败数目为dqi,节点p处的所有失败查询对象的查询数目为dq,则对象oi的节点需求pdoi可表示为
| $pd{o_i} = \frac{{d{q_i}}}{{dq}},pd{o_i} \in [0,1]$ | (6) |
对于稀有资源,目前没有一个统一的定义.已有的研究中,多数将稀有资源与流行资源相对应,即,认为网络中副本较多的资源为流行资源,对应的网络中副本较少的资源为稀有资源(those with few replicas)[33].文献[18]将探测过程中探测失败的资源定义为稀有资源,忽略了稀有资源的价值性.由于很难获得整个网络的所有副本资源分布情况,本文在所构建的局部环境的基础上,依据搜索所进行的不同阶段和所获得的不同信息,将稀有资源细分为潜在的稀有资源、稀有资源和有价值的稀有资源,其定义如下.
定义7(潜在稀有资源、稀有资源、有价值的稀有资源). 时间$\Delta $t内,在节点p处,如果对象(资源)oi的节点点击度为0,即ppoi=0,则定义该资源oi为潜在的稀有资源;节点p发起对该资源的主动搜索,设搜索长度为TTL,如果在TTL内,对该资源的搜索失败,则定义该资源oi为稀有资源;如果在搜索过程中,有对该资源oi的需求,则称该资源为有价值的稀有资源.
2.2 稀有资源主动探测机制由于P2P网络的动态特性,很难获得P2P网络整体信息.在第2.1节中,构建了基于一条搜索所构成的局部网络环境,在该环境的基础上,给出了对象的局部需求度和对象的节点点击度等相关概念.同时,更多的启发式的搜索方式被研究并获得了广泛的应用[20, 21, 22, 23, 24] .这些方法实现了在局部搜索范围内对资源的有效搜索,体现了搜索的局部性和局部信息的有效性.因此在本文中,用局部的信息对稀有资源进行探测和复制是可行的.
已有的对稀有资源的复制策略要么是基于对稀有资源的成功搜索后所采用的被动复制策略[27, 28],要么是对所有对象复制相同数目的副本到网络中[31, 32, 33].前者利于流行资源的复制,后者带来了不必要的网络开销.为了解决这些问题,本文给出了一种有效的解决策略:每个节点从自身所提供的资源出发,对自身提供的共享资源进行主动的搜索,以确定节点自身所拥有的资源是否为稀有资源.若判定为稀有资源,则进行稀有资源的复制.这个过程按照时间间隔$\Delta $t周期性的进行.
在这个策略中,需要解决4个问题.
(1) 每个节点上资源数目不等,且可能包含流行资源和稀有资源.如果对节点上每个资源都发出主动的搜索探测,则探测开销巨大.因此,需要对节点上资源进行区分,实现仅对少量可能的稀有资源进行主动的探测搜索;
(2) 在搜索过程中,怎样判定所搜索的资源是稀有资源;
(3) 在复制过程中如何降低复制的盲目性,减少复制开销与存储开销.例如,某些节点所拥有的个人照片等信息对其他人是没有价值的,因此对这类信息是不需要进行复制的;
(4) 在确定所搜索的资源为稀有资源后,怎样确定所复制的稀有资源的数目和位置.
针对第1个问题,依据定义7,采用每个对象的节点点击度进行判断.如果节点上对象oi的节点点击度ppoi为0,则说明对象oi未被点击过,判定其为潜在的稀有资源,对其进行探测;如果节点上对象oi的节点点击度ppoi大于0,则说明对象oi在节点上被点击过,视为非潜在的稀有资源,对其不进行探测.通过这种方式,可以减少节点上需要进行主动探测的资源数目,并把探测限定在较少的潜在稀有资源的范围内.
针对第2个问题,依据定义7,采用主动资源搜索的结果进行判定.由资源的拥有节点对资源发起主动的搜索,并设定其搜索长度为TTL.如果对资源的主动搜索在规定的TTL内失败,则判定该资源为稀有资源;如果在对该资源的主动搜索在TTL内成功,则判定该资源为非稀有资源.因为我们很难获得网络资源的整体信息,因此可以将这样的一次探测搜索视为如第2.1节所介绍的局部搜索环境L.如前所述,在这样的局部环境下,根据其搜索的成功与失败来判定资源是否为稀有资源是有效的.
第3个问题主要解决复制的盲目性问题,即,并非所有的稀有资源都是网络中有价值的资源.因此,对于那些无价值的稀有资源无需复制.网络中,资源的价值主要体现在对资源的需求程度上,因此针对这个问题,采用公式(4)所定义的对象的局部需求度来标定资源的价值.即:如果对象的局部需求度为0,则说明在这个局部范围内,该资源为不被需求的稀有资源,因此不需要被复制;如果对象的局部需求度不为0,则说明在这个局部范围内,该资源为被需求的稀有资源,则对其进行复制.
在以上3个问题被解决的基础上,最后需要解决资源被复制的数目和复制位置的问题.很显然,被复制的资源的数目越多,稀有资源流行度提高的越快,其搜索的成功率就越高,但伴随着复制的通信开销和存储开销就越大.因此,可依据不同的网络实际情况采用不同的复制策略.本文给出了3种不同的复制策略,并对这3种不同的复制策略进行了性能的分析与对比,其详细内容分别在第2.3节和第4.2节给出.
2.3 基于局部需求的稀有资源主动复制机制在本文中,通过主动的探测机制,在一次探测搜索的局部环境下对稀有资源进行了判定,并获取了其局部的需求信息.基于该需求信息,对稀有资源进行主动复制.称这种机制为基于需求的主动复制机制(demand proactive replication,简称DPR).在DPR的基础上,基于需求信息将DPR复制策略细分为3种不同的复制机制:基于需求的全路径复制机制(demand proactive replication-full path,简称DPR-FP)、基于需求的全需求复制机制(demand proactive replication-full demand,简称DPR-FD)和基于需求的最大需求复制机制(demand proactive replication-maximum demand,简称DPR-MD).
●DPR-FP:在对资源向前主动搜索失败的情况下,判定沿途路径上是否有对该资源的需求.如果有对该资源的需求,则判定该资源为有需求的稀有资源,则将该资源沿搜索路径进行全路径的复制,即,将该资源复制到搜索路径中的每个节点上.称这种机制为基于需求的全路径复制机制;
●DPR-FD:在判定搜索中的资源为有需求的稀有资源之后,在搜索路径上选择对该资源有需求的节点进行资源的复制;
●DPR-MD:在判定搜索中的资源为有需求的稀有资源之后,选择搜索路径上对该资源需求最大的节点作为对该资源进行主动复制的唯一复制节点.
这3种不同的复制策略依据局部需求信息,逐步缩小复制的范围,并将资源复制到更接近于需求的位置.这一点与PR[18]机制有本质的不同:在PR中,并未考虑在搜索失败的局部环境下对资源的需求情况,即,无论在搜索的局部环境下是否有对该资源的需求,都决定对该资源进行复制;同时,在PR中也未充分考虑资源的复制位置,仅将稀有资源复制到探测搜索的终端节点.因此,PR复制机制具有极高的盲目性;而基于需求的DPR复制策略则对资源的复制更有针对性.
3 稀有资源搜索与更新策略在基于需求的主动复制机制DPR中,每个节点处需要设置相应的数据结构用于记录每个节点处所拥有资源的点击情况和在每个节点处对资源的需求信息.结合这种数据结构,我们给出了一种基于成功点击的稀有资源搜索机制(hit search algorithm,简称HSA),并在这种搜索策略下验证了基于需求的主动复制机制的性能.下面分别给出所采用的数据结构、搜索机制和索引的更新过程.
3.1 数据结构1) 消息格式
每个在网络中传递的消息由一个消息9元组构成:Message=$\langle $MType,ID,QNode,FNode,ONode,Item,Path,TTL, Extension$\rangle $.其中,ID为消息Message的唯一标识;QNode为发起该消息查询的初始节点;FNode为传递该消息的节点;QNode为拥有查询资源的节点;Item为被查询的资源信息;Path为该查询消息所经历的路径信息;Extension为消息的扩展部分;MType为消息的类型,包括Query和Probe两种类型.如果消息Message.MType是Query,那么该消息为查询消息,消息Message.Extension为空;如果消息Message.MType是Probe,那么该消息为探测消息,消息Message.Extension的值为探测过程中所搜集的探测资源的需求信息;如果采用最大需求复制策略DPR- MD,则Message.Extension中的内容为探测路径中对资源具有最大需求节点的信息;如果采用其他两种复制策略,则Message.Extension中的内容为探测过程中搜集的对探测资源的需求信息.
2) 节点记录
为实现基于需求的主动复制与搜索机制,在每个节点上需要维护3种辅助的数据结构,分别为:节点对象列表(peer object list,简称POL)、成功查询记录列表(success search list,简称SSL)和查询需求记录列表(search demand list,简称SDL).POL用于记录节点本身所拥有的资源的节点点击度信息,SSL用于记录通过该节点获得成功点击的查询对象和对应的邻居节点,SDL用于记录在该节点处获取的未被查询成功的对象和对该对象对应的查询需求信息.其结构与信息分别见表 1~表 3.其中,表 1中the degree of hit(ppoi)和表 3中的Demand information(pdoi)分别由公式(5)和公式(6)获得.
|
Table 1 Peer object list POL 表 1 节点对象列表POL |
|
|
Table 2 Success search list SSL 表 2 成功查询记录列表SSL |
|
|
Table 3 Search demond list SDL 表 3 查询需求记录列表SDL |
在查询与复制过程中,分别对SSL和SDL进行动态的初始化与更新,并在稀有资源的主动探测搜索过程中,从SDL中获取对查询对象的需求信息.在执行过程中,所采用的这3种辅助数据结构均采用队列作为存储结构,并采用FIFO的方式对查询消息的相关信息进行排列和更新,其存储容量可依据节点本身的存储与处理能力进行设置.下面分别给出基于成功点击的稀有资源搜索机制(hit search algorithm,简称HSA)和基于需求的稀有资源主动复制机制中的索引更新过程.
3.2 搜索机制HAS当一个节点接收到一个查询请求时,执行如下步骤:
步骤1: 检测被请求的资源对象是否在POL中:如果在,则成功点击,返回成功消息,并修改POL中查询对象所对应的点击度信息;如果不在,则执行步骤2;
步骤2: 在SSL中检测是否包含该查询对象:如果包含,则说明该节点之前存在对该对象的成功查询,其成功向下查询的邻居节点记录在对应对象的邻居节点列表中,在邻居节点列表中任选一邻居节点向下查询,直到搜索失败或成功点击;如果不包含,则执行步骤3;
步骤3: 在SDL中检测是否包含该查询对象:如果包含,则说明在该查询之前接收过对该对象的查询但
查询失败,SDL中内容(Demand information)反映了在该节点处对该对象的查询需求信息,则增加该对象所对应的需求信息;如果不包含,则在SDL中增加该查询对象,初始化其需求信息,并执行步骤4;
步骤4: 在TTL范围内,随机选择该节点的任意邻居节点向下传递该消息,继续搜索,直到搜索失败或成功返回.
3.3 索引更新过程在节点上的索引信息,将在查询消息被成功返回和稀有资源执行复制策略的过程被更新.
当一条查询消息成功返回,节点接收到该成功返回消息的时候,分别对SDL和SSL表进行更新.
更新过程如下:
步骤1: 检测该查询对象是否包含在SDL中:如果包含,则从SDL中删除与该对象相关的信息,执行步骤2;
步骤2: 检测该查询对象是否包含在SSL中:
如果包含,则说明该查询消息被成功返回过,检测其对应的邻居列表是否包含该邻居节点:如果不包含,则将该邻居节点加入到对应的邻居列表,执行步骤4;如果包含则直接执行步骤4;
如果该查询对象不包含在SSL中,则执行步骤3;
步骤3: 在SSL中加入该查询对象,并将对应的邻居节点加入到对应的邻居信息表中,执行步骤4;
步骤4: 沿搜索路径继续向下传递该成功点击消息,直到发起该查询的初始节点.
当一条稀有资源探测消息搜索失败,并获取了对该稀有资源非零的查询需求后,执行对该稀有资源的复制,在复制过程中,对节点上相关的索引结构进行更新,其更新过程因采用不同的复制策略而有所不同:
(1) 在DPR-FP复制策略下,更新搜索路径上所有节点的POL,将该稀有资源加入到POL中,并视为一次点击成功.将SDL中该对象资源的相关信息清除;
(2) 在DPR-FD复制策略下,在复制资源的节点处,对POL和SDL的更新同情形(1);在非复制资源的节点处,将SDL中该对象资源的相关信息清除,并在SSL中加入该对象资源和对其进行传递的邻居节点信息;
(3) 在DPR-MD复制策略下,在最大需求节点处,更新过程同情形(1);对于复制路径上非最大需求的节点,首先将SDL中该对象资源的相关信息清除,然后以最大需求节点为间隔点,对其上游节点在SSL中加入该对象资源和对其进行传递的邻居节点信息,对其下游节点在SSL中加入该对象资源和发送该消息的邻居节点信息.
4 仿真实验及对比分析 4.1 实验环境设置为更好地验证本文提出的主动副本复制机制的有效性,使用PeerSim[35]作为仿真平台,布置了4种不同的网络结构模型,分别为随机图网络模型(random graph network)、小世界网络模型(small world network)、无标度BA网络模型(scale free network-BA)和无标度DM网络模型(scale free network-DM)[35].4种网络拓扑结构节点度分布情况如图 1所示,4种网络结构中节点度的统计信息见表 4.
|
Fig.1 Node degree distribution in the network topology 图 1 网络拓扑结构中节点度分布情况 |
|
|
Table 4 Node degree of statistical information in the network topology 表 4 网络拓扑结构中节点度的统计信息 |
网络中的资源分布采用Zipf-like[36, 37]分布.在资源初始分布相同的情况下,分别设计了服从均匀分布和Zipf-like分布的查询.实验中,共提供100类5 000个对象和10 000个查询.每类对象依据Zipf-like分布设置相应的流行度.依据它们的流行度设置相应的同类对象的个数,并随机的选择节点将对象进行复制,使得高流行度的对象获得较高的复制率.对象副本分布分析情况如图 2所示.
|
Fig.2 Object distribution 图 2 对象分布 |
对于查询,在服从Zipf-like[36, 37]的查询分布中,依据对象的流行度,从100类对象中随机的选择查询关键字进行查询.这种方式使得具有高流行度的对象更多的被查询,更接近于真实的网络应用情况.实际实验中的查询分布如图 3所示.
|
Fig.3 Query distribution 图 3 查询分布 |
(1) 副本复制前后搜索性能的比较.
为了评价基于需求的稀有资源主动复制策略的有效性,在第4.1节所布置的实验环境下,分别执行了RW和HSA算法,并对其在未采用复制策略和采用复制策略(基于需求的全路径复制DPR-FP)两种情况下的点击率进行了对比,结果分别如图 4和图 5所示.
|
Fig.4 Searching success rate of HSA under DPR replication and no DPR replication 图 4 在执行DPR复制与不执行复制情况下,HSA的查询点击率 |
|
Fig.5 Searching success rate of RW under DPR replication and no DPR replication 图 5 在执行DPR复制与不执行复制情况下,RW的查询点击率 |
执行了DPR复制策略的RW和HSA算法的查询点击率均有所提高,特别是对流行度比较低的对象(object popularity<2%),其查询点击率提高的幅度较大.在图 4中,执行复制策略的HSA算法在4种网络结构中,当对象的流行度小于2%时,其查询点击率大约被提高了20%~30%.而在图 5中也显示:执行复制策略的RW算法,在对象的流行度在1%左右,其查询点击率也分别被提高了10%~20%.在图 5(d)中显示,所提高的查询点击率更高.从图 4和图 5的对比来看:无论是否执行复制策略,HSA算法在4种网络拓扑结构中的查询点击率均高于RW算法.在DPR-FD和DPR-MD两种复制策略下的点击率情况将在实验中体现,这里不再重复给出.
为了更清晰地展现流行度较低时的搜索成功率的情况,图 6和图 7分别用点图的形式给出了对象流行度小于0.5%的各类不同对象搜索成功的情况.
|
Fig.6 Searching success rate of HSA under DPR replication and no DPR replication (object popularity<0.5%) 图 6 在执行DPR复制与不执行复制情况下,HSA的查询点击率(object popularity<0.5%) |
|
Fig.7 Searching success rate of RW under DPR replication and no DPR replication(object popularity<0.5%) 图 7 在执行DPR复制与不执行复制情况下,RW的查询点击率(object popularity<0.5%) |
从图 4~图 7可以看出,4种网络结构中,搜索查询点击率的变化趋势是相似的.因此在后续的实验与分析中,只给一种较为流行的无标度网络结构下的对比情况,而与其类似的其他3种结构下的对比情况不再重复给出.
(2) 几种复制策略下的点击率与稀有资源平均被复制数目的比较.
为了分析DPR复制策略的性能,我们也介绍了另一种稀有资源的主动复制策略PR[18].在PR中,通过随机漫步的方式向前搜索,判定资源是否为稀有资源.当搜索失败时,判定为稀有资源,则选择在搜索终端节点处将副本复制.
图 8给出了在网络中对象分布与查询分布都服从Zipf-like分布的情况下,如图 2和图 3所示,HSA在没有复制发生和不同复制策略发生情况下的查询点击率情况.从图 8可以看出,任何一种复制策略的点击率均高于没有复制发生情况下的点击率.原因是显而易见的,有复制发生增加了资源的流行度,自然会提高查询的点击率.但是不同副本复制策略下,点击率的提高程度是不同的.在4种策略中,PR复制策略下点击率最低,而基于需求的DPR-FP,DPR-FD和DPR-MD这3种策略下的点击率均高于PR策略.这一结果说明:PR复制存在一定的盲目性,没有将副本复制到更需要的节点上;这也说明:基于需求的DPR复制策略能够降低这种盲目性,将资源副本复制到有效的位置上.在基于需求的3种DPR-FP,DPR-FD和DPR-MD策略中,全路径复制策略DPR-FP下的点击率最高,全需求复制策略DPR-FD和最大需求复制策略DPR-MD下的点击率相似,最大需求复制策略DPR-MD下的点击率略低于全需求复制策略DPR-FD下的点击率.其主要的原因是:DPR-FP,DPR-FD和DPR- MD这3种复制策略下,复制的副本数目是不同的.
|
Fig.8 Query follows Zipf distribution, Searching success rate of HAS under different replications and no replication 图 8 查询服从Zipf分布,不同复制策略与无复制策略下,HSA的点击率 |
在对象分布与查询分布都服从Zipf-like分布的情况下,不同流行度对象在不同复制策略下复制的平均副本数目如图 9所示.DPR-FP策略下复制的平均副本个数远高于其他3种复制策略.因此,在4种复制策略中, DPR-FP以最高的副本复制数目获得了最好的点击率.图 9显示,最大需求复制策略DPR-MD复制的平均副本数目最少.全需求复制策略DPR-FD和PR复制策略下复制的平均副本数目相似,但PR的略高于DPR-FD.
|
Fig.9 Query follows Zipf distribution,the average number of copies under different replications 图 9 查询服从Zipf分布,不同复制策略下平均的副本复制数目 |
综合图 8和图 9可以看出:基于需求的全路径复制DPR-FP以复制较多的副本数目获得最好的点击率,基于需求的全需求复制策略DPR-FD以低于PR复制策略的平均复制副本数目获得了高于PR低于DPR-FP的点击率,基于需求的最大需求复制策略DPR-MD以最少的副本数目获得了与DPR-FD相似较好的点击率.综合对比来看:基于需求的DPR优于PR策略,基于需求的最大需求复制策略DPR-MD是最好的.其主要原因是:基于需求的DPR有效地将副本复制到了需要的位置上,克服了PR策略的盲目性.其中,DPR-MD将副本复制到最大需求的位置上,并获得了最优的性能,说明这种基于需求的DPR是有效的.
为了更进一步说明这种基于需求的复制策略的有效性,我们还设置了在对象分布为Zipf-like分布不变而查询分布为均匀分布情况下,几种不同复制策略所表现的点击率和平均的副本复制情况,其结果分别如图 10和图 11所示.
|
Fig.10 Query follows uniform distribution,Searching success rate of HAS under different replications and no replication 图 10 查询服从均匀分布,不同复制策略与无复制策略下HSA 的点击率 |
|
Fig.11 Query follows uniform distribution,the average number of copies under different replications 图 11 查询服从均匀分布,不同复制策略下的平均副本复制数目 |
从图 10和图 11可以看出:其点击率和平均副本复制情况与图 8和图 9相似;但是对比于图 8,图 10显示对流行度较低而需求较高的对象的点击率在基于需求的DPR策略下有多于10%的提高,而相应的副本复制数目没有更明显的增加,这也进一步说明这种基于需求的DPR的有效性;对比于图 9,在图 11中显示,DPR-FD的平均副本复制数目高于PR,这说明随着稀有资源需求度的提高,其副本复制数目有随着增长的趋势,适合于需求发生变化的动态情况.
(3) 几种复制策略副本复制总数量与总体趋势比较.
在无标度网络结构下,对不同流行度范围内的整体副本复制情况进行了对比.实验室中,在Zipf-like和均匀(uniform)两种查询分布情况下,搜集了不同流行度范围内的整体副本复制情况,其结果分别如图 12、图 13所示.
|
Fig.12 Query follows Zipf distribution,the total number of copies under different replications 图 12 查询服从Zipf 分布,不同复制策略下总的副本复制数目 |
|
Fig.13 Query follows uniform distribution,the total number of copies under different replications 图 13 查询服从均匀分布,不同复制策略下总的副本复制数目 |
在图 12和图 13中,X坐标表示对象的流行度,Y坐标表示副本复制的总数目.每个点所对应的横坐标表示其对象流行度在相应最小上下界内的平均流行度,每个点所对应的纵坐标表示该点所在横坐标最小上下界范围内的对象的副本复制总数目.如在x$ \in $[0.1,0.2]内的点,其对应的横坐标表示对象流行度在该范围内的平均值.而该点所对应的纵坐标为流行度在[0.1,0.2]范围的对象的副本复制数目之和.从图 12和图 13可以看出:随着对象流行度的不断增加,对象被复制的副本数目呈不断下降趋势.对低流行度的对象复制了更多的副本,而对流行度较高的对象复制了较少的副本.图 12和图 13显示,几种副本复制策略均实现了对低流行度资源即稀有资源的有效复制.
(4) 存储与通信消耗的对比.
为了更好地对几种副本复制策略的整体性能进行分析,我们对几种复制策略的整体通信消耗和存储消耗进行了对比.复制策略产生了额外的网络通信消耗和存储消耗.网络通信消耗主要包括复制策略向前探测所产生的探测消耗和决定进行副本复制所产生的复制通信消耗.不同的副本复制策略会产生不同的网络通信消耗,但同时,通过不同的副本复制策略对资源副本进行有效的复制,会不同程度地提高资源的查询点击率,从而会不同程度地降低对资源搜索的通信开销.因此,为了对比几种复制策略的整体性能,我们对几种复制策略下产生的整体通信开销进行了对比分析,如图 14(a)所示,而整体的存储消耗的对比分析如图 14(b)所示.
|
Fig.14 The overall performance comparison under different replications 图 14 不同复制策略的整体性能比较 |
从图 14可以看出:在均匀查询分布的情况下,各种复制策略的整体通信消耗和整体存储消耗都高于Zipf-like查询分布的情况.其主要的原因是:在查询服从均匀分布的情况下,有更多的对稀有资源的查询请求;而在Zipf-like查询分布的情况下,对稀有资源的查询请求也相对较少,因此均匀查询分布情况下产生了更多的通信开销和存储开销,但对比于存储开销,其通信开销的消耗略高.而在4种搜索策略中,PR产生的整体通信开销最多.主要原因是:在PR策略中,对稀有资源的复制存在较大的盲目性,未能更好地提高搜索的性能.DPF-FP复制策略的存储开销最大,主要原因是在有需求的路径上进行了全部节点的稀有资源复制.但这种策略下的通信消耗也是最低的,主要是因为通过更多的副本复制提高了查询效率,从而降低了整体的通信消耗.因此,可以在有足够节点存储空间的网络构成情况下,采用这种按需求的全路径复制策略来降低网络的通信开销.
图 14也显示出:DPR-MD复制策略整体的存储消耗是最低.同时,在Zipf-like查询分布下,其整体的通信消耗低于PR策略,略高于通信消耗最少的DPR-FP策略,与策略DPR-FD的通信消耗是相似的.在均匀查询分布情况下,即,加大对稀有资源查询需求的情况下,DPR-MD复制策略的整体的通信消耗低于PR策略较多,略高于通信消耗最少的DPR-FP策略.这表明,基于需求的最大需求复制策略DPR-MD将副本复制到最大需求的节点上是最有效的.
结合图 8、图 9和图 14,从查询点击率、整体通信开销和整体的存储开销这3方面对4种复制策略进行综合评价,基于需求的最大需求复制策略DPR-MD的综合性能最好.
5 结束语为了提高非结构P2P网络中稀有资源的查询点击率,本文从提高稀有资源的副本率入手,对资源的搜索与复制技术进行了研究.提出了一种稀有资源的主动复制策略,由拥有稀有资源的节点主动发起对稀有资源的搜索,有效获取局部需求信息,实现了稀有资源的按需复制,有效提高其流行度和点击率.基于局部需求信息,本文共提供3种不同的按需复制策略,分别为DPR-FP,DPR-FD和DPR-MD,并给出了一种稀有资源搜索算法HSA.仿真实验结构表明:无论是在复制策略下还是在非复制策略下,对比于随机漫步,RW,HSA搜索算法均获得了较高的查询点击率;同时,在HSA算法下,对所给出的DPR-FP,DPR-FD和DPR-MD这3种复制策略和已有的PR复制策略进行了对比分析.结果显示:所给出的3种复制策略的综合性能均好于PR,说明这种按需求的复制策略降低了复制的盲目性;同时,在所给出的DPR-FP,DPR-FD和DPR-MD这3种复制策略中,基于需求的最大需求复制策略DPR-MD获得最好的综合性能.本文研究显示,准确获取用户需求是改进非结构P2P搜索有效性的一个根本因素.在今后的工作中,将基于用户对资源的需求,对网络资源基于需求的合理化分布和基于用户需求的高效搜索技术进行深入研究.
| [1] | Gupta I, Birman K, Linga P, Demers A, Renesse RV. Kelips: Building an efficient andstable P2P DHT through increased memory and background overhead. In: Proc. of the 3rd Int’l Conf. on Peer-to-Peer Computing. Berkeley: Springer-Verlag, 2003.160-169 . |
| [2] | Cameron C, Khalil I, Tari Z. An ID-based approach to the caching and distribution of peer-to-peer, proxy-based video content. Journal of Network and Computer Applications, 2014,37:293-314 . |
| [3] | Liu XT, Cai K, Yue Q, Ji TK. A versatile crawler for kademlia-based networks and its convergence analysis. Chinese Journal of Electronics, 2013,22(1):7-14. |
| [4] | Ma WM, Zhang YJ, Meng XW. Toward convergent search for large peer-to-peer networks. Journal of Internet Technology, 2014, 15(1):19-34 . |
| [5] | Stutzbach D, Rejaie R. Understanding churn in peer-to-peer networks. In: Proc. of the ACM Internet Measurement Conf. (IMC). New York: ACM Press, 2006.189-202 . |
| [6] | Zhang R, Hu YC. Assisted peer-to-peer search with partial indexing. IEEE Trans. on Parallel and Distributed Systems, 2007,18(8): 1146-1158 . |
| [7] | Frankel J, Pepper T. Gnutella. http://www.gnutella.com. |
| [8] | Heinla A, Kasesalu P, Tallinn J. KaZaA. http://www.kazaa.com. |
| [9] | Heinla A, Kasesalu P, Tallinn J. Skype. http://www.skype.com. |
| [10] | Ripeanu M. Peer-to-Peer architecture case study: Gnutella network. In: Proc. of the 1st Int’l Conf. on Peer-to-Peer Computing. Linkoping: IEEE, 2001.99-100 . |
| [11] | Jiang S, Guo L, Zhang XD, Wang HD. LightFlood: Minimizing redundant messages and maximizing the scope of peer-to-peer search. IEEE Trans. on Parallel and Distributed Systems, 2008,19(5):601-614 . |
| [12] | Lv Q, Cao P, Cohen E, Li K, Shenker S. Search and replication in unstructured peer-to-peer networks. In: Proc. of the 16th Annual ACM Int’l Conf. on Supercomputing. New York: ACM Press, 2002.84-95 . |
| [13] | Mei HY, Zhang YJ, Meng XW. CSA: A credibility search algorithm based on different query in unstructured peer-to-peer networks. Mathematical Problems in Engineering, Vol. 2014.1-20 . |
| [14] | Meng XF, Wang YL, Ding YL. An optimized strategy for update path selection in unstructured P2P networks. Computer Networks, 2012,56(17):3744-3755 . |
| [15] | Ma WM, Meng XW, Zhang YJ. Bidirectional random walk search mechanism for unstructured P2P network. Ruan Jian Xue Bao/ Journal of Software, 2012,23(4):894-911 (in Chinese with English abstract). |
| [16] | Loo BT, Hellerstein JM, Hubsch R, Shenker S, Stoica I. Enhancing P2P file-sharing with an internet-scale query processor. In: Proc. of the 30th Conf. on VLDB. Toronto: VLDB Endowment, 2004. 432-443. |
| [17] | Qiao Y, Bustamante FE. Structured and unstructured overlays under the microscope. In: Proc. of the USENIX Annual Technical Conf. Berkeley: USENIX Association, 2006. 341-355. |
| [18] | Gao GQ, Li RX, Wen KM, Gu XW. Proactive replication for rare objects in unstructured peer-to-peer networks. Journal of Network and Computer Applications, 2012,35(1):85-96 . |
| [19] | Gkantsidis C, Mihail M, Saberi A. Hybrid search schemes for unstructured peer-topeer networks. In: Proc. of the 24th Annual Joint Conf. of the IEEE Computer and Communications Societies. 2005.1526-537 . |
| [20] | Mei HY, Zhang YJ, Meng XW, Ma WM. Limited search mechanism for unstructured peer-to-peer network. Ruan Jian Xue Bao/ Journal of Software, 2013,24(9):2132-2150 (in Chinese with English abstract). |
| [21] | Tsoumakos D, Roussopoulos N. Adaptive probabilistic search in peer-to-peer networks. In: Proc. of the 2nd Int’l Workshop on Peer-to-Peer Systems (IPTPS 2003). IEEE, 2003.102-109 . |
| [22] | Xu M, Zhou SG, Guan JH, Hu XH. A path-traceable query routing mechanism for search in unstructured peer-to-peer networks. Journal of Network and Computer Applications, 2010,33(2):115-127 . |
| [23] | Sharifi L, Khorsandi S. A popularity-based query scheme in P2P networks using adaptive gossip sampling. Peer-to-Peer Networking and Applications, 2013,6(1):75-85 . |
| [24] | Himali DMR, Sushil K. SPUN: A P2P probabilistic search algorithm based on successful paths in unstructured networks. In: Proc. of the IEEE Int’l Symp. on Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW). Shanghai: IEEE, 2011.1610-1617 . |
| [25] | Niu JW, Dai B, Sun LM, Lin JL, Xiong YP. PQBCF: A P2P query algorithm based on betweenness centrality forwarding in opportunistic networks. Acta Electronica Sinica, 2013,41(9):1815-1820 (in Chinese with English abstract) . |
| [26] | Shen HY, Zhu YW. A proactive low-overhead file replication scheme for structured P2P content delivery networks. Journal of Parallel and Distributed Computing, 2009,69(5):429-440 . |
| [27] | Liao XF, Zhang F, Jin H, Yu LC. iDARE: Proactive data replication mechanism for P2P voD system. In: Proc. of the CIT IEEE Computer Society. Bradford: IEEE, 2010.682-689 . |
| [28] | Cohen E, Shenker S. Replication strategies in unstructured peer-to-peer networks. In: Proc. of the 2002 Annual Conf. of the Special Interest Group on Data Communication. New York: ACM Press, 2002.177-190 . |
| [29] | Zhou JY, Song AB, Luo JZ. Evolutionary game theoretical resource deployment model for P2P networks. Ruan Jian Xue Bao/ Journal of Software, 2013,24(3):526-539 (in Chinese with English abstract). |
| [30] | Zhai HB, Jiang H, Sun Y, Li J, Li ZC. A node-link based cache deployment algorithm for P2P traffic in ISP networks. Journal of Computer Research and Development, 2013,50(1):122-135 (in Chinese with English abstract). |
| [31] | Ferreira RA, Ramanathan MK, Awan A, Grama A, Jaganathan S. Search with probabilistic guarantees in unstructured peer-to peer networks. In: Proc. of the 5th Int’l Conf. on Peer-to-Peer Computing. IEEE, 2005.165-172 . |
| [32] | Shen HY. Ead: An efficient and adaptive decentralized file replication algorithm in P2P file sharing systems. In: Proc. of the 8th Int’l Conf. on Peer-to-Peer Computing. IEEE, 2008.99-108 . |
| [33] | Puttaswamy KPN, Sala A, Zhao BY. Searching for rare objects using index replication. In: Proc. of the IEEE INFOCOM. Phoenix: IEEE, 2008.1723-1731 . |
| [34] | Mei HY, Meng XW. An optimal replica selection algorithm based on local request characteristic. Journal of Beijing University of Posts and Telecommunications, 2012,35(3):16-19 (in Chinese with English abstract) . |
| [35] | Jelasity M. The peersim simulator. 2007. http://peersim.sourceforge.net/2007 |
| [36] | Sripanidkulchai K. The popularity of Gnutella queries and its implications on scalability. 2001. http://www.cs.cmu.edu/~kunwadee/research/p2p/paper.html |
| [37] | Breslau L, Cao P, Fan L, Phillips G, Shenker S. Web caching and Zipf-like distributions: Evidence and implications. In: Proc. of the 18th Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM’99). New York: IEEE, 1999.126-134 . |
| [15] | 马文明,孟祥武,张玉洁.面向非结构化P2P网络的双向随机漫步搜索机制. 软件学报,2012,23(4):894-911. |
| [20] | 梅红岩,张玉洁,孟祥武,马文明.非结构P2P网络受限搜索机制. 软件学报,2013,24(9):2132-2150. |
| [25] | 牛建伟,戴彬,孙利民,林佳骝,熊永平.PQBCF:一种基于中间中心度的机会网络P2P查询算法.电子学报,2013,41(9):1815-1820 . |
| [29] | 周经亚,宋爱波,罗军舟.P2P网络中一种基于进化博弈的资源配置模型. 软件学报,2013,24(3):526-539. |
| [30] | 翟海滨,蒋海,孙毅,李军,李忠诚.一种基于点路结合的骨干网P2P缓存部署方法.计算机研究与发展,2013,50(1):122-135. |
| [34] | 梅红岩,孟祥武.基于局部需求特征的副本优化选择算法.北京邮电大学学报,2012,35(3):16-19 . |