一种新型的层次P2P搜索模型

　　收稿日期 :2003 - 06 - 25 　　作者简介 :林燕 (1978 - ) ,女 ,山东烟台人 ,硕士研究生 ,主要研究方向 :计算机网络应用技术 ; 　姚青 (1963 - ) ,女 ,山东济南人 , 副教授 ,主 要研究方向 :计算机网络技术、网络信息安全. 文章编号 :1001 - 9081(2003) 12 - 0070 - 03 一种新型的层次 P2P 搜索模型 林 　燕 ,姚 　青 ( 山东大学 计算机科学与技术学院 ,山东 济南 250061) 摘 　要 :在分析现有 P2P 模型的基础上 ,提出了一种新的 P2P 搜索模型 ,该模型是分层的混合结 构 ,利用分组和建立搜索空间的机制 ,来提高搜索的效率 ,增强系统的可扩展性。同时为低带宽节点 引入了搜索代理的机制 ,提高了带宽的利用率 ,减少了搜索延迟。而且为了增强网络的自恢复性 ,利 用缓存机制引入了备用连接 ,使搜索模型具有较好的容错能力。 关键词 :P2P ;搜索 ;分组 ;RTT 中图分类号 : TP393 　　文献标识码 :A A Ne w Type of Hierarchical P2P Model for Research L IN Yan , YAO Qing (School of Com puter Science and Technology , S handong U niversity , Jinan S handong 250061 , China) Abstract : This paper analyzes the current P2P models , then proposes a new type of P2P model that is a hierarchical hybrid model . In this model , grouping mechanism and the idea of search space are introduced to provide the efficient query and scalability. For the narrow bandwidth peer , the search proxy is adopted to make full use of bandwidth and to reduce the network delay. The back2up links using cache mechanism are introduced to make the model has good fault2tolerance capability. Key words : P2P ; search ; group ; RTT 　　随着网络技术的飞速发展和网络规模的不断扩大 ,网络 中的设备及计算单元的种类和数量也越来越多。然而目前的 互联网仍然是以 C/ S 模式为主 ,尤其是 Web 技术的发展使得 许多 Web 服务器成为信息的主要提供源 ,也就使得整个 Internet 系统依附于这些少量的服务器节点 ,导致网络中大量 的边缘节点上的资源无法充分利用 ,形成大量的信息孤岛。 P2P( Peer To Peer)计算技术的目的就是希望能够充分利 用互联网中所蕴含的潜在计算资源。P2P 中文称为对等网 络 ,是指分布式系统中的各个节点是逻辑对等的 ,与 C/ S 计 算模型不同的是 ,P2P 计算模型中不再区别服务器 Server 以 及客户端 Client ,而是称为 Servent ,系统中的各个节点之间可 以直接进行数据通信而不需要通过中间的服务器。其实质在 于引导网络计算模式从中心走向分散 ,从中央走向边缘 ,充分 利用终端设备的处理能力 ,每个节点都主动地加入网络中共 享资源。 1 　目前的 P2P 模型 Napster 采用集中化的结构[ 1 ] ,由一个目录服务器来维护 所有的共享目录 ,并进行查询 ,但文件共享交换的过程是 P2P 方式。其缺点是存在目录服务器的单点失败和扩展性问题。 Gnutella 在进行搜索的过程中所采用 TTL2Flooding 算法[ 2 ] , 虽然具有分布式的搜索结构 ,但却使得消息数量呈指数级增 长。Freenet 提供的是基于 P2P 的分布式“匿名”文件存储服 务[ 3 ] ,它在文件的检索以及可扩展性方面还很不完善。Chord 是 MIT 提出来的基于 P2P 的信息资源定位和查找模型[ 4 ] , 该模型维护路由的邻接方式 ,但是它没有很好地解决新节 点加入的命名冲突问题以及系统的可扩展性问题 ,同时它消 息的前递速度也比较低。CAN 采用基于 n 维空间分割的节 点增减管理策略[ 5 ] ,节点的邻接关系受限于节点间 PNS 的几 何邻接关系。这种策略导致该系统的任意两点之间通信时消 息传递的逻辑路径长度 Hops 为多项式量级 ,同时当几何维数 增加时节点的 PNS管理也十分复杂。 2 　建立一种新的层次模型 2. 1 　网络结构 图 1 　Peer 节点的结构 Peer : 位于层次模型的最低层即第 0 层 ,所有加入 P2P 搜索网络的节点都是作为 Peer 存在的。网络中低带宽 (NarrowBandwidth Peer)的节点 ,我们称为 NBPeer ,为了节约 宝贵的带宽 ,这类节点由上层的 PeerHub 代理接受查询请 求[ 5 ] ,因此要向 PeerHub 注册共享文件的目录信息。对带宽 较高、性能较好的节点 BroadBanwidthPeer ,我们称为 BBpeer , 第 23 卷第 12 期 2003 年 12 月 　 计算机应用 Computer Applications 　 Vol. 23 , No. 12 Dec. , 2003 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. 这类节点可以直接提供搜索服务。这两类节点都可以提供文 件共享的服务。Peer 节点的结构如图 1。 PeerHub( PH) : PH 处于层次模型的第 I 层 , I = 1 ,2 ,3 , ⋯, K - 1 ,我们记为 PHI , K为模型的最高层。PH 的职责是接 受 NBPeer 注册 ,检索和管理 NBPeer 的文件信息 ,将查询或 响应消息组播到 BBpeer ;确定和发现最快速的对等点连接 等。这里 PH 仅仅维护 NBPeer 共享文件的目录信息 ,真正进 行共享的时候仍然是 P2P 的方式。PH 由固定的服务器充 当。 RegisterServer (RS) : 最高层即第 K 层。接受各层所有 PH 的注册信息。当 Peer 提出查询 PH 信息请求的时候 ,提供 PH1 的 IP 地址。为了增加可扩展性和进行负载的平衡 ,设计 多个 RS并存。 2. 2 　关键技术的实现 2. 2. 1 　分组机制 为了加快消息的传送速度 ,减少网络延迟 ,Peer 选择一个 与之连接速度最快的 PH 加入 ,作为该 PH 的组中的一员。 Peer 的分组算法 : ① Peer 向 RS提交一个查询 PH 的消息 ; ②RS搜索自己的数据库 ,并返回所有 PH1 的 IP 地址 ; ③Peer 收到 K个 PH1 的 IP 地址后 ,向每个 PH1 发送 I 次 Ping 消息 ,并记录每次消息到达的时间 PingTime[J ] [ I ] , I 为 Ping 次数 ,J 为 PH1的标号 ,J = 1 ,2 , ⋯, K; ④对每个 PH1 计算 PingTime[J ]的平均值 APT[J ] ; ⑤求 APT[J ]的最小值 MinAPT[ N ] ,N 是具有最小 APT 的 PH1 的标号 ; ⑥加入第 N 个 PH1 的组中。分组过程如图 2。 图 2 　分组过程 PHk 的分组 : 与 Peer 的分组类似 ,不同的是 RS 返回的 应该是 PHk + 1的 IP 地址 ,PHk 加入 PHk + 1的组中。 NBpeer 的注册机制 : 分组后 NBPeer 通过注册服务向 PH1 进行注册。 ①NBPeer 向 PH1 提交注册请求 Register (NBPeer) ; ② PH1 接受注册请求 ,并请求 NBPeer 提交文件信息 ; ③NBPeer 提交共享文件信息 ; ④ PH1 更新文件目录信息数据库。 2. 2. 2 　高速缓存与备用连接 Peer 和 PH 都要缓存它所在组的 PH 的 IP 地址 ,当再次 加入的时候 ,可以减少 Ping 和计算的时间。同时缓存加入组 时计算的 APT[J ]的值 ,以便在 MinAPT[ N ]无法连接的时候 , 重新选取一个最小值作为备用连接 ,加入组中。 缓存中的超时 ( TimeOut) : 因为网络是动态变化的 ,任何 连接都不可能是不变的 ,为了使缓存机制更加有效 ,引入 TimeOut。缓存一个最快连接的时候 ,启动计时器 Timer ,当 超时 ( TimeOut)后就要将这个最快连接从缓存中删除。 2. 2. 3 　平均往返延迟 (RTT)确定 RTT 是指从发出查询信息到接收到响应消息的这段时 间间隔 ,为了选择一个最快的响应连接进行文件的共享 ,每次 查询过程中 ,PH 对每个 Peer 或 PH 的响应都计算一个 RTT 的值 ,并据此计算该 Peer 或 PH 的平均 RTT。 RTTnew[i ] (RTTold[i ]) / RTTold 当前 Peer[i ]或 PH[i ]的平均 RTT ;RTTnew 重新计算的 平均 RTT/ { RTTs[i ] = EndTime[i ] - Start Time[i ] ; / RRTs 是一个新的 RTT 时间/ / Start Time[i ]是查询消息发出的时间 ; EndTime [ i ]是收到查询 响应的时间/ RTTnew = a 3 RTTs[i ] + (1 - a) 3 RTTold ; / 1 > a > 0/ Return (RTTnew) ; RTTold[i ] = RTTnew[i ] ; } 2. 2. 4 　搜索机制 基本搜索 Peer 将请求提交给所在组的 PH1 , PH1在本地文件目录 信息数据库中进行查询 ,并将此请求组播到所有的 BBPeer 上。如果二者都没有返回响应结果 ,则 PH1 再将请求交给所 在组的 PH2 ,PH2 将请求广播到组中所有其它的 PH1 ,继续查 询 ,直到返回查询响应[ 6 ] 。若在第一层的组中可以满足查询 请求 ,则不需要将请求转发给 PH2 。 搜索空间的引入 如果有多个 Peer 响应请求 ,应该选择具有最快连接速度 即平均 RTT 最小的 Peer 来进行共享。但是如果这些响应的 Peer 位于不同的组中 ,按照基本搜索算法我们优先选择了同 组中的 Peer ,而同组的这个 Peer 并不能保证具有最快速的连 接。为了解决这个问题我们引入了搜索空间的概念。 定义搜索空间 搜索空间是组的扩展 ,是整个网络搜索空间的一个子空 间 ,它将每次搜索的最小范围从组扩大到一个搜索空间。这样 每个搜索请求都转发到整个搜索空间中 ,如果该空间无法满足 查询请求则将请求转发到其它搜索空间中 ,继续进行。定义搜 索空间 SP是 M 层的 ,即从第 0 层到第 M - 1 层 ,如图 3。 图 3 　定义搜索空间 基于搜索空间的搜索算法 (查询空间 I 的某个 Peer 提出 查询请求 Q)如下 : Search(Q) while Search- SP(SPi ,Q) 为空 do {k = M ; 将 Q 转发给 PHk ; PHk将 Q 广播到该组中所有其它的 SPj ,j < > i ; Search- SP(SPj , Q) 17第 12 期 林燕等 :一种新型的层次 P2P 搜索模型 　　　　 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved. } Search- SP(SPi ,Q) : PH0 = Peer ; / 为了算法描述方便将 Peer 定义为 PH0/ For i = 0 to M - 1 / M 是搜索空间的层数/ {PHi向 PHi + 1发送查询消息 Q ; IF i = 0 then {PHi + 1在本地文件数据库中进行查询 ; PHi + 1将 Q 组播到该组的所有的 BBPeer ;} PHi + 1将 Q 组播到所有的 PHi ; } Start Time[j ] = PHj 发送 Q 的时间 ,j = 1 ,2 , ∗,M ; If (N[ Q ] = = 1 ) then Response (Q) ; / N[ Q ]是 Q 的响应数量/ If (N[ Q ] > 1) then { For i = 1 to N[ Q ] { Response (Q) ; End time[j ] = Ri 的到达 PHj 时间 ; RTTnew[j ] (RTTold[j ]) ;} 求 RTTold[j ]的最小值 MinRTT ; PHj 缓存具有 MinRTT 的 Peer 的信息 ; } IF(响应 Peer 的数量 N = 0) then R 为空 ; Response (Q) IF R 自 BBPeer then / 如果 R 来自 BBPeer ,应该从 PH0开始向上转发/ PH0 将 R 转发给 PH1 ; For i = 1 to M - 1 / 如果 R来自 PH1 的本地数据库 ,那么应该从 PH1 向上转发 / PHi将 R 向上转发给 PHi + 1 ; / 将 R 转发给搜索空间的最高/ For i = M - 1 downto 0 PHi + 1向下转发 R 给 PHi ; / 最上层将 R 返回给提交请求的 PH0/ 3 　性能分析 带宽利用率 由于采用了分组机制和搜索空间的策略 ,查 询消息在较小的范围内广播 ,与 Gnutella 相比消息的数量大 大减少 ,减少了网络的拥塞 ,同时对 NNPeer 引入由 PH 代理 查询的机制 ,使得 NNPeer 的带宽主要用来进行文件的传输 , 有效地利用了带宽。 搜索效率 基于搜索空间的搜索算法使搜索同时具有广 度和深度的特点 ,增加了搜索的成功率。搜索消息仅在多数 PH 都失败的情况下 ,才可能丢失。而且算法返回的响应 Peer 是具有最快连接速度的 ,提高了搜索的效率 ,减少了延迟 ,有 利于快速的文件共享。 可扩展性 在 Peer 数量的可扩展性方面 ,模型设计利用了 互联网中扩展性最好的 DNS 系统 ,设 DNS 名字服务器所维 护的所有主机数量为 N (DNS) ,层次模型中 Peer 的数量为 N ( P) ,则 N ( P) = k % 3 N (DNS) 。P2P 中的节点数不可能超过 DNS所有的主机数量。设 PH 的数量为 N ( PH) ,一个组中节 点的最大数量为 N ( G) ;则它们之间的关系为 : N ( PH) = p % 3 k % 3 N (DNS) N ( G) = N ( P) / N ( PH) 同时由于采用了 RTT 机制 ,使得 Peer 数量的增加对搜 索延迟的影响处于对数级的范围。 负载的平衡 模型采用多个 RS 和层次化多 PH 的结构 , 在注册和搜索方面都提供了负载平衡的能力。 参考文献 [ 1 ] 　Napster. http :/ / www. napster. com[ EB/ OL ] ,2002 - 02. [ 2 ] 　Gnutella. http :/ / www. gnutella. org[ EB/ OL ] ,2002 - 04. [ 3 ] 　Stoica I , Morris R , Karger D , et al . A scalable peer2to2peer lookup service for Internet applications [ A ] . Proc ACM SIG2 COMM[ C] , August 2001. [ 4 ] 　Harren M , Hellerstein J M , Huebsch R , et al . Complex queries in dht2based peer2to2peer networks [ A ] . Proceedings of IPTPS02 [ C] . Cambridge , USA , March 2002. [ 5 ] 　Annextein FS , Berman KA , Jovanovic MA , et al . Indexing Tech2 niques for File Sharing in Scalable Peer2to2Peer Networks [ A ] . Proceedings IEEE ICCCN 2002[ C] ,2003. [ 6 ] 　Jovanovic MA , Annexstein FS , Bernnan KA. Modling Peer2to2 Peer Network Toplogies Through “Small - World" Models and Powerlaws[ A ] . IX Telecommunications Forum TEL FOR 2001 [ C] . Belgrade , 2001. 20 - 22. (上接第 69 页) 3. 4 　更新兴趣模型 由于兴趣的广泛和易变性 ,因此不断的更新是保持兴趣 模型准确完善的重要环节。通常可以把用户输入的检索信息 以及用户所访问的检索结果信息作为更新兴趣模型的信息 源。假设检索时输入的关键字和所访问的检索结果页面的特 征词条组成集合 P = { P1 , P2 , ⋯, Pm } , 兴趣模型为 U = { ( L 1 , W 1) , ( L 2 , W 2) , ⋯, ( L n , W n) } ,更新算法如下 : for (i = 1 ;i < = m ;i + + ) for (j = 1 ;i < = n ;j + + ) if ( Pi = = L j) Wj + = min{Wk| 1 ≤k ≤n} / 3 兴趣模型中包含信息源词条 ,则修改兴趣模型中该词条 所对应的权 3 / else n + + (L n , Wn) = ( Pi , min{Wk| 1 ≤k ≤n}) / 3 兴趣模型中不包含信息源词条 ,则向兴趣模型中添加一 个新的二元组 3 / for (i = 1 ;i < = n ;i + + ) Wi = Wi ∑ n j = 1 wj / 3 最后将权单位化 3 / 参考文献[1 ] 　张卫丰 , 徐宝文 , 周晓宇 ,等. 元搜索引擎综述 [J ] . 计算机科学 , 2001 , 28 (8) .[ 2 ] 　Howe AE , Dreilinger D . SavvySearch : a meta 2 search engine thatlearns which search engine to query[J ] . ACM Transactions on In2formation Systems ,1997 ,3 (15) .[ 3 ] 　Letizia L H . An Agent that Assists Web Browsing [ A ] . Intl JiontConf on Artificial Intelligence[ C] ,1995.[4 ] 　Levy MR. Web Programming in Guide[J ] . SOFTWARE - Prac2tice & Experience , 1998 , 28 (15) .[ 5 ] 　Burkoyc KB. The InfoFinder Agent : Learning user intereststhrough heuristic phrase extraction [J ] . IEEE Expert ,1997 ,12(5) .[ 6 ] 　Kautz H , et al . Refferal Web : Combining Social Networks andCollaborative Filtering[J ] . Communication of ACM ,1997 ,40 (3) .[ 7 ] 　汪晓岩 ,胡庆生 ,李斌 ,等. 面向 Internet 的个性化智能信息提取[J ] . 计算机研究与发展 ,1999 ,36 (9) .[8 ] 　Cheung DW , Kao B , Lee J . Discovering User Acess Patterns onthe World Wide Web Knowledge2based Systems[J ] . Journal Else2 vier Science ,1998 ,10 (7) . 27　　　　 计算机应用 2003 年 © 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.