お知らせ 研究会の開催と会場に参加される皆様へのお願い(2022年6月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [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 Print edition: ISSN 0913-5685  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著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者 第1著者 
発表日時 2021-09-09 14:55:00 
発表時間 25分 
申込先研究会 NS 
資料番号 NS2021-65 
巻番号(vol) vol.121 
号番号(no) no.170 
ページ範囲 pp.48-53 
ページ数
発行日 2021-09-02 (NS) 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会