论文研究-一种小路由延迟的云对等网络搜索算法.pdf

所需积分/C币:10 2019-07-22 21:12:17 944KB .PDF
5
收藏 收藏
举报

利用分布式哈希表(DHT)技术和简单的随机邻居策略,提出了一种基于云对等网络的资源搜索算法(RCLOUD),解决了以1-c的概率在d跳内完成查询的问题,c 和d均为可设定的常数。该算法的一个主要优势是当节点加入或离开时邻居信息维护开销低。仿真实验结果表明,与经典Chord等P2P算法相比,RCLOUD网络中云节点只有在网络规模N增加一倍(或减半)时才会增加(或减少)其随机邻居的数量,并且不牺牲系统效率。这表明任意邻居的查找与N的大小无关,可以高概率将查询跳数控制在常数跳d以内。
1762 计算机应用研究 第31卷 表1符号说明 seg(x)的范围,则会立刻查询到哪个节点负责存储该DD的信 符号 明 息。另一方面,如果要查询的ⅢD属于随机邻居z的超级区间 云对等网络中云节点的数量 片段,则查询会从节点x转到节点z。 志符的比特位数 r、y、2、1 云对等网络中的任意节点 3.2路由算法 云节点x负责的区间片段 任意被查询的标忐符 当节点x收到一个查询 request(id),它用下面的算法执行 node(id)鱼责标志符为d的云节点 该查询 云节点x的前后连续的邻居集合 云节点x的随机邻居的集合 IClOUd_ Routing (id sup seg t)云节点集S{x}+x所负责的区间片段 1 if id E seg(x)then 迕续邻居的数量 process request and send result to original requester 随机邻居的数量 if彐y←Sx, id e seg(y) 在d或更少跳数内查洵到目标节点的概率 orward the request to y 在d或更少跳数內查洵到目标节点的目标概率 5 else if彐z∈R,id∈ sup_seg(z)then RCLOUD(d,c)以不低于(1--)的概率在d或更少跳数内查询到目标 节点的云对等网络 forward the request to z 本文评估云对等网络的性能基于以下指标 8 forward the request to all random neighbors a)时间复杂度。一个查询( request(id))通过覆盖网拓扑 图2~5中给出了几个路由查询的例子。 达到日标节点( node(id))的最大路由跳数。 0跳情况如果 ide seg(x),则只需0跳即可完成查询 )空间复杂度。一个节点川来存储邻居信息的最大存储空间。如图2 如图2所示,此时算法中第1~2行代码祓执行。 关于负载均衡、安全等问题暂不在本文研充的范围内。 1跳情况如果彐y∈S,id∈seg(y),则只需1跳完成查 3基于随机邻居策略的云对等网络( RCLOUD) 询,如图3所示,此时算法中第3~4行代码被执行 2跳情况如果彐z∈R,id∈ sup seg(x),则只需2跳完成 给定两个常数d和c,目标是建立一个时间和空间复杂度查询,如图4所小,此时算法中的5~6行代码被执行。 分别为0(d)和O(N)的云对等网络。下文将提出实现该系 3跳情况需要3跳或更多跳才能完成査询,如图5所 统的算法和一些分析结果。上述0(N)复杂度的讨论中,暂示,此时算法中的7-8行做执行 吋忽略∫d和这两个因素的影响,这些因素将在卜文系统描 述细节中予以阐述。 亠∠工一 3.1云对等网络拓扑结构 图20跳完成查询的情形 图31跳完成查询的情形 每一个节点都维护一个能直接通信的邻居集。邻居分两 node(id 类:一类是随机邻居,一类是连续邻居,如图1所小,图中的环 ode(id 代表m空间 跳完成查询 2跳完成查询, 此时d属于sup_ sengi) un se g(2)/ 此时id属于 y为z的随机邻居 节点x的随机邻居 2为x的随机邻居 冬42跳完成查询的情形图53跳或吏多跳完成查询的情形 对于前三种情况,节点x确切知道执行查询的下一跳节 节点的连续邻居 点。最后一种情况,节点x不知道下一跳节点,于是它将查询 播至其所有随机邻居。为限制广播开销,在查询报文中引人 个TIL字段,使得查询只能传播d跳或更少跳数,对随机邻 图1随机邻居和节点x的连续邻居 居的广播直到d-2级为止。如图所示,最后两跳不需要广播 随机邻居:一个节点x随机选择一定数量的节点作为其因为节点收到查询请求后已有足够的信息来判断能否超过两 随机邻居,表示为R、 跳來到达node(id),如果能在两跳内到达,则路由至下一节点 连续邻居:一个节点κ选择一定数量的前驱节点和后继节继续执行杳询操作。 点作为连续邻居,表示为S。 下面给出一个基本的分析过程和结果。假设每个节点有 邻居集S,+{x}所负责的区问片段表示为sup_seg(x),s个连续邻居和r个随机邻居。为简化分析,假定每个节点负 叫做节点x的超级区间。 责相等大小的ID空间。下面将显示该假设所得的分析结果与 图1的例子中,节点x有三个随机邻居和四个连续邻居。实验模拟结果相符合。设P4为查询 request(id)在d或更少跳 一个节点需要冇储其邻居的如下信息 内没有到达mde(id)的概率。已证明P的值(d≥2)为 a)对每个迕续邻居y∈S,用两个整数存储邻居的区间片 段,即seg(y)。将这些片段区间记录整合,节点x就控制了它 下面将证明s和r取某一合适的值,一个查询能以一个指 的超级区间片段,即sp_seg(x)。 b)对每一个随机邻居:e,节点x用两个捡数来存储邻定的概率(如1-10)在d或更少跳内找到月标节点。 居z的超级区间片段,即sup_seg(z) 3.3s值与r值的确定 上述信息可从邻居获得。存储信息的空问复杂度与邻居 设一个整数d≥2和一个常数cc(0…1)。可证,如果 的数量相等。当节点x收到一个查询,如该查询I属于sups=r=hN2,则k=(-lnc),则有Pa<c。代入式(1)可得 第6期 李剑锋,等:一种小路由延迟的云对等网络搜索算法 1763 P<(1 4)(N)-1 经典Chod和上述P2P改进算法平均查询跳数与网络规 2) 模的正相关,会随着网络规模的增人平灼查询跳数相应増加, ),代入(2)式可得P1<(“。其无法根据云服务的需求控制平均查询跳数。而木文提出的 对等网络 RCLOUD(d,c)中,云节点只有在网络规模N增加 中:(1-1)是关于q的单调递增函数,且1m(1-1)=倍(或减半)时才会增加(或减少)其随机邻居的数量,并且不 牺牲系统效率。这表明任意邻居的查找与N的大小无关,可 e,e是自然对数。因此可以得到 将杳询跳数以高概率控制在规定的常数跳以内 (-In el 构建一个基于随机邻居的云对等网络 RCLOUD(d,c),使得 每个节点有(-lnc)aN个连续邻居数和相同的随机邻居。假设 ,则 如果d=3,则该网络为 RCLOUD(3,c)。假设每一个请求有一个初始值为d的TIL字 图6算法耷询效率比较 段,可修改上面的路由算法使得最长路由跳数不超过d跳。 5云对等网络 RCLOUD(,c)的复杂度分析 RCLOUD_ Routing _ttl( id I decrease the TTL of the request by one 在云对等网络 RCLOUD(d,c)中,杳询的最大跳数为d跳, 2 if id F seg( x) then 时间复杂度为O(d)。每个节点邻居的数量为r+s=2(-ln process request and send result to original requester se if c)÷N,空间复杂度为0(-1mc)N)。 forward the request message to y else if彐z∈R、,id∈ sup-seg(z),then 6结束语 forward the request message to 木文建立了云对等网络 RCLOUD(d,c),其每个节点的邻 else if TTl of the request 2 then 居由一部分连续邻居和一部分随机邻居组成。 RCLOUD(d,c) forward the request to all random neighbors 解决了以高概率在常数路由跳数内完成查询的问题。该算法 的个主要优势是当节点加入或离开时邻居信息维护开销低。 discard the request 基于上述分析得到如下定理: RCLOUD(d,c)的时间复杂度和空间复杂度分别为0(d)和O 定理1云对等网络 RCLOUD(d,c)在d跳或更少跳数内(-lnc)可Na)。本文对该系统的性能进行了综合分析,仿真 完成查询额概率大于1-c,此时d≥2且c∈(0…1) 实验结果证明了分析的下确性。 4仿真实验 参考文献: [Ⅰ李璞,陈世平,李剑锋.一种基于对等网络的云资源定位算汏[J 用平均査询跳数衡暈算法性能,仿真实验结果很好地匹配 计算机应用研究,2013,30(2):570573 了前面的分析。实验是在 Linux环境下使用PP仿真工貝 [2 RISSON J, MOORS T. Survey of research towards robust peer-to-peer networks: search methods [J. Journal of Computer Networks Peersin完成的,实验共分六组完成,第1组分别模拟具有 2006,50(17):3485-3521 100001001点的 RCLOUD(3,c)云对等网络,分别3] XU Jun, KUMAR A. J Xing-xing., On the fundamental tradeoffs be 设置不同的c值来反复模拟实验。实验结果如表2所小。表 [J. IEEE Joumal on Selected Areas in Communications 中c列的值为目标失败概率,s、r列的值分别是节点连续邻居 200,22(1):151-163 数和随机邻居数;P3列的值为没有在3跳或更少的跳内完成 PLAXTON C G, RAJARAMAN R. RICHA A W. Accessing nearby copies of replicated objects in a distributed environment[ C// Proc of 查询的概率。P3总是比目标失败概率低,附录B中的式(5)已 the 9th Annual ACM Symposium on Parallel Algorithms and Architec tures. New York: ACM Press. 1997: 311-320 证明P的上限。 [5 ROWSTRON A, DRUSCHEL P. PastrY: scalable, distributed object 表2云对等网络 RCLOUD(3,c)的实验模拟结果 location and routing for large-scale pccr-to-pecr systems[ C// Proc of 网络规模 the 18th IFIP/ACM International Conference on Distributed Systems 网络规模 刈终规模 N-1000 N-10000 V-100000 Plalcortus.2001:329-350 [6 ZHAO B Y, KUBIATOWICZ J D, JOSEPH A D. Tapestry: a fault C P, P3 to-lcrant widc-arca application infrastructure[ J]. ACM SIGCOMM l.0e-13 6.9e-2 8 Computer Communication Review, 2002, 32(1): 81 1.0e-2 9.8e-3 [7] STOICA L, MORRIS R, KARGER D, et al. Chord: a scalable peer 1.3 7.6e-4 rence on Applications, Technologics, Architccturcs, and Protocols for Computer Communications. New York ACM Press, 2001: 149-160 1.0e-522 7.2e-648 9.6e-6 1049.7e-6 [8 RAtNASAMY S, FRANCIS P, HANDLEY M, el al. A se(on L.0e-6 l.8e-6 5 8.2e 8.8e-7 tent-addressable network C// Proc of Conference on Applications 1.0e-7 7.4e-8 Technologics, Architccturce, and Protocols for Computcr Communica tions. New york. ACM Press, 2001. 161-172 在第2-6组实验中每组进行5次网络规模不同的实验,[9 MALKHI D, NAOR M, RATAJCZAK D. Viceroy: a scalable and 网络节点数为500、10002000、30004000时,每次实验随机 dynamic emulation of the butterfly [C ]// Proc of the 21 st Annual Symposium on Principles of Distributed Computing. Ncw York: ACM 发起1000次查找,统计五种算法查询的平均路由跳数。其中 Press,2002:183-192 算法RCUD(3,c)中c=1.0e-7,s=r=25;ieM算法中101 KAASHOEK F, KARGER D R.K∞rde: a simple degree-optimal 的层级 level=3。实验结果如图6所示。 hash table[ J]. Peer-to-Peer Syslems ll, 2003, 38(6): 98-107 (下转第1767页 第6期 梁锦叶,等:交换超立方网的无死锁虫洞路由算法 1767 (t,0)(-1,0)(t-2,0)…(2,0)(1,0) Dependable and Secure Computing, 2011, 8(1): 74-88 按照ROTE3可知,当源节点和目的节点都位于+导出15.唐荣旺,杨小帆,朱氧,等一种基于局部拉曲立方体的无死领路 网中时,则会按照(1)(t-1,1)(1-2,1)…(2,1)(1,1)「6 由算法[冂].重庆大学学报,2008,29(4):9599 ANG Nen-chun. Dual-hamiltonian-path-based multicasting on (0,1)通道顺序进行路由。当源节点和目的节点都位于s导 wormhole-routed star graph interconnection networks[ C]//Proc of the 出子网中时,则会按照(s)(s-1)(s-2)…(1)(0,0)通道进行 9h PArallel and Dislrilnuledl Syslems. Washington DC: IF.E. Compul 路由。当源节点位于t-导出子网,目的节点位于s-导出子网 er Society, 2002: 17-2. [7 TSAI C H. Embedding of mcshcs in MObius cubes J. Theoretical 时,按照(t,1)(t-1,1)(t-2,1)…(2,1)(1,1)(0,1)(s)(s-1) Computer Science,2008,401(1-3):181-190 (s-2)…(1)进行路由。当源节点位于s-导出子网,目的节点[8] KEMAL.F. The crossed cube archileelure fur parallel Impul ali 位于t导出了网中时,则会按照(s)(s-1)(s-2)…(1)(0, []. IEEE Trans on Parallel and Distributed System, 1992, 3 (5):513524 0)(t,0)(t-1,0)(t-2,0)…(2,0)(1,0)进行路由。由于算 [9 ZANG Ming-xiang, ZHANG Xiang-xiang, WEN Jia. Wormhole rou- 法输出的任意一条路径都是按照这个顺序使用通道的,因此算 ting optimization algorithm based on virtual channel switching[C]// 法是无死锁的。证毕。 Proc of International Conference on Multimedia Technology. Washing- 因为在任意一个s-导出子网和任意一个t导出子网所组成 ton DC: IEEE Comp ty,2011:3798380 [10 REZAZADEH A, FATHY M, RAHNAVARD G. An enhanced fault- 的网络中不存在死锁,则在整个交换超立方网中也不存在死锁。 loleranl rUling alyorithm for mesh nelwork-1nl-chip[C_// Pro of In- ternational conference on embedded software and systems. Washin 3结束语 ton DC: IEEE Computer Socicty, 2009: 505-510 [11 CONCATTO C, KOLOGESKI A, CARRO L, et aL. Two-levels of ada 本文在虫润路由模型下,对一种新超立方体网络变种一交 tive buffer for virtual channel router in NoCs[ C// Proc of the 19th 换超立方网进行了研究。首先提出导出子网的概念,并证明了 International Conference on VLsI and System-on-Chip. Washington 导出子网与超立方网的同构关系;然后利用虚通道技术和虫洞[12] WANG H, WU Ling. Preconcerted wormhole routing algorithm for 维序路由算法,提岀了一和交换超立方网的无最短路径路由算 mesh structure based on the network on chip[ c]//Proc of Information 法,并证明该路由算法是尢死锁的。 Conference on Intermational management Ir Industrial Enginccring. Washington DC: IEEE Computcr Socicty 参考文献 2012:154-158 I] DALLY W J, SEITZC L. Deadlock- free message routing in multipro-[13]梁锦叶,梁家荣文换超立方体网络的网络嵌入研究[J。计算机 ccssor intcrconncction nctworks[J. IEEE Trans on Computers 工程与科学,2011,33(8):74-78 1987,36(5) [14]王新阳,梁家荣,豆秋丽,交挨超立方体网络的拓扑性质与嵌入 [2] DANIEL H L. An adaptive and fault tolerant wormhole routing strate- 问题研究[J].电子学报,2012,40(4):669673 yy for k-ary ll-tubes[J]. IEEE Trans on Computers, 1991, 40( 1) [15] MA Mei-jie, ZHU Li-ying. The super connectivity of exchanged hy- pere nhes[ J]. Information Processing Letters, 2011, 111(8): 360 [3 BORHANI A H, MOVACHAR A, COLE R C. A new deterministic 364 fault tolerant wormhole routing strategy for k-ary 2-cubes[ C]// Proc [16] LI Xiang-jun, XU Jun-ming. Generalized measures of fault tolerance of iEEE Intemational Conference on Computational Intelligence and in exchanged hypercubes[ J. Information Processing Letters Computer Research Conference. Washington DC: IEEE Computer So 2013,113(14-16):533-537. city,2010:17. [17] LOH P KK, HSU WJ, PAN Yi. The exchanged hypercube[ J] [4 XIANG Dong. Deadlock-free adaptive routing in meshes with fault- IEEE Trans on Parallel and Distributed System, 2005, 16(9) Tolerance abilily based on charnel overlapping[ J]. IEEE Trans on 866874 (上接第1763页) cloud: research problems in data center networks[ J]. ACM SIG [11 MANKU G S. Rouliny nel works for dislriluled hash Iables[C/ COMM Computer Communication Review, 2009, 39(1): 68-73 Proe of the 22nd Annual Symposium on Principles of Distributed Con [191 ABBES H. CERIN C, JEMNI M. A decentralized and fault-tolerant puting. New York: ACM Press, 2003: 133-142 desktop grid system for distributed applications[ J]. Concurrency 12] JIANG JurI-jie, PAN Ru(-yu, L. ANG Chang-yony el al. BiChord and Computation Practice and Experience, 2010, 22(3): 261 an improved approach for lookup routing in chord C]// proc of the 9th East European Conference on Advances in Databases and Informa- L 20 PANZIERI F, BADAOGLU 0, FERRETTIS, et al. Distributed com lion Syslems. 2005: 338-348 puting in the 21 st century some aspects of cloud computing J].De- 13] WANG Yu-feng, LI Xiang-ming, JI\ Qun, et al. AB-Chord: an effi bendable and Historic Computing, 2011, 6875(8): 393-412 cient approach for resource location in structured P2P networks[ C1// 211 VALANCIUS V, LAOUTARIS N, MASSOULIEL, ct al. Greening the internet with nano datacenters[C]// Proc of the 5th International Proe of the 9th International Conference on Ubiquitous Intelligence Networking Experiments Computing and 9th International Conference on Autonomic Trusted New York: ACM Press. 2009:37-48 14)邓业平,社欢基于物理扑分组的Chm1法:1计算x在121,MM, espn anu lm 与设计,2012,33(10):3734-3738 Applied Compiling. New York: ACM Pr 15] WANG Bin, SHEN Qing-guo. Tidc: an cffcctivc and practical dcsign 2012:412417 for hierarchical-structured P2P model[ J]. Computer Communica 23] JELASITY M, MONTRESOR A, BABAOGLU O. T-man: gossip tons,201235(13):1601-1612 based fast overlay topology construction[. ] Computer Networks [16]李园,陈世平.基于层次划分的RP2P路由算法[冂].计算机应用, The International Journal of Computer and Telecommunication 2009,29(3):646618 Networking,2009,53(13):2321-239 [I]NAMB, SUSSMAN A. Analyzing design choices for distrihuted mul-[24]吴吉义基于DHT的开放对等云存储服务系统研究[D].杭州 bidimensional indexing[J]. The Journal of Supercomputing 浙江大学,2011 2012,59(3):1552-1576 [25]张启飞,张尉东,李文娟,等.基于对等网络的面向小文件的云有 [18 GREENBERG A, HAMILTON J, MALTZ D A, et aL. The cost of a 储系统[冂.浙江大学学报:工学版,2013,49(1):8-14.

...展开详情
试读 5P 论文研究-一种小路由延迟的云对等网络搜索算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841848 你的留言是对我莫大的支持
2019-07-22
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
    最新推荐
    论文研究-一种小路由延迟的云对等网络搜索算法.pdf 10积分/C币 立即下载
    1/5
    论文研究-一种小路由延迟的云对等网络搜索算法.pdf第1页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >