P-Grid覆盖网络的加速收敛构建算法.pdf

华南理工大学学报(自然科学版) JoumalofSouthChina of V01．38№．11 第38卷第11期 UniversityTechnology Science November20lo 20lo年11月 (Natural Edition) P—Grid覆盖网络的加速收敛构建算法木 宋玮赵跃龙 (华南理工大学计算机科学与工程学院，广东广州510006) 摘要：在原P—Grid构建算法的基础上，针对节点无初始数据负载量(I印ore—of-Load)及 从加大路径延长的程度以及推荐成功率两方面提高其收敛速度；同时，提出了以路径为主 导、以数据为主导及具有符合度调整的3种Care．of-had算法，并进行了比较．模拟实验 结果表明：lgnore．of-bad算法能减少原算法交互次数的50％以上，大幅提高了算法的收 敛速度；具有符合度调整的Care-of-kad算法在收敛速度上表现良好，并且对数据索引的 查找成功率在90％左右． 关键词：覆盖网络；P．G蒯构建算法；收敛速度；交互次数；初始数据负载量；查找 失败卒 中图分类号：TP393 结构化P2P覆盖网络按照一定的逻辑拓扑结 构将系统物理层的节点相互连接起来．在覆盖网络 非叶节点并不对应实际的对等节点，各节点最终成 提供的加入、路由、查找、退出等基本功能之上可实 为叶节点．整个树的构建过程不需要中心协调，节点 现不同的应用服务．目前已有的建立在覆盖网络之 随机漫步导致的相遇是树构建的动力，这样一来，树 上的P2P数据存储系统有：使用MIT提出的Chord形成的速度(即收敛性)便是一个关键，它严重影响 覆盖网络建立的开放文件存储环境CFS¨1；使用整个系统的性能．文中重点在两种情况下讨论了P— G州的收敛性，改进了原有算法以加快构建速度，为 Berkeley提出的Tapestry覆盖网络建立的Oce硼一 今后建立在其上的应用系统提供更好的支撑． Store旧o；使用微软亚洲研究院提出的xring覆盖网 络建立的面向较少更新的存储系统BitVault口。以及 1 P．Gdd概述 清华大学提出的采用T0urist路由算法建立的面向 对象的存储系统Gmnary【4J．覆盖网络层是整个P2P1．1 P-Grid数据结构 存储系统运行的基础，其特性影响到整个系统的特 文献[5．6]描述了P一嘶d系统中基于虚拟二叉 性，是系统成功与否的关键． 有哪些信誉好的足球投注网站树的覆盖网络及路由算法．系统中每个对象，包 P．Grid覆盖网络是一个分布式信息管理的P2P 括对等节点和数据对象都拥有一个二进制索引值， 平台，具有完全分散管理、自组织∞西J、基于动态IP 的数据管理(更新)刮、分布式负载平衡归删等特 节点在二叉树中的路径，动态形成于虚拟二叉树的 点．覆盖网的构建基于随机算法和本地交互，面向低 构建过程．每个对等节点根据其路径值对应一个索 在线率的节点环境，该网络既具有虚拟树的结构，能 引值区间；每个对等节点含有两类信息：数据索引信 以树的形式组织资源实现系统的层次化管理，提高 息和路由信息．数据索引信息是存储索引值最大前 资源查找效率，又摆脱了基于树的覆盖网络结构 缀与节点路径值相同的数据对象的索引信息．图l 收稿日期：2009．12．24 }基金项目：教育部博士点基金资助项目(200805610019)；广东工业大学青年基金资助项