资源描述：
《基于small-world网络的非结构化dht算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、基于small-world网络的非结构化DHT算法*基金项目:国家自然科学基金项目(60003004)周晋+，李衍达(清华大学自动化系北京100084)(zhoujin00@mails.tsinghua.edu.cn)摘要：针对非结构化系统搜索效率过低的问题，提出一种基于聚类分布的DHT算法，基本做法是将一个环状覆盖网络划分为两层，下层负责数据管理，上层负责节点路由，每层在局部节点上以聚类方式组织信息。该算法初步解决了已有非结构化算法的数据组织无序性和搜索盲目性。为了进一步减小搜索路径长度，改进算法利用small-world的研
2、究成果，在HUB层中加入指向远距离节点的远程连接，使得严格聚类转为带有随机性的概率化聚类，从而将搜索路径长度控制在数量级。关键词：Peer-to-Peer；搜索；聚类分布；small-world；DHT中图法分类号：TP393APeer-to-peerDHTAlgorithmBasedonSmall-worldNetworkZHOUJin,LIYan-Da(DepartmentofAutomation,TsinghuaUniversity,Beijing100084)AbstractToaddresstheinefficienc
3、yofexistingunstructuredalgorithms,thepaperpresentsaDHTalgorithmbasedonclusteringdistributionofindices.Thealgorithmdividesaring-likekeyspaceintotwolayers.Thelowerlayerisresponsibleforindicesmanagement,andupperlayerisresponsibleforroutingnodes.Onbothlayers,indicesarecl
4、usteredwithineachpeer.Thealgorithmsolvestheproblemsofpresentunstructuredalgorithmsinacertaindegree,inwhichthedatumisorganizedinaconfusedsituationandroutingisproceedinadisorderedmanner.Further,enhancedalgorithmusesoutcomeofsmall-worldtocutdownlatencyofroutinghops.With
5、enhancedalgorithm,afewconnectionstoremotepeersareintroducedintoroutingtablewithasuitableprobability.Inanotherword,thecriterionofclusteringisnotofdetermination,butofprobability.Thus,itispossibletorouteoverlaywithaveragelatencyofhops.KeywordsPeer-to-Peer,route,clusteri
6、ngdistribution,small-world,DHT1简介近来，Peer-to-peer系统（简称P2P系统）在文件共享和信息搜索等方面得到了越来越多的应用，Morpheus[1]的系统报告指出：截止2001年10月26日，用户数量超过470,000位，共享文件总量约360TeraBytes。P2P系统是由一组地位相等的节点构成，节点间可以直接通讯，无需第三方参与。与C/S结构相比，P2P结构在可扩展性、数据更新性、可靠性和平衡网络负载能力具有明显优势，为互联网的发展提供了新的契机。搜索算法是决定P2P系统性能的首要因素
7、。Napster[2]采用了的集中式的目录服务器机制，目录服务器中集中存放了各个节点的地址信息和所保存数据的信息。这种集中式的目录服务器可以对请求进行快速查找并返回最合适的目的节点。但由于Napster搜索机制不属于纯粹的分布式搜索，它依然面临着单节点瓶颈、时效性差、安全性低等一系列难题。纯粹的分布式搜索算法分为结构化算法和非结构化算法[3]。结构化算法的典型代表包括Tapestry[4]、Pastry[5]、CAN[6]和Chord[7]，它们严格定义了网络连接的拓扑结构，每个文件必须安放到预先规定好的key空间的某个位置上，
8、这样才能保证搜索步数处于数量级。由于结构化算法要求节点承担的责任较高，所以，它更适合运行于企业网。非结构化算法没有规定数据的存储位置，仅是适应性地进行局部索引调整。非结构化算法给予节点充分的自主性，因此得到广泛的应用。典型代表包括Gnutella[8]和Free
