基于DHT的几种P2P算法研究.PDF

基于DHT的几种P2P算法研究 周巍 北京邮电大学电信工程学院，北京(100876) E-mail: lunchboxzw@ 摘 要：P2P 网络相对于CS 模式网络具有去中心化，可扩展性，健壮性，高性能，负载均 衡等优点。本文介绍了4 种基于DHT 的P2P 算法：Chord, Can, Pastry, Tapestry。详细分析 了各算法的组织结构，查找方法，结点插入退出，路由方法及性能，并对它们的算法效率进 行了比较研究。 关键词：P2P, DHT, 路由 中图分类号：TP393 1. 引言 P2P 技术也称对等网络结构(Peer-to-Peer)，是通过系统之间直接交换来共享计算机资 源和服务的一种应用模式。它在很大程度上颠覆了人们对互联网的传统观念，打破了占据主 导地位的客户端服务器(Client/Server)的互联网架构，其最根本的思想就是网络中不存在 中心节点(或中心服务器).每个节点(peer)既可以获取其它节点的资源或服务，同时又是资 源或服务的提供者。一般 P2P 网络中每一个节点的权利和义务都是对等的，包括通讯、服务 和资源消费。 结构化 P2P 用纯分布式的消息路由，目前的主流方法是采用分布式哈希表(DHT)技术。 DHT 各节点并不需要维护整个网络的信息，节点仅存储其临近的后继节点信息，因此较少的 路由信息就可以有效地实现资源定位。该 P2P 网络模式有效减少了资源定位的开销，提高了 P2P网络的可扩展性。 目前基于DHT的代表性的研究项目主要包括麻省理工学院的Chord[1]、 加州大学伯克利分校的 CAN[2] [3] [4] 和 Tapestry 、以及微软研究院的 Pastry 。 2. Chord 2. 1 Chord 原理 Chord 中每个关键字和节点都分别拥有一个 m 比特的标识符。关键字标识符 K 通过哈希 关键字本身得到，而节点标识符N则通过哈希节点的IP地址得到。哈希函数可以选用SHA-1。 所有节点按照其节点标识符从小到大（取模 2m 后）沿着顺时针方向排列在一个逻辑的标识 圆环上（称为 Chord 环）。Chord 的映射规则是：关键字标识为 K 的(K, V)对存储在这样的 节点上，该节点的节点标识等于 K 或者在 Chord环上紧跟在 K 之后，这个节点被称为 K 的后 继节点，表示为 successor(K)。因为标识符采用 m 位二进制数表示，并且从 0 到 2m －1 顺 序排列成一个圆圈，successor(K)就是从 K 开始顺时针方向距离 K 最近的节点。 - 1 - 2.2 Chord 的路由 为了加快查询的速度，Chord 使用扩展的查询算法。为此，每个节点需要维护一个路由 表，称为指针表（finger table）。如果关键字和节点标识符用 m 位二进制位数表示，那么 指针表中最多含有 m 个表项。节点n 的指针表中第 i 项是圆环上标识大于或等于 n+2i-1 的第 一个节点（比较是以 2m i-1 为模进行的）。例如若 s=successor(n+2 ), 1≤i≤m，则称节点 s 为节点 n 的第 i 个指针，记为 n.finger[i]。n.finger[1]就是节点 n 的后继节点。指针表 中每一项既包含相关节点的标识，又包含该节点的 IP 地址（和端口号）。 0 6 图 1 给出了节点 8 的指针表，例如节点 14 是环上紧接在(8+2 ) mod 2 =9 之后的第一