| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-09-09 14:55 学習型インデックスの高速化とパケット転送への適用 ○樋口俊介・武政淳二・小泉佑揮（阪大）・田上敦士（KDDI総合研究所）・長谷川 亨（阪大）  NS2021-65 |
|
| 抄録 | （和） | 学習型インデックスは、キー・バリュー型データベースにおけるキーと対応するエントリの格納位置の関係を回帰モデルで再現するインデックス用のデータ構造である。筆者らは、学習型インデックスをIP のForwarding Information Base (FIB) に適用した学習型FIB を実現した。学習型FIB は、回帰モデルを用いて、入力IP アドレスに対応するFIB エントリの格納位置を予測し、回帰モデルの予測の誤差を補正するためにその予測位置の周辺を探索する2 つの工程から構成される。本稿では、これまでの実装を用いて計算時間を分析し、周辺探索の処理が検索時間の72%を占めることを明らかにした。さらに、周辺探索処理の時間が長い要因を調査し、分岐予測のミスが計算時間増加の要因の1つであることを明らかにした。さらに、学習型インデックスの高速化のため、分岐のない高速な学習型インデックスの実装法を設計した。高速化した実装を用いた評価の結果、以前の実装よりも周辺探索処理の時間が約1.5 倍高速化した。 |
| （英） | An emerging data structure, a learned index structure, which uses machine learning to associate key-position pairs in a key-value store. The authors have applied learned index structures to an forwarding information base (FIB) of IP, which is referred to as a learned FIB, in the previous work. The learned FIB consists of the following two phases: First, it predicts the position of the FIB entry corresponding to an input IP address by leveraging a machine learning regression model. Second, it searches around the predicted position for the FIB entry to correct errors caused by the regression model. In the present study, we reveal that the second phase accounts for 72 percent of the entire computation time, and one of significant causes of the long computation time is pipeline stalls due to branch misprediction. On the basis of the analysis, we design and implement the learned FIB without any loops and branches. The new implementation realizes approximately 1.5 times faster than our previous implementation. | |
| キーワード | （和） | Forwarding information base / パケット転送 / 最長一致検索 / Learned index / 学習型インデックス / / / |
| （英） | Forwarding information base / Forwarding / Longest prefix matching / Learned index / / / / | |
| 文献情報 | 信学技報, vol. 121, no. 170, NS2021-65, pp. 48-53, 2021年9月. | |
| 資料番号 | NS2021-65 | |
| 発行日 | 2021-09-02 (NS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2021-65 |
|
| 研究会情報 | |
| 研究会 | IN NS CS NV |
| 開催期間 | 2021-09-09 - 2021-09-10 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | セッション管理(SIP・IMS)，相互接続技術/標準化，次世代・新世代・将来ネットワーク，クラウド/データセンタネットワーク，SDN(OpenFlow等)・NFV，IPv6，機械学習のネットワーク適用，一般 |
| テーマ（英） | Session management (SIP/IMS), Interoperability/Standardization, NGN/NwGN/Future networks, Cloud/Data center networks, SDN (OpenFlow, etc.)/NFV, IPv6, Machine learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2021-09-IN-NS-CS-NV |
| 本文の言語 | 日本語 |
| タイトル（和） | 学習型インデックスの高速化とパケット転送への適用 |
| サブタイトル（和） | |
| タイトル（英） | Acceleration of learned index structures: A case for IP packet forwarding |
| サブタイトル（英） | |
| キーワード(1)（和/英） | Forwarding information base / Forwarding information base |
| キーワード(2)（和/英） | パケット転送 / Forwarding |
| キーワード(3)（和/英） | 最長一致検索 / Longest prefix matching |
| キーワード(4)（和/英） | Learned index / Learned index |
| キーワード(5)（和/英） | 学習型インデックス / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 樋口 俊介 / Shunsuke Higuchi / ヒグチ シュンスケ |
| 第1著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 武政 淳二 / Junji Takemasa / タケマサ ジュンジ |
| 第2著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 小泉 佑揮 / Yuki Koizumi / コイズミ ユウキ |
| 第3著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 田上 敦士 / Atushi Tagami / タガミ アツシ |
| 第4著者 所属（和/英） | 株式会社KDDI総合研究所 (略称： KDDI総合研究所) KDDI Research, Inc. (略称： KDDI Research) |
| 第5著者 氏名（和/英/ヨミ） | 長谷川 亨 / Toru Hasegawa / ハセガワ トオル |
| 第5著者 所属（和/英） | 大阪大学 (略称： 阪大) Osaka University (略称： Osaka Univ.) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-09-09 14:55:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NS |
| 資料番号 | NS2021-65 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.170 |
| ページ範囲 | pp.48-53 |
| ページ数 | 6 |
| 発行日 | 2021-09-02 (NS) |
[研究会発表申込システムのトップページに戻る]