| Presentation | 2018-09-04 Reducing Average Path Lengths of Range Queries on Skip Graphs Ryohei Banno, Kazuyuki Shudo, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Structured overlay networks are useful techniques to enable a large number of nodes to discover each other in an autonomous manner. Skip Graph is one of the algorithms of structured overlay networks, which has the capability of range queries. Although there are some existing methods for routing range queries, they have problems of long path length or a large number of messages. In this paper, we propose a novel routing method for range queries in Skip Graph. In the proposed method, each node which receives a range query divides its target range into subranges by the keys of its neighbor nodes, and delegates the subranges to the nodes. The proposed method enables to deliver a range query to all nodes within its target range with a shorter average path length and the minimum number of messages. By simulation experiments, we confirmed that our method can reduce the average path length roughly 30% or more compared to an existing method. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Skip Graph / Overlay networks / Peer-to-peer networks / Routing algorithms / Range queries |
| Paper # | IA2018-27 |
| Date of Issue | 2018-08-27 (IA) |
| Conference Information | |
| Committee | IA |
|---|---|
| Conference Date | 2018/9/3(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Hokkaido Univ. Conference Hall |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Internet Operation and Management, etc. |
| Chair | Katsuyoshi Iida(Hokkaido Univ.) |
| Vice Chair | Rei Atarashi(IIJ) / Hiroyuki Osaki(Kwansei Gakuin Univ.) / Toru Kondo(Hiroshima Univ.) |
| Secretary | Rei Atarashi(Tokyo Metropolitan Univ.) / Hiroyuki Osaki(TOYOTA-IT) / Toru Kondo(NEC) |
| Assistant | Kenji Ohira(Tokushima Univ.) / Ryohei Banno(Tokyo Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Internet Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Reducing Average Path Lengths of Range Queries on Skip Graphs |
| Sub Title (in English) | |
| Keyword(1) | Skip Graph |
| Keyword(2) | Overlay networks |
| Keyword(3) | Peer-to-peer networks |
| Keyword(4) | Routing algorithms |
| Keyword(5) | Range queries |
| 1st Author's Name | Ryohei Banno |
| 1st Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
| 2nd Author's Name | Kazuyuki Shudo |
| 2nd Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
| Date | 2018-09-04 |
| Paper # | IA2018-27 |
| Volume (vol) | vol.118 |
| Number (no) | IA-204 |
| Page | pp.pp.69-76(IA), |
| #Pages | 8 |
| Date of Issue | 2018-08-27 (IA) |