微信服务号

微信订阅号

2025年6月6日 2:25 星期五
首页 > 过刊浏览>2007年第18卷第11期 >2851-2862
PDF HTML阅读 XML下载 导出引用 引用提醒
一种支持多维资源描述的高效P2P路由算法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60403027, 60773191 (国家自然科学基金); the Natural Science Foundation of Hubei Province of China under Grant No.2005ABA258 (湖北省自然科学基金); the Open Foundation of State Key Laboratory of Software Engineering of China under Grant No.SKLSE05-07 (软件工程国家重点实验室开放基金)


An Efficient P2P Routing Algorithm Supporting Multi-Dimensional Resource Description
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [21]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    在分析现有P2P(peer to peer)路由算法的基础上,提出了一种基于二阶矩定位、支持多维资源数据描述的高效资源路由算法--FAN(flabellate addressable network)路由算法.FAN算法将节点映射到统一的多维笛卡尔空间,并以节点相对空间原点的二阶矩作为子空间管理和资源搜索的依据.FAN路由算法具有O(log(N/k))的高路由效率,在节点加入和退出FAN网络时,更新路由信息的代价为O(klog(N/k)).实验结果表明,FAN路由算法具有路由效率高、维护代价小的优点,是一种P2P环境中支持多维资源数据描述的高效结构化资源路由算法.而且,目前部分基于CAN(content-addressable network)网络的改进算法也可以在FAN网络中适用,并获得更好的路由效率和更低的维护代价.

    Abstract:

    Analyzing the existing P2P(peer to peer)routing algorithms,Flabellate Addressable Network(FAN) routing algorithm,an efficient second-moment-based resource routing algorithm supporting multi-dimensional resource description is proposed.Peers are mapped into a multi-dimensional Cartesian space with FAN routing algorithm that manages the subspaces and searches resources based on the peers'second-moment.The routing efficiency of FAN algorithm is up to O(log(N/k)).When a peer joins and leaves the FAN network,the cost for updating routing messages is O(klog(N/k)).The experimental results show that FAN routing algorithm has advantages of high efficiency of routing and low cost of network maintenance,and is an efficient structured P2P resource routing algorithm supporting multi-dimensional resource description.Some improved routing algorithms based on CAN(content-addressable network)can also be implemented in FAN network,and they can obtain better routing efficiency and lower maintenance cost.

    参考文献
    [1]Sylvia R,Paul F,Mark H,Richard K,Scott S.A scalable content-addressable network.In:Cruz R,Varghese G,eds.Proc.of the ACM SIGCOMM 2001.New York:ACM Press,2001.161-172.
    [2]Napster.http://www.napster.com
    [3]Gnutella.http://www.gnutella.com
    [4]Yang B,Hector GM.Improving search in peer-to-peer networks.In:Rodrigues LET,Raynal M,Chen WSE,eds.Proc.of the 22nd IEEE Int'l Conf.on Distributed Computing Systems (ICDCS 2002).Washington:IEEE Computer Society,2002.5-14.
    [5]Stoica I,Morris R,Karger D,Kaashoek MF,Balakrishnan H.Chord:A scalable peer-to-peer lookup service for Internet applications.In:Govindan,ed.Proc.of the ACM SIGCOMM 2001.New York:ACM Press,2001.149-160.
    [6]Zhao BY,Huang L,Jeremy S,Sean CR,Anthony DJ.Tapestry:A resilient global-scale overlay for service deployment.IEEE Journal on Selected Areas in Communications,2004,22(1):41-52.
    [7]Karger D,Lehman E,Leighton T,Levine M,Lewin D,Panigrahy R.Consistent hashing and random trees:Distributed caching protocols for relieving hot spots on the World Wide Web.In:Proc.of the 29th Annual ACM Symp.on Theory of Computing.New York:ACM Press,1997.654-663.
    [8]He YJ,Wang S,Du XY.Efficient top-k query processing in pure peer-to-peer network.Journal of Software,2005,16(4):540-552 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/16/540.htm
    [9]Liu B,Lee WC,Lee DL.Supporting complex multi-dimensional queries in P2P systems.In:Proc.of the 15th IEEE Int'l Conf.on Distributed Computing Systems (ICDCS).New York:IEEE Computer Society,2005.155-164.
    [10]Norbert B,Hans-Peter K,Ralf S,Bernhard S.The R*-tree:A efficient and robust access method for points and rectangles.In:Hector GM,Jagadish HV,eds.Proc.of the 1990 ACM SIGMOD Int'l Conf.on Management of Data.New York:ACM Press,1990.322-331.
    [11]Ashwin RB,Mukesh A,Srinivasan S.Mercury:Supporting scalable multi-attribute range queries.Computer Communication Review,2004,34(4):353-366.
    [12]Shu YF,Beng CO,Kian-Lee T,Zhou AY.Supporting multi-dimensional range queries in peer-to-peer systems.In:Germano C,Nathalie W,Marcel W,Nahid S,eds.Proc.of the 5th IEEE Int'l Conf.on Peer-to-Peer Computing (P2P).New York:IEEE Computer Society,2005.173-180.
    [13]James A,Gauri S.Skip graphs.In:Proc.of the 14th Annual ACM-SIAM Symp.on Discrete Algorithms.Philadelphia:Society for Industrial and Applied Mathematics,2003.384-393.http://www.ic.unicamp.br/～celio/peer2peer/skip-net-graph/skip-graph-aspnes.pdf
    [14]Li DS,Lu XC,Wang BS,Su JS,Cao JN,Keith CCC,Hong VL.Delay-Bounded range queries in DHT-based peer-to-peer systems.In:Proc.of the 26th IEEE Int'l Conf.on Distributed Computing Systems (ICDCS).New York:IEEE Computer Society,2006.
    [15]Li DS,Lu XC,Wu J.FISSIONE:A scalable constant degree and low congestion DHT scheme based on Kautz graphs.In:Proc.of the 24th Annual Joint Conf.of the IEEE Computer and Communications Societies (INFOCOM).New York:IEEE Press,2005.1677-1688.
    [16]Li M,Lee WC,Anand S.Semantic small world:An overlay network for peer-to-peer search.In:Proc.of the 12th IEEE Int'l Conf.on Network Protocols (ICNP 2004).New York:IEEE Computer Society,2004.228-238.
    [17]Lakshmish R,Bugra G,Liu L.A distributed approach to node clustering in decentralized peer-to-peer networks.IEEE Trans.on Parallel and Distributed Systems,2005,16(9):814-829.
    [18]Tang CQ,Xu ZC,Mallik M.pSearch:Information retrieval in structured overlays,ACM SIGCOMM Computer Communications Review,2003,33(1):89-94.
    [19]Artur A,Xu ZC.Scalable,efficient range queries for grid information services.In:Ross LG,Nahid S,eds.Proc.of the 2nd Int'l Conf.on peer-to-peer Computing (P2P 2002).New York:IEEE Computer Society,2002.33-40.
    [20]Murat D,Hakan F.Peer-to-Peer spatial queries in sensor networks.In:Nahid S,Ross LG,Germano C,eds.Proc.of the 3rd IEEE Int'l Conf.on Peer-to-Peer Computing (P2P 2003).New York:IEEE Computer Society,2003.32-39.
    [8]何盈捷,王珊,杜小勇.纯Peer-to-Peer环境下有效的Top-k查询.软件学报,2005,16(4):540-552.http://www.jos.org.cn/1000-9825/ 16/540.htm
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

宋伟,李瑞轩,卢正鼎,於光灿.一种支持多维资源描述的高效P2P路由算法.软件学报,2007,18(11):2851-2862

复制
分享
文章指标
  • 点击次数:4125
  • 下载次数: 5844
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2006-02-13
  • 最后修改日期:2006-11-03
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19999945位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号