| 講演名 | 2022-08-05 Random Walker 単位の非同期処理における Random Early Detection を用いた自律的輻輳制御機構 滝沢 駿(慶大), 金子 晋丈(慶大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 大規模グラフ解析において, Random Walk (RW) は有用であり, 同期型, 非同期型の分散グラフシステムに実装されてきた. しかし, 動的グラフ等の均等分割が困難なグラフを複数のサーバで分散管理し, 非同期に RW を実行しつつ, 実行時間を短縮する場合, 各サーバの Random Walker (RWer) の待ち行列である Random Walker Queue (RQ) のキューイング遅延が課題となる. そこで本研究では, 非同期に RW を実行するとともに, 各サーバが RWer の流量を自律的に調整する機構として, 自律的 RWer 輻輳制御機構を提案する. 本機構は, ルータなどで採用されているキュー管理アルゴリズム Random Early Detection (RED) を適用し, RWer の破棄を許容しながらサーバの RQ を管理する. 評価の結果, キュー管理をテールドロップにした場合と比べ, 実行時間が約 1 秒早くなり, RW の追加実行数が約 84 % 少なくなった. |
| 抄録(英) | 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. |
| キーワード(和) | ランダムウォーク / グラフ解析 / 非同期処理 / 分散処理 / Random Early Detection |
| キーワード(英) | Random Walk / graph analysis / asynchronous processing / distributed processing / Random Early Detection |
| 資料番号 | IN2022-18 |
| 発行日 | 2022-07-28 (IN) |
| 研究会情報 | |
| 研究会 | IN / CCS |
|---|---|
| 開催期間 | 2022/8/4(から2日開催) |
| 開催地（和） | 北海道大学 百年記念会館 |
| 開催地（英） | Hokkaido University(Centennial Hall) |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 赤井 恵(北大) |
| 委員長氏名（英） | Kunio Hato(Internet Multifeed) / Megumi Akai(Hokkaido Univ.) |
| 副委員長氏名（和） | 村瀬 勉(名大) / 中野 秀洋(東京都市大) / 会田 雅樹(都立大) |
| 副委員長氏名（英） | Tsutomu Murase(Nagoya Univ.) / Hidehiro Nakano(Tokyo City Univ.) / Masaki Aida(TMU) |
| 幹事氏名（和） | 城 哲(KDDI総合研究所) / 渡部 康平(長岡技科大) / 秦泉寺 久美(NTT) / 濱田 浩気(NTT) / 宮田 純子(芝浦工大) / 眞田 耕輔(三重大) |
| 幹事氏名（英） | Tetsu Jyo(KDDI Research) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Kumi Jinzenji(NTT) / Koki Hamada(NTT) / Sumiko Miyata(Shibaura Inst. of Tech.) / Kosuke Sanada(Mie Univ.) |
| 幹事補佐氏名（和） | / 安田 裕之(東大) / 安東 弘泰(筑波大) / 佐々木 智志(湘南工科大) / 小林 幹(立正大) |
| 幹事補佐氏名（英） | / Hiroyuki Yasuda(Univ. of Tokyo) / Hiroyasu Ando(Tsukuba Univ.) / Tomoyuki Sasaki(Shonan Inst. of Tech.) / Miki Kobayashi(Rissho Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Complex Communication Sciences |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Random Walker 単位の非同期処理における Random Early Detection を用いた自律的輻輳制御機構 |
| サブタイトル（和） | |
| タイトル（英） | Autonomous Congestion Control Mechanism Using Random Early Detection in Asynchronous Random Walker Processing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ランダムウォーク / Random Walk |
| キーワード(2)（和/英） | グラフ解析 / graph analysis |
| キーワード(3)（和/英） | 非同期処理 / asynchronous processing |
| キーワード(4)（和/英） | 分散処理 / distributed processing |
| キーワード(5)（和/英） | Random Early Detection / Random Early Detection |
| 第 1 著者 氏名（和/英） | 滝沢 駿 / Shun Takizawa |
| 第 1 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 第 2 著者 氏名（和/英） | 金子 晋丈 / Kunitake Kaneko |
| 第 2 著者 所属（和/英） | 慶應義塾大学(略称：慶大) Keio University(略称：Keio Univ.) |
| 発表年月日 | 2022-08-05 |
| 資料番号 | IN2022-18 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | IN-146 |
| ページ範囲 | pp.15-20(IN), |
| ページ数 | 6 |
| 発行日 | 2022-07-28 (IN) |