对等网络中一种新的非集中式查找算法

• 作者: 柏海寰 汪为农 蒋俊杰
• 来源期刊: 上海交通大学学报
• 学科: 工学
• 关键词: 分布式网络 对等网络 查找 路由 非集中式算法
• 年，卷（期）: 2004,（1）
• 所属期刊栏目: 自动化技术、计算机技术
• 页码范围: 75-78
• 页数: 4页
• 分类号: TP393
• 字数: 3740字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-2467.2004.01.018

摘要

提出了一种适用于对等网络环境的非集中式查找算法,它具有可扩展、自组织、高容错等特性,能够自动适应网络中节点的加入、退出和失效.该算法的时间复杂度和空间复杂度均为O(logN).算法的基本思想是:将有限大小的线性空间平均划分为M等份,对每等份的子空间递归划分为M等份,直到每个子空间对应一个点;采用Hash算法将网络中的数据或节点映射为线性空间中的一点,每个节点本地存储一个路由表,其内容为其各个划分层次中的对应点所在位置信息;这样,一个节点可以在不超过O(logN)次转跳的情况下找到目的节点.仿真实验结果表明:当M增大时,算法的查找性能也会提高;当M=16,网络规模为104个节点时,算法的平均查找长度仅是Pastry、Tapestry算法的70%左右.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汪为农	上海交通大学计算机科学与工程系	43	372	12.0	18.0
2	蒋俊杰	上海交通大学计算机科学与工程系	5	28	3.0	5.0
3	柏海寰	上海交通大学计算机科学与工程系	4	16	2.0	4.0