FRT-Skip Graph: A Skip Graph-Style Structured Overlay based on Flexible Routing Tables

被引：0
作者：
Hojo, Masashi [1 ,3 ]
Banno, Ryohei [1 ,2 ]
Shudo, Kazuyuki [1 ]
机构：
[1] Tokyo Inst Technol, Meguro Ku, Ookayama 2-12-1, Tokyo 1528552, Japan
[2] NTT Corp, NTT Network Innovat Labs, Midori Cho 3-9-11, Musashino, Tokyo 1800012, Japan
[3] NTT DATA Corp, Koto Ku, Toyosu Ctr Bldg,Toyosu 3-3-3, Tokyo 1356033, Japan
来源：
2016 IEEE SYMPOSIUM ON COMPUTERS AND COMMUNICATION (ISCC) | 2016年
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Structured overlays enable a number of nodes to construct a logical network autonomously and search each other. Skip Graph, one of the structured overlays, constructs an overlay network based on Skip List structure and supports range queries for keys. Skip Graph manages routing tables based on random digits; therefore, the deviation of them disturbs effective utilization of the routing table entries and increases path length than the ideal value. We therefore propose FRT-Skip Graph, a novel structured overlay that solves the issues of Skip Graph and provides desirable features not in Skip Graph. FRT-Skip Graph is designed based on Flexible Routing Tables and supports range queries similarly to Skip Graph. Furthermore, it provides features derived from FRT, namely, dynamic routing table size and high extensibility.
引用
收藏
页码：657 / 662
页数：6
相关论文
共 13 条
  • [1] Ando Y., 2014, P IEEE P2P 2014 IEEE, P1
  • [2] Ando Y, 2014, 2014 INTERNATIONAL CONFERENCE ON INFORMATION NETWORKING (ICOIN 2014), P170, DOI 10.1109/ICOIN.2014.6799686
  • [3] Skip Graphs
    Aspnes, James
    Shah, Gauri
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)
  • [4] Hojo M., 2015, P IEEE ISCC 2015 IEE, P309
  • [5] Maymounkov P, 2002, LECT NOTES COMPUT SC, V2429, P53
  • [6] Miyao Takehiro, 2013, 2013 IEEE Symposium on Computers and Communications (ISCC), P000508, DOI 10.1109/ISCC.2013.6754997
  • [7] Miyao T., 2014, P IEEE ISCC 2014 IEE
  • [8] GFRT-Chord: Flexible Structured Overlay Using Node Groups
    Nagao, Hiroya
    Shudo, Kazuyuki
    [J]. 2014 IEEE 11TH INTL CONF ON UBIQUITOUS INTELLIGENCE AND COMPUTING AND 2014 IEEE 11TH INTL CONF ON AUTONOMIC AND TRUSTED COMPUTING AND 2014 IEEE 14TH INTL CONF ON SCALABLE COMPUTING AND COMMUNICATIONS AND ITS ASSOCIATED WORKSHOPS, 2014, : 187 - 195
  • [9] Nagao H, 2011, IEEE INT CONF PEER, P72
  • [10] SKIP LISTS - A PROBABILISTIC ALTERNATIVE TO BALANCED TREES
    PUGH, W
    [J]. COMMUNICATIONS OF THE ACM, 1990, 33 (06) : 668 - 676
12