| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2022-08-05 09:00 Random Walker 単位の非同期処理における Random Early Detection を用いた自律的輻輳制御機構 ○滝沢 駿・金子晋丈（慶大）  IN2022-18 |
|
| 抄録 | （和） | 大規模グラフ解析において, 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 / / / | |
| 文献情報 | 信学技報, vol. 122, no. 146, IN2022-18, pp. 15-20, 2022年8月. | |
| 資料番号 | IN2022-18 | |
| 発行日 | 2022-07-28 (IN) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IN2022-18 |
|
| 研究会情報 | |
| 研究会 | IN CCS |
| 開催期間 | 2022-08-04 - 2022-08-05 |
| 開催地（和） | 北海道大学 百年記念会館 |
| 開催地（英） | Hokkaido University(Centennial Hall) |
| テーマ（和） | ネットワークの科学、将来ネットワーク 、クラウド/SDN/仮想化、コンテンツ配信・流通、及び一般 |
| テーマ（英） | Network Science, Future Network, Cloud/SDN/Virtualization, Contents Delivery/Contents Exchange, and others |
| 講演論文情報の詳細 | |
| 申込み研究会 | IN |
| 会議コード | 2022-08-IN-CCS |
| 本文の言語 | 日本語 |
| タイトル（和） | 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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 滝沢 駿 / Shun Takizawa / タキザワ シュン |
| 第1著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 金子 晋丈 / Kunitake Kaneko / カネコ クニタケ |
| 第2著者 所属（和/英） | 慶應義塾大学 (略称： 慶大) Keio University (略称： Keio Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2022-08-05 09:00:00 |
| 発表時間 | 20分 |
| 申込先研究会 | IN |
| 資料番号 | IN2022-18 |
| 巻番号（vol） | vol.122 |
| 号番号（no） | no.146 |
| ページ範囲 | pp.15-20 |
| ページ数 | 6 |
| 発行日 | 2022-07-28 (IN) |
[研究会発表申込システムのトップページに戻る]