（计算机应用技术专业论文）基于kademlia的p2p网络资源定位模型改进.pdf

湖 北 工 业 大 学 硕 士 学 位 论 文 i 摘 要 近年来，随着计算机网络的发展，网络技术不断涌现出新的技术和发展方向， 从最初的 http，ftp，smtp 等协议到后期的 https，web2.0，云计算；从最 初单纯的 c/s 模式到后来的 p2p 网络模型。intemet 的广泛使用和数据共享技术的 进步，使人们意识到高效利用网络上的数据将是网络向前发展的源动力。 p2p 对等网络是一种自组织网络、 可以为对等计算、 协同工作和搜索引擎等网 络应用提供良好技术支持。p2p 网络中的资源定位算法是研究的一个重点和热点， 而结构化的分布式哈希表算法以其独特的高效和可扩展性强等优势已经被越来越 多的人研究。在这些结构化查询的协议中，kademlia 协议以其稳定性、高效性和 下载速度受到欢迎，很多文件共享系统都是采用 kademlia 协议实现。 本文根据基于分布式散列表的 p2p 网络资源定位方法，将洪泛式查找与 dht 系统相结合，在拓扑形成时充分利用网络访问的区域性和物理网络中节点的邻近 性来降低访问延迟并优化路由选择。构建一种改进的基于 kademlia 的 p2p 网络资 源定位模型 fkademlia，并通过 p2psim 仿真软件进行仿真测试，实验结果表明 fkademlia 继承了 dht 和 kademlia 的优点，在路由选择、查找成功率和平均逻辑 路径长度等方面的性能均优于原 kademlia 模型。 关键词：关键词： 对等网络，分布式哈希表，kademlia，fkademlia，资源定位，洪泛查找 湖 北 工 业 大 学 硕 士 学 位 论 文 ii abstract in reeent years, with the development of the networks, new technologies are emerging and new directions are finding. at the beginning of the internet http,ftp and smtp were used, but now https,web2.0 and cloud computing are coming to us; from the beginning of the clientserver model to the p2p strategy. all those changes make we realize that how to hamess the data in the network adequately and reasonably is the driving force for the network. p2p network (peer to peer) is a self-organizing network, it can provide good technical support for peer to peer computing, collaborative work, search engines and so on. the resource location algorithm is a key research and hot spots in p2p network, while the structured distributed hash table algorithm for its unique high-performance and scalability advantages is studied by more people. in these structured distributed hash table algorithm, kademlia protocol for its stability, efficiency and download speeds is welcome, a lot of file-sharing systems are based on the kademlia protocol. in this paper, according to the p2p network based on distributed hash table (dht), flooding will be combined with the dht system, the physical proximity of nodes in the network will be used to reduce the latency and optimize routing before the formation of the logical topology. an improved fkademlia based on original model is constructed. p2psim is used to simulate the performance of the new protocol and the results show that fkademlia inherits the advantages of dht and kademlia, and it is superior to the original kademlia model in the routing choices, the rate of successfully finding, the average logical path length and other aspects. keywords: peer-to-peer, distributed hash table, kademlia, fkademlia, resource location, flooding 学位论文原创性声明和使用授权说明 原创性声明原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 湖 北 工 业 大 学 硕 士 学 位 论 文 1 第 1 章 引 言 1.1 课题背景和研究意义课题背景和研究意义 自 20 世纪 70 年代以来，对等计算(peer-to-peer 1，简称 p2p)技术就是互联 网研究领域的焦点。与其它计算机网络模型相比，p2p 网络具有分散化、可扩展、 健壮性、高性能等显著特点，使得 p2p 技术以及其实际应用备受关注。由于传统 的 client/server(c/s) 2模式不再能够适应现代互联网发展的需求，服务器无法 负担日益增长的网络用户，而且难于扩展，在这样的背景下 p2p 技术应运而生。 如今，无论我们是否意识到或者是否了解 p2p 技术，但我们每时每刻在互联 网间的活动基本都与 p2p 技术相关。网络 qq 聊天、网络电话 skype 的应用、迅雷 高速下载以及 pplive 网络电视的观看甚至智能移动终端 3都是 p2p 技术的应用， 可以说我们的现在上网的每时每刻都在享受 p2p 技术给我们带来的便利。 那么 p2p 技术究竟到底意味着什么？或许关于 p2p 技术的两种解释 4能够简单的说明这个 问题。 一种解释是，p2p 即 peer-to-peer。而 peer 在词典里的解释是“(地位或能 力等)同等者” 、 “同事”和“伙伴”的意思。那么，p2p 就可以理解为“同伴对同 伴” ，或者称为对等的网络。 另一种解释是，p2p 就是一种思想，是一种能够改变整个互联网的思想。客观 讲，如果只从技术而言，p2p 并没有激发出重大的创新，而更多的改变是人们对因 特网的认识与理解。正是由于此原因，ibm 早就宣称 p2p 不是一个技术概念，而是 一个社会和经济现象 5。 无论是技术还是思想，p2p 技术就是将人们直接联系起来，让人们通过网络直 接进行交流。它使得网络上的联系真正地消除中间环节，变得更容易、更直接。 这听起来似乎是全新的概念，但其实并新鲜。在生活中，我们每天见面，打电话 都是 p2p 的例子。而从电话的发展的历程中我们可以感觉到，p2p 必将在这个互联 网时代有着迅猛的发展，以大网站为中心的 internet 现状将彻底改变、用户重返 “非中心化” ，以最直接的方式把我们的语言影像传递到对方身边。它符合互联网 络的初衷，给了我们一个自主的互联网。 湖 北 工 业 大 学 硕 士 学 位 论 文 2 但是有着“无限美好未来”和“必定成为未来互联网发展趋势”的 p2p 技术 还存在一些问题 6，其中一个热点就是怎么在数以千万计的网络节点中快速、高校 的搜寻到真正需要的资源，这也就是网络路由问题的研究。对于不同的 p2p 链路， 虽然之间可以共享同物理链路，却不能直接控制底层物理链路，当两节点间建立 了物理层的链接以后，这两个节点间就建立了 p2p 链接。链路的不同选择方式和 网络拓扑结构将直接影响 p2p 网络的服务质量以及路由性能，因此，在现有的 internet 基础上构建一个合理、高效、传输延时小的 p2p 拓扑结构具有十分重要 的意义。 1.2 p2p 技术研究现状技术研究现状 1.2.1 peer-to-peer 网络定义 1.2.1 peer-to-peer 网络定义 p2p 是一种对等网络，网络上的计算机之间通过直接交换与共享资源或服务， 对等计算机兼有客户机和服务器的功能。在这样的网络中所有的计算机都是对等 的（称为对等点） ，每个网络上的对等点具有相同的能力与责任，并共同完成任务。 对等点之间通过直接互连实现存储资源、信息资源甚至处理器资源等的全面共享， 完全不需要依赖集中式中央服务器支持，可以有效消除了信息孤岛与资源孤岛。 p2p 的所具有的特点是改变互联网目前以大型网站为中心的状态、返回非中心化， 并把权力交还给对等点 7。 与传统的网络相比，p2p 具有不可比拟的优势。互联网上各种 p2p 应用软件 如雨后春笋般涌现，用户的数量也急剧增加，给互联网带宽带来极大的冲击。同 时，p2p 技术还具有广阔的应用前景，并不断应用到商业领域、军事领域、政府信 息、通讯等领域。根据文献8，p2p 网络根据具体应用不同，可以分为以下五个 类型： 1、提供文件和其它内容共享的 p2p 网络，例如 bittorrent 9、emule10、 napster、gnutella、edonkey 等； 2、发掘 p2p 存储共享能力和对等计算能力，如 popularpower、avaki 等； 3、基于 p2p 方式的服务共享与协同处理的平台，如 jxta 11-13、groove14等； 4、用于网络交流的即时通讯工具，包括 icq、skype 15、uc 等。 5、安全的 p2p 通讯与信息共享，例如 crowds 16、onion routing17、skype 湖 北 工 业 大 学 硕 士 学 位 论 文 3 等。 在 p2p 网络中，由于每个网络节点在功能上是完全平等的，在行为上是完全 自由的，在连接上则是相互干预的，所有网络节点分布式的自由组织成一个整体 网络，因此对等网络能够很大程度上提高网络传输效率，充分利用网络带宽，挖 掘网络中每个节点的潜力。 根据文献18，p2p 网络的技术特点体现在以下六个方面。 1、非中心化：网络中的服务和资源分散在每一个节点上，节点间的服务和信 息传输都直接在节点间进行，无需中间环节或者服务器介入，避免了由可能由服 务器产生的瓶颈。p2p 网络的可健壮性、扩展性等方面的优势正是由 p2p 的非中心 化基本特点而形成的。 2、 可扩展性： 在 p2p 网络中， 当用户不断加入， 虽然系统中服务需求增加了， 但整个系统的资源和服务能力也相应的同步扩充，始终能满足节点的需要。整个 系统是全分布式的，理论上没有瓶颈，其可扩展性几乎是无限的。 3、健壮性：p2p 系统因其自身结构天生就具有高容错、耐攻击等优点。由于 系统提供的服务是由分布在网络中的每个对等节点所提供，部分节点如果遭到破 坏对其它节点的影响很小。 p2p 网络根据自身协议能够在部分节点失效时自适应的 调整拓扑，保证其它节点依然连通。p2p 网络是以自组织的方式连接起来的，节点 能够自由地加入和离开。 4、 高性价比： 关注 p2p 网络的一个重要原因是其性能优势。 随着时代的发展， 个人电脑的计算能力和网络带宽等性能依照摩尔定理高速增长。采用 p2p 网络架 构可有效地利用大量散布于网络中的普通节点，将计算任务和存储资料分布到各 个节点上。利用各节点空闲的计算能力和存储空间，达到任何单个计算机无法匹 配的高性能计算和海量存储的目的。 5、隐私保护：由于 p2p 网络中信息的传输分散于各节点之间而无需通过像中 央服务器一样的集中环节，可以极大程度上降低用户的隐私信息被窃听的可能性。 由于目前解决 internet 隐私问题的主要方式是采用中继转发的方法，将参与通信 的节点隐藏于众多的网络节点之中。而在 p2p 系统中，所有参与者都可以提供中 继转发的功能，从而大大提高了匿名通讯的可靠性和灵活性，能够提供更好的隐 私保护。 6、负载均衡：在 p2p 网络环境下，每个节点既是服务器又是客户端，大大减 湖 北 工 业 大 学 硕 士 学 位 论 文 4 少了传统 c/s 结构的服务器的计算能力和存储能力，同时因资源分布在网络中的 多个节点，能够更好的实现整个网络中的负载均衡。 1.2.2 p2p 网络拓扑结构网络拓扑结构 拓扑（topology）是将各种物体的位置表示成抽象位置。在网络中，拓扑形 象地描述了网络的安排和配置，包括各种节点和节点的相互关系。网络中的计算 机等设备要实现互联，就需要以一定的结构方式进行连接，这种连接方式就叫做 拓扑结构。目前互联网络中广泛使用集中式、层次式等拓扑结构。 互联网是世界上最大的非集中式的互联网络，但是由于技术等一些方面的原 因，在 90 年代所建立起来的大部分网络系统都是集中式的系统、web 应用基本都 是运行在集中式服务器系统上。随着时代的发展，集中式拓扑结构系统越来越不 能满足网络的需要，面临着过量存储负载、单点失效、dos 攻击等一些问题 19。 p2p 系统需要构造一个非集中式的拓扑结构，在系统构造过程中需要解决包 括系统节点的命名、组织节点的加入和离开方式等问题。 根据文献20，按照拓扑结构结构的不同可以将 p2p 系统分为 4 种形式：中 心化拓扑（centralized topology） ；全分布式非结构化拓扑（decentralized unstructured topology） ；全分布式结构化拓扑（decentralized structured topology，也称作 dht 网络）和半分布式拓扑（partially decentralized topology） 。 1、中心化拓扑 中心化拓扑有着发现效率高、维护简单等优点。由于中心化服务器负责资源 的发现，发现算法灵活高效并能够实现复杂查询。中心化拓扑存在的最大的问题 是与传统 c/s 结构类似，单点的失效容易造成系统故障，还会涉及到法律等相关 问题，中心化拓扑第一代 p2p 网络采用的结构模式，从严格意义上来说为非纯粹 意义上的 p2p 网络模型，中心化拓扑的经典案例是 napster 21。 中心化拓扑对等网络模型存在一些制约其大规模发展的缺陷，主要是： (1)随着网络规模不断扩大，中央服务器所需维护和更新的成本急速增加。 (2)中央服务器的失效导致整个网络崩溃，可靠性和安全性较低。 (3)中央服务器存在版权问题上，并不适合大型网络应用。 2、全分布式非结构化拓扑 湖 北 工 业 大 学 硕 士 学 位 论 文 5 全分布非结构化网络采用了随机图的组织方式，节点度数服从 power-law 22 规律，从而能够达到较快发现目的节点的目的，能够很好的面对网络的动态变化， 对于 p2p 网络有一定的实用性。全分布非结构化网络支持模糊查询和多关键字的 复杂查询，一个典型的案例是 gnutella 23。 gnutella 是一个纯粹的 p2p 系统的文件共享系统，它没有采用索引服务器， 而是使用了基于完全随机图的洪泛（flooding）发现和随机转发（random walker） 机制 24。gnutella 通过 ttl25(time to live)的减值来控制搜索消息的传输。 但是，随着网络规模逐渐增加，参与节点的不断增多，通过洪泛查找的方式 将造成网络流量呈级数方式增加，从而迅速吞噬网络带宽，导致网络中部分节点 会因为过载而失效。因此，在早期 gnutella 网络中，存在较为严重的分区，断链 现象。而且由于没有确定拓扑结构的支持，非结构化网络的资源发现的效率无法 保证。 并且由于采用 ttl、 洪泛、 随机漫步或有选择转发算法， 查找的直径不可控， 可扩展性差。 因此非结构化网络面临的两个重要问题是发现的准确性和可扩展性。目前对 此类结构的研究主要集中于复制策略和改进发现算法以提高发现的准确率和性 能。 3、全分布式结构化拓扑 由于非结构化系统中存在的随机搜索造成整个系统的不可扩展性，现阶段研 究的重点就集中在如何构造一个高度结构化的系统来满足系统扩展的需要。最新 的研究成果都是基于分布式哈希表(distributed hash table，简称 dht)的分布式 发现和路由算法。这些基于 dht 的算法可以有效避免类似 napster 的单点服务器 失效问题和 gnutella 那样基于洪泛查找而容易照成网络瘫痪的问题，这些算法通 过分布式散列函数，将关键字唯一映射到网络中的某个节点上，然后通过一定的 路由算法同该节点建立连接。 dht 的基本设计思想是：在 p2p 网络中构造一个足够大的 id 空间，系统中的 所有节点和数据均具有唯一的 id 标志，每个节点和数据的 id 是通过散列函数得 到， 通过散列函数将节点和数据统一， 即 nodeid=hash(node)； dataid=hash(data)。 系统再根据 hash 的结果决定此关键词对应的那条信息由哪个节点负责存储。用户 搜索的时候，用同样的算法计算出每个关键词的 hash 值，再根据 hash 值找到该 关键词对应信息的储存位置，从而能够迅速定位资源的位置。这种方法搜索速度 湖 北 工 业 大 学 硕 士 学 位 论 文 6 相当快，但是关键词出现在文件中的频率不同，导致节点存储信息的在网络上分 布不均。 dht 的路由算法能够自适应节点的动态加入与退出，具有良好的可扩展性和 自组织能力。由于整个拓扑网络采用了确定性拓扑结构，资源的查找变的非常快 捷与准确。 基于 dht 的全分布式结构化拓扑的最经典的案例是 can、 pastry、 chord 和 kademlia。 4、半分布式结构 半分布式结构结合了中心化结构和全分布式非结构化拓扑的优点， 选择带宽、 处理、存储等方面性能较高的节点作为系统中的超级点（supernodes)，各超级节 点组成一个小型网络系统，系统中其他部分节点的信息储存在超级节点当中，叶 子节点的查询请求先转发给超级节点，整个系统中的发现算法仅在超级点之间转 发。半分布式结构可以看做一个层次式结构，超级节点在上层组成了一个高速转 发层，而超级点所维护的一系列普通节点构成若干子层。目前，半分布式结构最 广泛的应用就是迅雷下载工具。 半分布式结构扩展性和网络整体性能都比较好的优点，容易管理，但系统对 于超级点的依赖，容易导致整个网络受到攻击，容错性能也会大大降低。 比较了 4 种结构的综合性能，比较结果如表 1.1 所示。 表 1.1：4 种结构的性能比较 30 中心化拓扑 全分布式非结 构化拓扑 全分布式结构 化拓扑 半分布式拓扑 可扩展性 差 差 好 中 可靠性 差 好 好 中 可维护性 最好 最好 好 中 发现算法效率 最高 中 高 中 1.2.3 p2p 的发展中存在的问题的发展中存在的问题 p2p 技术在最近几年里取得了快速的发展，迅雷、verycd、pplive 等优秀 p2p 软件如雨后春笋一样涌现在互联网中，并逐渐改变着我们对互联网的认识。在众 多 p2p 资源定位技术中最为重要的研究成果应该是基于 small world 理论的非结 构化发现算法和基于 dht 的结构化发现算法。尤其是 dht 及其发现技术为资源的 湖 北 工 业 大 学 硕 士 学 位 论 文 7 组织与查找提供了一种新的方法。 随着 p2p 系统实际应用的快速发展，p2p 发现算法的效率开始受到物理网络 的制约。主要由于实际网络中节点之间存在的较大差异引起。这些差主要体现在 对等点在计算能力、存储空间和网络带宽上。另一方面，网络波动（churn fluctuation of network）的程度，包括节点的加入、退出、失效、并发过程等 严重影响了系统的查找效率。dht 的搜索算法中，can、chord 等模型都是考虑到 网络波动的情况来设计与实现系统。由于每个节点的度数都尽可能保持最小，需 要响应的成员关系变化的维护就可以比较小，从而网络波动造成的影响就容易恢 复。可是每个节点保持少量路由状态所付出的代价是发现算法的高延时，因为节 点每一次查找需要联系多个节点，理想中的网络中是不会出现这种情况的。 同时，无法提供多关键字、复合查询是 dht 算法的另一个缺陷，尽管信息检 索和数据挖掘领域提供了大量成熟的语义查询技术， dht 自身精确关键词映射的特 征阻碍了 dht 在复杂查询方面的应用，只能通过变通实现。 1.3 论文研究的主要内容论文研究的主要内容 本文的研究是基于 dht 原理的结构化 p2p 系统中的代表系统:kademlia， kademlia 是一种典型的结构化 p2p 覆盖网络，在应用层分布式地进行整个 p2p 网 络信息的存储和检索，该协议被应用于 emule 等许多主流 p2p 软件。在 kademlia 网络中，所有信息均以散列表条目的形式进行存储，这些条目被分散存储在网络 的各个节点上，从而以全网方式构成一张巨大的分布式散列表。 但是 kademlia 依靠一致性散列函数在应用层建立逻辑上的拓扑覆盖网络， 这 有利于其定位、查询、数据存储与复制。但是由于它不考虑实际的底层的物理网 络，造成了物理层的拓扑与逻辑覆盖层的拓扑不匹配，这是使得查询延迟增大。 因此我的具体思路是根据基于分布式散列表的 p2p 网络资源定位方法，将洪泛式 查找与 dht 系统相结合，在拓扑形成时充分利用网络访问的区域性和物理网络中 节点的邻近性来降低访问延迟并优化路由选择。构建一种改进的基于 kademlia 的 p2p 网络资源定位模型，新模型能够继承 dht 和 kademlia 的优点，在路由选择、 查找成功率和平均逻辑路径长度等方面的性能均优于原 kademlia 模型。 湖 北 工 业 大 学 硕 士 学 位 论 文 8 第 2 章 基于 dht 的资源定位方法及其相关原理 2.1 分布式哈希表技术概述分布式哈希表技术概述 随着摩尔定律的不断实现，使得目前的个人电脑具有更快的运算速度，更大 的容量以及更好的网络带宽，每台个人电脑都具备一个小型服务器的能力。在这 样硬件技术的保证下，我们可以对 p2p 系统的健壮性和查找效率等方面提出更高 的要求，对于这些需求的拉动和技术的推动，一种分布式哈希表技术（dht）的新 技术在对等网络的应用中孕育而生，并得到了广泛的应用。 2.1.1 hash 函数 2.1.1 hash 函数 hash 函数是一种能够通过某种运算产生统一编码的方法，一般用于对数据加 密。hash 函数的表示方法：h=h(x)，即给定函数 h(x)对于任何大小的数据 x 能够 产生定长的输出 h。一个优秀的 hash 函数 h(x)能够帮助系统快速计算和查找。 hash 函数的一个最重要的特点就是单向性，即通常给定 h，一般很难通过计 算 找 到 x 使 h=h(x) 成 立 。 另 外 不 管 是 弱 冲 突 抵 抗 weak collision resistenee(wcr)，即给定 xy 使 h(x)=h(y)。还是强冲突抵抗 strong collision resistenee(scr)，即找到 xy 使 h(x)=h(y)，在计算上都是不可行。这样就可以 保证使用 hash 函数的应用的安全性。 2.1.2 在在 p2p 网络中网络中 dht 的应用的应用 基于dht分布式hash表进行网络资源定位的方式是一种结构化的资源定位方 法。利用 dht 技术在 p2p 网络节点与被查询资源之间的关系如图 2.1 所示。分布 式 hash 表利用了 hash 函数加速了查找速度和安全性，而且便于管理同时不会占 用太多的网络带宽。 湖 北 工 业 大 学 硕 士 学 位 论 文 9 图 2.1 p2p 网络节点与被查询资源之间的关系 基于 dht 分布式 hash 表技术是与应用无关的技术； 因为 dht 层单独加入在应 用层和下层通信层之间，可以不考虑具体的应用，只利用 dht 层负责上层数据和 下层通信节点之间查询和插入。由 hash 函数散列得出的关键字和原始数据的含义 没有任何关系，关键字如何产生，完全由开发者决定。 dht 作为应用层的接口如图 2.2。 dht 系统基本的操作就是 find(key)。 在 dht 系统中，每一个节点负责存储一个或者一定范围的关键字，系统通过 find(key) 操作返回存储该关键字节点的 nodeid。通过 dht 层的 find(key)操作，可以把应 用层的数据均匀分布在网络的各个节点内，使下层网络不需要中央服务器的控制。 图 2.2 dht 层的操作 基于 dht 分布式 hash 表技术是一个良好的下层共享方法， dht 系统不必为 资源编码成位置信息，这样容易形成统一的命名层，而这个命名层是基于资源内 容的，增加了查询的灵活性。再加上 dht 构成的体系非常均衡，可以提供多种选 择来思考在哪些节点空间存放对象和用哪一条路径寻找存放对象以确保应用层的 安全。dht 的另一个优势是它的基础结构是自组和自治的，不需开发者在开发过程 中去预见额外的操作，由此可以降低维护和管理的代价。 dht 的路由算法能够自适应节点的动态加入与退出，具有良好的可扩展性和 自组织能力。 基于dht的全分布式结构化拓扑的最经典的案例是can、 pastry、 chord 湖 北 工 业 大 学 硕 士 学 位 论 文 10 和 kademlia。 2.2 基于基于 dht 的的 p2p 路由算法路由算法 2.2.1 can 路由模型路由模型 can 简介 can(content addressable networks) 26路由模型的特点在于采用多维的标识 符空间来实现分布式散列算法。 can 将系统中所有节点映射到一个 n 维的笛卡尔空 间中，并为每个节点尽可能均匀的分配一块区域。can 采用的散列函数通过对 (key,value)对中的 key 进行散列运算，得到笛卡尔空间中的一个点，并将 (key,value)对存储在拥有该点所在区域的节点内。can 采用的路由算法相当直接 和简单，知道目标点的坐标后，就将请求传给当前节点四邻中坐标最接近目标点 的节点。can 是一个具有良好可扩展性的系统，给定 n 个节点，系统维数为 d，则 路由路径长度为 o(n 1/d) ，每节点维护的路由表信息和网络规模无关为 o(d)。 can 的路由策略 can 构建了一个 d 维的直角坐标系空间来应用 dht 散列。超矩形划分了 can 的坐标空间，使得 can 坐标空间分成区域(zone)。每个坐标系统中的节点负责维 护一个区域(zone)，而每个节点又由它的区域(zone)边界标识。当一个关键字通 过 dht 映射到直角坐标系上的一点时，坐标系点对应这个区域，将散列后的关键 字存储在负责这个区域的节点里。图 2.3 表示了 2 维0，1*0，l的 can，该 can 系统有 6 个节点。每个 can 节点负责维护它在坐标系中的所有邻居节点的路由表。 如果两个节点的区域共享 d-1 维超平面，则这两个节点被系统认定为邻居。 图 2.3 can 系统中的节点 can 通过在 d 维直角坐标系空间中转发查询消息来执行查询操作，转发操作 是从查询初始化点开始，沿着直角坐标系上最接近直线的路径到达存储关键字的 湖 北 工 业 大 学 硕 士 学 位 论 文 11 节点。当一个节点收到查询请求时，它转发请求到与目标节点在坐标系中最接近 的节点上。图 2.4 表示 can 找寻关键字(0.8，0.9)的路径。 图 2.4 can 路由模型的路由过程 can 系统中，一种多实现技术被用来降低 can 的查询时延。网络中位于多个 坐标空间的对等点同时参与查询的策略用来减少查询时延和增强 can 的健壮性。 在每个坐标空间中每个节点被分配一个不相同的区域。关键字在这些坐标空间被 多次复制，来提高单点失效时整个系统的强壮性。为了转发系统消息，节点会检 验在坐标系中实际存在的邻居节点，并把消息转发到距离本节点最近的邻居节点。 can 网络中新节点的加入和退出 如果一个新节点加入 can 网络，它需要在坐标空间中随机寻找一个节点 p， 再通过节点 p 找到新加入节点。初始化新加入节点的路由表是件很容易的事情， 因为除了 m 节点之外和它相邻的所有节点都在 m 节点的邻居表中。 当一个节点离开 can 系统时， 这个节点把自己负责维护的区域交给它的邻居。 如果离开的节点和邻居节点能合并，则产生一个新的大区域。如果这两个区域不 能合并，那么它的邻居节点就会暂时负责维护这两个区域。 2.2.2 pastry 路由模型路由模型 pastry 简介 pastry 27路由模型是由英国剑桥microsoft研究院和rice大学共同提出的一 种高效的 dht 路由模型。pastry 充分考虑了网络的本地性，比较好的解决了 dht 中普遍存在的物理网络和逻辑网络的拓扑失配的问题。pastry 是基于应用层定义 的邻近性度量，例如 ip 路由跳数、地理距离、往返延时等。pastry 网络采用环形 结构，网络中每个节点都拥有一个 128 位的节点 id，用于标识该节点在标识符环 湖 北 工 业 大 学 硕 士 学 位 论 文 12 中的位置。pastry 维护每个节点的路由信息表，该表的组织基于共享地址前缀的 长度。 pastry 采用 sha-1 31的 hash 算法， 系统中的节点 id 是利用节点的 ip 地址的 sha-1 散列得到一个 m 位节点 id(表示为 nid)； 系统中的关键字 id 同样利用 sha-1 算法，对关键字进行散列，得到一个 m 位的关键字 id(表示为 kid)。nid 和 kid 是 以 2 b为基的数，共有 m 除以 b 个数位，其中 b 是一个配置参数。节点按 id 从小到 大顺序排列在一个逻辑环上， 关键字存储在 nid 与 kid 数值最接近的节点上， 一个 m=8，b=2 的 pastry 系统如图 2.5 所示。 图 2.5 一个简单的 pastry 系统 pastry 节点维护状态表 pastry 节点所维护的状态表有三个，分别是：pastry 的路由表、pastry 的 邻居节点集和 pastry 的叶子节点集。 pastry 的路由表包括 log2 bn(m/b)行，每行包括 2b-1 个表项，在 pastry 的路 由表中，第 n 行与节点 id 的前 n 个数位相同，但是第 n+1 个数位不同，也称为 n 数位前缀相同。路由表中的每项都包含了节点 id，ip 地址等网络信息，系统根据 邻近性度量选择距离本节点临近的节点。 pastry 的邻居节点集包含|m|个在邻近性度量上最接近于本节点的节点，|m| 的值为 2 b或者 22b。 这里的邻近性度量指的是物理上相邻节点， pastry 的邻居节 n0002 n0201 n0322 n1331 n1113 n2120 n2222 n3001 n3033 n3200 m=8 k1320 k1201 k0220 k2120 k3122 2m-1 0 b=2 湖 北 工 业 大 学 硕 士 学 位 论 文 13 点集通常不用于路由查询消息，而是用来维护本地性。 pastry 的叶子节点集包含|l|个节点 id 最接近本节点的节点，也就是逻辑地 址上的相邻节点，其中|l|/2 个节点的 id 大于本节点，|l|/2 个 id 小于本节点， |l|的值为 2 b或者 22b。 图 2.6 所示为一个 m=16，b=2 的 pastry 系统的一个节点所维护的状态表，因 为系统调节参数 b=2，因此节点 id 的基数为 16bits。在 pastry 的路由表中，一 共有 m/b=8 行， 每行 2b-1=3 个表项。 蓝色的区域里的数字当前节点的第 n 个数位， 而白色的空白区域表示没有合适节点的表项为空。 图 2.6 pastry 节点维护状态表 pastry 的查询过程 当一个待查询消息到达某一个系统节点，该节点首先看待查消息是否在该节 点的叶子节点集中，如果是，则查询消息直接被转发到目的节点，也就是叶子节 点集中节点 id 与待查消息节点数值最接近的那个节点，也有可能就是当前节点， 否则进行下一步在路由表中查找与待查消息具有更长相同前缀的表项，如果该表 项不为空，则将查询消息直接转发到该节点，否则进行下一步。如果不存在这样 的节点,当前节点将会从其维护的所有邻居节点集合中选择一个距离该键值最接 近的节点作为转发目标。 pastry 节点的加入与退出 当一个节点需要加入 pastry 时，该节点首先需要初始化状态表，该节点开始 湖 北 工 业 大 学 硕 士 学 位 论 文 14 时知道一个根据邻近性度量接近自己的节点，假设该节点为节点 a，节点 a 可以通 过使用扩展环 ip 组播等机制自动定位，或者由系统管理员通过其它手段获得。新 节点通过运行 sha-1 算法计算自己的 ip 地址的摘要得到节点 id 为 x， 节点 x 向节 点 a 发送 join 消息，pastry 将该消息路由到节点 id 在数值上最接近 x 的节点 z 接收到 join 消息的节点，包括 a、z，以及 a 到 z 路径上所有的节点将发送它们的 状态表给 x，x 检查这些信息，然后节点根据下面的过程初始化状态表：1、由于 a 与 x 在邻近性度量上接近,所以使用 a 的邻居节点集来初始化 x 的邻居节点集；2、 由于 z 的节点 id 与 x 最相近,因此使用 z 的叶子节点集来初始化 x 的叶子节点集； 3、x 将 join 消息经过的第 i 个节点的路由表的第 i 行作为自己路由表的第 i 行， join 消息经过的第 i 个节点与 x 的前 i 个数位相同。 在初始化状态表完毕之后，新节点向其它相关节点通告自己的到来，新节点 向邻居节点集、叶子节点集和路由表中的每个节点发送自己的状态，以更新这些 节点的状态表。 pastry 节点退出包括叶子节点集 l 中的节点退出机制和路由表 r 中的节点退 出机制。叶子节点集 l 中的节点退出机制：本地节点要求当前叶子节点集合 l 中 的 id 最大的节点或 id 最小的节点把它的叶子节点集合 l1 发送过来，如果 l1 中 存在 l 中没有的节点，则从中选择一个替代失效节点。在退出过程中除非|l|/2 个 节点同时失效，否则恢复过程始终是有效的。 路由表 r 中的节点退出机制： 如果失效节点对应的表项为 r d l(第 l 行第 d 列)， 则联系同一行中的 r d l，id 所指向的存活节点并且获取该节点的 r d l表项，如果 l 行中没有存活节点，则从下一行选择一个节点。 2.2.3 chord 路由模型路由模型 chord 简介 基于 dht 的 chord 28路由模型是由麻省理工学院和加州大学伯克利分校共同 设计的一种 p2p 路由协议。chord 路由模型相比其它模型来说更简单，只需要指定 一个对象， chord 就把这个对象通过系统算法映射到相应的节点上。 鉴于这个原因， chord 路由模型是目前被最为广泛研究的 dht 模型。 在基于 chord 协议的应用中，系统节点并不需要知道系统中所有的节点的位 置，只需要保存相关的少数几个节点的路由信息，由于 chord 路由表按照一定规 律分布的，节点可根据自己的路由表与系统中其它节点进行通信。在有 n 个节点 的系统中，假设在稳定的状态下，每个节点只需保留 o(1og2n)个节点的相关信息， 并最多通过 o(1og2n)次消息转发就能够完成查询请求。另外，在系统节点加入或 湖 北 工 业 大 学 硕 士 学 位 论 文 15 者离开时，能够有效保证路由信息与系统的变化保持同步。 chord 路由模型优点十分突出，由于 chord 路由模型采用一致性哈希函数， 系统能够有效的实现负载平衡，所有的节点以同等的概率分担系统负荷，从而可 以避免某些节点负载过大的情况。另外，由于系统中的节点之间完全平等并完成 同样的工作，使得 chord 具有很高的鲁棒性，可以抵御 dos 攻击。chord 路由模型 的最大特点是系统的可扩展性，chord 协议的开销随着系统规模(节点总数 n)的增 加而按照 o(log2n)的比例增加这使得 chord 可以用于大规模的系统。 然而，chord 路由模型在理想的环境下所展现出来的，当在实际网络中应用 的时候，chord 路由模型存在拓扑失配的问题。系统中每次查找只需要 o(log2n) 次逻辑跳数，但是每一逻辑跳可能跨越多个自治域，甚至是多个国家的网络重叠， 网络与物理网络脱节导致实际的寻路时延较大。 chord 路由模型同样采用 sha-1 的 hash 算法，节点的 id 由节点的 ip 地址的 128 位 sha-1 值得出，而关键字也也会通过 sha-1 的哈希散列得到与系统 id 形式 相同的 128 位值。节点按 id 从小到大顺序排列在一个逻辑环上，关键字储存在与 之节点 id 相同的节点上。 一个简单的 chord 路由模型如图 2.7 所示， n 为节点 id， k 为关键之 id。 图 2.7 简单的 chord 路由模型 基于指针表的查找过程 chord 网络拓扑是一个建立在 ip 网络之上的覆盖网络，根据节点哈希散列值 组成一个顺时针的圆环形结构。每个节点 n 有 2 个邻居：以顺时针为正方向排列 在 n 之前的第 1 个节点称为 n 的前继，在 n 之后的第 1 个节点称为 n 的后继，资 湖 北 工 业 大 学 硕 士 学 位 论 文 16 源存放于其关键字的后继。但为了路由和拓扑变化的需要，节点同时也保存前继 和后继信息，并维护一张最多 m 项的路由表(m 是哈希的比特值)，称之为指针表。 图 2.8 描述了 chord 模型基于指针的查询过程，关键字散列后的 id 值为 54， 虽然节点 n54 不在线，但是为了保证系统的稳定，chord 在周围的节点中都储存了 关键之信息，关键字信息被储存在节点 n56 中，整个查找转变为节点 n8 在 chord 系统中查询 n56 的过程。 n8 的指针列表中储存了 n42，因此 chord 的第一次跳转直接跳转到节点 n42， 以此类推，通过三次跳转，节点 n8 很容易的找到了要查询的关键字，整个查找效 率是非常高的。 图 2.8 chord 模型基于指针的查询过程 chord 节点的加入与退出 当一个新节点要加入 chord 是，新节点 n 通过事先知道某个或者某些节点初 始化自己的指针表，也就是说，新节点 n 将要求已知的系统中某节点为它查找指 针表中的各个表项。在其它节点运行探测协议后，新节点 n 将被反映到相关节点 的指针表和后继节点指针中，新节点 n 的第一个后继节点将其维护的小于 n 节点 的 id 的所有 k 交给该节点维护。 当 chord 中某个节点 m 退出/失效时， 所有在指针表中包含该节点的节点将相 应指针指向大于 m 节点 id 的第一个有效节点即节点 m 的后继节点。为了保证节点 m 的退出/失效不影响系统中正在进行的查询过程，每个 chord 节点都维护一张包 括 r 个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它 就用其后继列表中第一个正常节点替换失效节点。 湖 北 工 业 大 学 硕 士 学 位 论 文 17 chord 路由模型的研究方向 由于 chord 路由模型的简单的路由算法和高效的查询策略，chord 协议是目 前被最为广泛研究的基于 dht 的路由算法，针对 chord 路由模型，现今己经提出 了很多的方法，改进的目的都是希望能够提高 chord 的资源查找效率，提高其 p2p 网络的整个路由性能，更大程度的优化网络。由参考文献32可以看到，目前对 于 chord 的改进算法主要有以下三种： g-chord 模型，g-chord 路由算法的核心思想是在 chord 中实现区域自治，并 将分组的概念引入到 chord 中，从而使得非组代表节点的路由表长度和平均路径 长度均得到有效改善。同时，由于