Presentation | 2022-08-05 Autonomous Congestion Control Mechanism Using Random Early Detection in Asynchronous Random Walker Processing Shun Takizawa, Kunitake Kaneko, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In large-scale graph analysis, Random Walk (RW) is useful and has been implemented in both synchronous and asynchronous distributed graph systems. However, when a graph such as a dynamic graph, which is difficult to divide equally, is distributed across multiple servers and RW is executed asynchronously, queuing delays occur in the Random Walker Queue (RQ), which is a queue of Random Walker (RWer) on each server. Therefore, we propose an autonomous RWer congestion control mechanism that executes RW asynchronously and allows each server to adjust the RWer flow rate autonomously. This mechanism applies the queue management algorithm Random Early Detection (RED), which is used in routers, to manage RQ on server while allowing RWer discards. The evaluation results show that the execution time is about 1 second faster and the number of additional RW executions is about 84 % less than the case with tail-drop queue management. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Random Walk / graph analysis / asynchronous processing / distributed processing / Random Early Detection |
Paper # | IN2022-18 |
Date of Issue | 2022-07-28 (IN) |
Conference Information | |
Committee | IN / CCS |
---|---|
Conference Date | 2022/8/4(2days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | Hokkaido University(Centennial Hall) |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
Chair | Kunio Hato(Internet Multifeed) / Megumi Akai(Hokkaido Univ.) |
Vice Chair | Tsutomu Murase(Nagoya Univ.) / Hidehiro Nakano(Tokyo City Univ.) / Masaki Aida(TMU) |
Secretary | Tsutomu Murase(KDDI Research) / Hidehiro Nakano(Nagaoka Univ. of Tech.) / Masaki Aida(NTT) |
Assistant | / Hiroyuki Yasuda(Univ. of Tokyo) / Hiroyasu Ando(Tsukuba Univ.) / Tomoyuki Sasaki(Shonan Inst. of Tech.) / Miki Kobayashi(Rissho Univ.) |
Paper Information | |
Registration To | Technical Committee on Information Networks / Technical Committee on Complex Communication Sciences |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Autonomous Congestion Control Mechanism Using Random Early Detection in Asynchronous Random Walker Processing |
Sub Title (in English) | |
Keyword(1) | Random Walk |
Keyword(2) | graph analysis |
Keyword(3) | asynchronous processing |
Keyword(4) | distributed processing |
Keyword(5) | Random Early Detection |
1st Author's Name | Shun Takizawa |
1st Author's Affiliation | Keio University(Keio Univ.) |
2nd Author's Name | Kunitake Kaneko |
2nd Author's Affiliation | Keio University(Keio Univ.) |
Date | 2022-08-05 |
Paper # | IN2022-18 |
Volume (vol) | vol.122 |
Number (no) | IN-146 |
Page | pp.pp.15-20(IN), |
#Pages | 6 |
Date of Issue | 2022-07-28 (IN) |