基于 Bittorrent 网络的快速搜索策略zt
丁 林，程学旗，刘 悦，吕建明(中国科学院计算技术研究所，北京 100080)
摘 要：非结构化 P2P 网络在大规模网络环境下的资源共享方面具有优越性，针对这些网络的快速资源定位是一个关键问题。Bittorrent
是一个简单、高效的 P2P 文件共享系统，但是该系统只解决了如何高效地下载资源，而没有解决如何高效地搜索资源。该文针对目前
BitTorrent 网络中资源获取方式存在的不足之处，提出了一种基于 BitTorrent P2P 网络的快速搜索策略——Incentive Hop Search，并建立模
拟程序，对检索的性能与效果做了初步的验证。实验结果表明了该方法的有效性。
关键词：对等网络；信息检索；Bittorrent
Fast Search Method Based on Bittorrent Network
DING Lin, CHENG Xueqi, LIU Yue, LV Jianming
(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080)
【Abstract】Unstructured P2P networks are more scalable and more effective than centralized networks. How to locate resource rapidly and
effectively in unstructured P2P networks becomes a key issue. Bittorrent is a simple, effective P2P file sharing system, but it only solves how to
download effectively while how to locate resource is still unsolved. This paper presents a P2P distributed search method(IHS) based on bittorrent
P2P network in order to improve its search ability. It implements a simulation program and tests the performance of the system. Experimental results
show that IHS is an effective method with high recall rate and low resource usage.
【Key words】P2P; Information retrieval; Bittorrent
Bittorrent[1]是当前最流行的 P2P 文件共享系统之一，与其他同类 P2P 文件共享系统相比具有使用简单、性能优越、可扩展性好、容错性强等优点，英国的 Cache Logic 公司的最新研究数据表明：截至 2004 年底，BitTorrent 产生的流量已经占整个 Internet 流量的 30%。然而要想获取 BitTorrent网络内的资源必须要事先找到此资源对应的 torrent 文件。当前，寻找 torrent 文件的方法有 2 种：(1)借助传统 WWW 搜索引擎(如 Google)；(2)人工手动去 BitTorrent 相关的 BBS 上去找。这两种方法费时费力，而且效果不佳。针对这个问题，本文提出了一种快速检索策略(IHS)。
1 相关的研究及背景介绍
1.1 Bittorrent 网络的工作模式
图 1 给出的是一个典型的 BT 网络，同一种花色的网关节点代表同一个物理网络节点。
图 1 一个典型的 BT 网络
利用 Bittorrent 共享文件的过程非常简单：(1)用 Bittorrent客户端打开相应的 torrent 文件，客户端会从 torrent 文件中提取 tracker 地址，并从服务器上获取其它的下载该 torrent 的节点地址列表，这些节点形成一个 swarm；(2)从这些节点上下载资源。
网关节点是指同时下载多个 torrent 的节点(属于多个swarm)。而在目前的 Bittorrent 网络中，swarm 之间是没有联系的，物理上的一个节点被网络在逻辑上分成多个，可以通过这些网关节点把多个 swarm 连接起来。
1.2 Bittorrent 网络存在的问题和相关解决方法
Bittorrent 网络没有提供寻找 torrent 的方法。目前，用户只能通过访问某些论坛或者集中式的搜索引擎来寻找 torrent文件。而这两种方法都有一些不足：在论坛上可以找到最新的 torrent 文件，但是需要人工逐个地搜索论坛，费时费力；利用集中式搜索引擎虽然省时省力，但是因为集中式搜索引擎采集周期长，找到的 torrent 往往已经失效，不能使用。分布式的 P2P 搜索的方法已被许多研究者所研究，P2P 搜索相对集中式的搜索具有可扩展性高、鲁棒性好的特点，并且可以很方便地结合协同工作的方法来提高实时效率。 P2P 的搜索主要分为两大类：(1)非结构化网络，该类网络的组织比较松散，freenet[2]、gnutella、kazaa 都是这类网络的典型代表；(2)结构化网络，该类网络的典型代表是 CAN[3]、Tapestry[4]、Pastry[5]、Chord[6]等，文献[7]等对各类网络的搜索方法做出了总结。 Bittorrent 网络是一种非结构化网络，但其网络特征(平均度数、拓扑结构等)区别于一般的非结构化网络。为此希望在观测 Bittorrent 网络的基础上，改造拓扑，并提出一种适用于该网络的分布式搜索策略，使用户可以方便迅速地搜索网络中 torrent 文件资源。
2 模拟网络的建立
2.1 实验数据的获取
本文通过编写程序获取了 1 229 个 torrent 文件和 torrent文件对应的共享节点组。如果一个 IP 代表一个节点的话，发现一共有 40 310 个节点，其中 6 772 个是网关节点。1 229个 swarm 中只有 60 个没有网关节点。本文可以认为绝大多数的 swarm 是可以通过网关节点连接起来的。逻辑上割裂的多个 Bittorrent 网络在物理上实际上是一个大网络。
2.2 模拟网络的构建策略
如果 A、B 属于一个 swarm 并且 A、B 都是普通节点的话，A 与 B 之间建立连接对查询没有帮助，A、B 拥有同样的 torrent，A 无法在 B 上找到更多的 torrent 资源。只有 A、B 中的 1 个或 2 个都是网关节点的话，建立连接才对查询有帮助。本文采取普通节点与网关节点建立连接，网关节点与网关节点建立连接的策略，具体方法为：利用上文的获取的数据建立网络，对于一个节点 n，对于 n 所属的每个 swarm，找出网关节点集合 G，或者在 n 与 G 中所有的节点之间随机选择一部分节点建立连接。为了避免网络的平均度数过大，对节点 n 所处的每个共享节点集，随机选取 2~5 个节点建立连接，这样就可以构造 4 个网络(网络 2～网络 5)，本文将分别在这 4 个网络上验证路由与检索策略。
2.3 改造后网络的连通性分析
网关节点之间连通性对于整个网络的连通性至关重要。下面本文用染色法来分析网关节点之间的连通性。染色之后最大的色块代表网络中最大的连通图，这张最大的连通图可以覆盖多大范围的网络呢？可以看其中的节点拥有的 torrent数量。对于上文生成的 4 种网络，最大连通图覆盖的 torrent数量和网关节点数量如表 1 所示。其中，torrent 覆盖率＝最大连通图覆盖的 torrent 数量/torrent 总数。可以看出，在网络建立时，每个共享节点集选取的网关节点越多，连通性越高。
表 1 模拟网络连通性
一个 swarm 中 最大连通图覆盖
选择的邻居数 的 torrent 数量torrent 覆盖率
网络 2 2 957 77.87%
网络 3 3 1 046 85.11%
网络 4 4 1 064 86.57%
网络 5 5 1 085 88.28%
对于其他的不在最大连通图中的网关节点该怎么处理呢？可以考虑建立一些固定的代理节点(agent)，来接收这些孤立的网关节点，使整个网络连通起来。
3 Incentive Hop Search 算法
Incentive Hop Search(HIS)的基本原理是：利用属于多个swarm 的网关节点来传递查询消息，从而快速高效地定位资源。如图 2 所示。
3.1 算法流程
(1)发起节点将查询发给网关节点邻居，查询包含关键词、torrent hash 列表(用来记录查询走过的路径)，TTL。 (2)网关节点邻居查看自己所有的 torrent 文件看看有没有满足查询条件，有就给查询发起节点发响应消息，搜索结束。
(3)如果没有满足查询，检查 TTL 是否超时，如果超时就丢弃查询，搜索结束。
(4)如果不超时，TTL 减 1，把自己所有的 torrent 的 hash值加到查询的 torrent hash 列表中，再把网关节点邻居的torrent hash 列表一一与查询中的 torrent hash 列表进行比较，选择那些存储有不同torrent hash的邻居作为下一步的查询转发节点(因为如果查询的 torrent hash 列表完全包含某一邻居的 torrent hash 列表，说明此邻居所在的路径已经被走过了)，然后转发给符合上述条件的网关节点邻居。转(2)。
3.2 性能分析
在网络 2～网络 5 中各随机选取 100 个节点发起查询，记录 torrent 覆盖率和每个网关节点处理的消息数。取平均值可以得到图 3、图 4。
可以看出，网络 5 的 torrent 覆盖率最好，在 TTL 为 30的时候，可以覆盖 81.25%的 torrent 文件。网络 5 在 TTL 为30，在覆盖 81.25%的 torrent 时，每个网关节点平均处理的消息数只有 1.08 个。但是搜索的延迟比较大，这一点将在 3.3节中作改进。
3.3 IHS 的改进
由表 1 可知，模拟网络并不是全连通的(连通性最好的网络 5 的 torrent 覆盖率 88.28%)，有些网关节点不在最大连通图里，有些 swarm 中没有网关节点，新加入网络的节点也没法获取网关列表，需要引入 agent 节点来解决这些问题。
在实验中，建立 100 个 agent 节点。建立网络的过程中，节点加入网络时，先要与某个 agent 建立连接，如果此节点是网关节点，则把自己注册到该 agent 节点列表中。
本文为网络 2～网络 5 引入 agent 后生成网络 II~网络 V。表 2 给出了网络 II~网络 V 的连通性分析，与表 1 相比有所提高。
表 2 加入 agent 后的网络连通性
最大连通图覆盖的 torrent 数量 Torrent 覆盖率
网络 II 1 142 92.92%
网络 III 1 148 93.41%
网络 IV 1 150 93.57%
网络 V 1 151 93.65%
节点发起查询时，除了向它网关邻居发送查询消息外，还将从它连接的 agent 那里获取更多的网关节点列表，并向它们发送查询消息。加入 agent 后的 torrent 覆盖率和平均网关消息数见图 5、图 6。
通过试验可以看出，加入 agent 后，TTL 值大幅减少，意味着查询相应时间大大缩短，TTL=5 的时候搜索接近收敛。综合性能最好的是网络 IV，在 TTL=6 的时候，每个网关节点平均只需要处理 1.3 个消息就可以覆盖 93.5%的torrent。
4 结论
本文提出了如何改造 BitTorrent 网络的方法，并在新网络上建立一个分布式的高资源利用率、低运算复杂度、扩展性好、效果好的资源检索与路由方法。本文主要的贡献包括：
(1)改造 Bittorrent 网络，使之成为物理上、逻辑上都互连互通的完整网络。
(2)利用了 BitTorrent 网络中通过 torrent 定位资源这一特点，提出一套基于 IHS 的分布式检索策略。该方法通过在查询消息中标记经过的 torrent 来降低消息冗余度从而提高系统的性能。
(3)建立点对 BitTorrent 网络的模拟程序，对 IHS 的检索性能进行了验证。
在本文的基础上，进一步的工作包括：
(1)进一步扩大系统的规模，以验证检索系统在超大规模环境下的稳定性。
(2)引入局部内容启发的方法，替代在某一 swarm 中随机选择网关节点作为邻居的方法，进一步减少检索覆盖节点数目，减少消息传播路径。
(3)采用更加丰富的、经验证有效的传统信息检索技术，包括更精炼的索引模型、结果排序、查找优化策略等。
(4)定量评估系统的存储资源消耗和计算复杂度。
(5)实现系统的原型，在真实的分布式环境中得以验证。
参考文献
1 Cohen B. Incentives Build Robustness In Bittorrent[C]//Proceedings
of the 1st Workshop on the Economics of Peer-to-Peer Systems,
Berkeley, CA, 2003.
2 Clarke I, Sanberg O, Wiley B, et al. Freenet: A Distributed
Anonymous Information Storage and Retrieval System[C]//Proc. of
Workshop on Design Issues in Anonymity and Unobservability, 2000.
3 Ratnasamy S, Francis P, Handley M, et al. A Scalable Content-
addressable Network[C]//Proc. of ACM SIGCOMM, 2001-08.
4 Zhao B Y, Huang L, Stribling J, et al. Tapestry: A Resilient
Global-scale Overlay for Service Deployment[J]. IEEE Journal on
Selected Areas in Communications, 2004, 22(1).
5 Rowstron A, Druschel P. Pastry: Scalable, Distributed Object Location
and Routing for Large-scale Peer-to-Peer Systems[C]//Proc. of Int’l.
Conf. on Distributed Systems Platforms, 2001: 135-141.
6 Stoica I, Morris R, Karger D, et al. Chord: A Scalable P2P Lookup
Service for Internet Applications[C]//Proc. of ACM SIGCOMM,
2001-08.
7 Li X, Wu J. Searching Techniques in Peer-to-Peer Networks[M].
Auerbach, 2006: 613-642.
在[url]www.cnki.net[/url]上碰到的。
[[i] 本帖最后由 clumsy 于 2007-3-29 18:41 编辑 [/i]] [url]http://www.cnki.net/[/url]上面还有很多……
登陆名xa0017 密码：zgzfdxs:12
页:
[1]