Presentation | 2019-03-08 Detouring Skip Graph: A Structured Overlay Utilizing Detour Routes Takeshi Kaneko, Ryohei Banno, Yusuke Aoki, Kazuyuki Shudo, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Skip Graph, one of the structured overlays, constructs its own structure based on membership vectors assigned to every node, and consequently it provides routing path lengths of $O(log n)$ where $n$ is the total number of nodes. However, there is a problem that most of routing paths are not the shortest paths because each node knows only its local information, rather than the global topology. We proposed Detouring Skip Graph, which shortens the path lengths by means of utilizing detour routes. It does not require construction of extra links and modification of its topology; thereby, we succeeded in shortening them while maintaining the advantages of Skip Graph. Our evaluation experiments confirmed that the average path length was shortened by approximately 20% to 30% compared to Skip Graph. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Skip Graph / Structured overlays / Routing algorithms / Detour routes |
Paper # | SITE2018-86,IA2018-78 |
Date of Issue | 2019-02-28 (SITE, IA) |
Conference Information | |
Committee | IA / SITE / IPSJ-IOT |
---|---|
Conference Date | 2019/3/7(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Grand XIV Naruto |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Internet and Information Ethics Education, etc. |
Chair | Katsuyoshi Iida(Hokkaido Univ.) / Tetsuya Morizumi(Kanagawa Univ.) |
Vice Chair | Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Toru Kondo(Hiroshima Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) / Takushi Otani(Kibi International Univ.) |
Secretary | Rei Atarashi(Tokyo Metropolitan Univ.) / Hiroyuki Osaki(TOYOTA-IT) / Toru Kondo(NEC) / Masaru Ogawa(Tokyo Health Care Univ.) / Takushi Otani(Toyo Eiwa Univ.) |
Assistant | Kenji Ohira(Tokushima Univ.) / Ryohei Banno(Tokyo Inst. of Tech.) / Hisanori Kato(KDDI Research) / Nobuyuki Yoshinaga(Yamaguchi Pref Univ.) / Daisuke Suzuki(Hokuriku Univ.) |
Paper Information | |
Registration To | Technical Committee on Internet Architecture / Technical Committee on Social Implications of Technology and Information Ethics / Special Interest Group on Internet and Operation Technology |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Detouring Skip Graph: A Structured Overlay Utilizing Detour Routes |
Sub Title (in English) | |
Keyword(1) | Skip Graph |
Keyword(2) | Structured overlays |
Keyword(3) | Routing algorithms |
Keyword(4) | Detour routes |
1st Author's Name | Takeshi Kaneko |
1st Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
2nd Author's Name | Ryohei Banno |
2nd Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
3rd Author's Name | Yusuke Aoki |
3rd Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
4th Author's Name | Kazuyuki Shudo |
4th Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
Date | 2019-03-08 |
Paper # | SITE2018-86,IA2018-78 |
Volume (vol) | vol.118 |
Number (no) | SITE-480,IA-481 |
Page | pp.pp.343-350(SITE), pp.343-350(IA), |
#Pages | 8 |
Date of Issue | 2019-02-28 (SITE, IA) |