结构化P2P路由协议Chord的分析和实现

Chord是麻省理工学院(MIT)提出的一种基于DHT技术的结构化P2P路由协议,具有完全分布式、负载均衡、可用性及可扩展性好、命名方式灵活等特点。该文在分析Chord的基础上,使用Java远程方法调用(RMI)技术实现了基本路由协议系统JavaChord,并进行了验证测试。

计 算 机 工 程 第 33 卷 第19期

Vol .33 No.19 Computer Engineering · 网络与通信 ·

文章编号:1000—3428(2007)19—0122—03

文献标识码:A

2007年10月

October 2007

中图分类号:TP393

结构化P2P路由协议Chord的分析和实现

邵 鹰,刘 业

(东南大学计算机科学与工程学院网络与信息集成教育部重点实验室,南京 210096)

摘 要:Chord是麻省理工学院(MIT)提出的一种基于DHT技术的结构化P2P路由协议,具有完全分布式、负载均衡、可用性及可扩展性好、命名方式灵活等特点。该文在分析Chord的基础上,使用Java远程方法调用(RMI)技术实现了基本路由协议系统JavaChord,并进行了验证测试。

关键词:结构化;P2P;Chord;远程方法调用

Analysis and Implementation on Chord of

Structured P2P Routing Protocol

SHAO Ying, LIU Ye

(Key Laboratory of Computer Networks and Information Integration, Ministry of Education, College of Computer Science and Engineering,

Southeast University, Nanjing 210096)

【Abstract】The Chord, a type of structured P2P routing protocol proposed by MIT base on the distributed Hash table(DHT) technology, has theadvantages of entire distribution, balanced load, high scalability & availability, and flexible naming. This paper analyzes the Chord protocol andrealizes the basic routing system JavaChord with the Java remote method invocation(RMI) technology. Tests are done for validation. 【Key words】structurization; P2P; Chord; remote method invocation(RMI)

自1999年以来,对等网络(P2P网络)的研究得到了国内外学术界和商业组织的广泛关注。与传统C/S结构网络相比,P2P网络具有高可扩展性、健壮性、负载均衡等很多优势,逐渐成为研究的热点。

按照节点信息存储和搜索方式的不同,P2P网络拓扑结构分为以下几种:

(1)以Napster为代表的中心索引拓扑:使用特殊节点存储所有资源的索引信息,具有维护简单、发现效率高等优点,但与C/S结构类似,容易发生单点故障。

(2)以Gnutella、FreeNet为代表的非结构化拓扑:采用随机泛洪转发机制,具有很好的容错性,任何节点子集从网络中移除不会对网络本身造成影响,但随着网络规模的扩大,泛洪将造成网络流量的急剧增加,可扩展性差。

(3)结构化拓扑:大多采用了DHT技术,主要思想是每个节点和每个资源都使用相容哈希(consistent Hash)类方法赋予一个全局唯一的ID,把资源ID通过某种算法映射到节点ID以实现资源定位,具有可扩展、可管理的优点,典型代表有Chord[1~2]、CAN[3]、Pastry[4]、Tapstry[5]等。

的前继(predecessor),在n之后的第1个节点称为n的后继(successor),资源存放于其关键字ID的后继。为了路由的需要,节点保存前继和后继信息,并维护一张最多m项的路由表,称之为Finger表,其中,第k项保存ID为(n.id+

结构化P2P路由协议Chord的分析和实现

2k 1)mod2m的后继。图1显示了节点N8的Finger表及其生成方法,同时,标号的点划线表示了在节点N8上使用幂次逼近算法查询资源ID54的过程,其复杂度可以达到O(logN),其中,N是网络中已存在节点总数。

N481 Chord概述

文献[6]把Chord作为P2P路由机制的典型代表进行了介

绍。Chord实现了这样一种操作:给定一个关键字Key,将其映射到某个节点。为此,采用相容哈希为每个节点和关键字产生一个m位的ID,并按照ID大小构成环形拓扑。图1表示了m=6的一个Chord环,它可以容纳26=64个节点。

运行Chord的主机相互连接构成Chord网络,这是一个建立在IP网络之上的覆盖(overlay)网络。每个节点n有2个邻居:以顺时针为正方向排列在n之前的第1个节点称为n ——122

图1 Chord

Chord本身维护了这样一个结构化的覆盖网络,并提供给

基金项目:国家自然科学基金资助项目(60573133)

作者简介:邵 鹰(1981-),男,硕士研究生,主研方向:计算机网络应用;刘 业,博士研究生

收稿日期:2006-10-18 E-mail:yshao@2000@http://www.mianfeiwendang.com

Word文档免费下载Word文档免费下载:结构化P2P路由协议Chord的分析和实现 (共3页,当前第1页)

结构化P2P路由协议Chord的分析和实现相关文档

最新文档

返回顶部