学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structures

検索の高速化に関する数多くの研究がなされてきた[1, 2, 3, 4]。
一方で、データベース分野において、学習型インデックス (learned index structure) と呼ばれる、機械学習に基づく新たなデータ構造が提案された[5]。

学習型インデックスは、キー・バリュー型データベース (KVS: key-value store) において、キーとそれに小泉 佑揮 (Yuki Koizumi, Ph. D.)

対応するエントリの格納位置の関係を機械学習で再現

大阪大学 大学院情報科学研究科 准教授するインデックス用のデータ構造である。与えられた(Associate Professor, Graduate School of Information Scienceand Technology, Osaka University)

キーに対して、対応エントリの格納位置を機械学習で予測し、予測された位置の周辺を局所的に探索するこACM IEEE 電子情報通信学会
研究専門分野：情報ネットワーク ネットワークセキュリティとでエントリを発見する。学習型インデックスは、コンパクト性と高速性を両立するデータ構造として期待されている。
本研究は、学習型インデックスの提唱をふまえて、あらましパケット転送に関するデータ構造とアルゴリズムに関パケット転送は、宛先情報を有するテーブル (FIB:する研究に再訪し、学習型インデックスの FIB への適Forwarding Information Base) から、パケットごとに用を目指す。学習型インデックスを用いた FIB を学習宛先を検索する処理であり、ルーターの重要な役割の型 FIB と呼ぶ。このとき、学習型 FIB を実現する上で、一つである。一方で、最近、データベース分野で、学機械学習によるエントリ格納位置の予測に要する時間習型インデックスと呼ばれる機械学習に基づく新たなと、機械学習によるエントリ格納位置の予測誤差を訂データ構造が提唱され、そのコンパクトさと検索の高正するための局所探索に要する時間の削減が課題とな速性から様々な応用が期待されている。しかし、学習る。これに対して、ニューラルネットワークをベース型インデックスを FIB 検索に用いるためには、さらなとする回帰は、区分線形関数による回帰に帰着する点

る高速化に加えて機械学習に起因する検索速度のばらに着目し、最悪時の予測誤差を保証し誤差保証のためつきを抑制する必要がある。本研究では、学習型インの局所探索アルゴリズムを最適化する。これにより、デックスの本質が区分線形関数による回帰であること

既存の FIB 用のデータ構造よりもコンパクトでありなに着目して学習型インデックスを FIB に最適化する

がら、同程度の検索速度を実現する。さらに、宛先のことで、FIB 用に提唱された最新のデータ構造と同等プレフィクス長に依存せずに一定時間での FIB 検索をの検索速度を達成し、かつアドレスのプレフィクス長実現する。に依存しない一定の検索速度を実現する。
２．研究の背景１．研究の目的IP パケット転送は、受信パケットの宛先 IP アドレ

IP (Internet protocol) におけるパケット転送は、スをキーとして、FIB からパケットの転送情報が格納各ルーターが、受信したパケットについて、FIB と呼されたエントリを検索する処理である。FIB 上のエンばれるテーブルに格納されたパケットの転送情報を検トリは、Classless Inter-Domain Routing (CIDR)を前索し、パケットの宛先を決定し、決定した宛先情報に提として、集約されている [6] ため、FIB の検索にはしたがってパケットを転送する処理である。FIB の検最長一致検索が用いられる。つまり、ルーターは、パ索処理は、パケット転送の根幹をなす技術であり、そケットを受信するごとに、宛先 IP アドレスと最も長の高速化がルーターの高速化に直結することから、FIB

く一致する IP プレフィクスをキーとするエントリを
1

TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structures

FIB から探索し、パケットの宛先を決定する。最長一本研究では、前述の通り、学習型インデックスを FIB

致検索の処理は、単純な厳密一致検索処理よりも複雑に応用し、既存の FIB 用のデータ構造よりもコンパクであることから、この処理の高速化がパケット転送のトながら、同程度の高速な検索を実現することである。

高速化の鍵であり、最長一致検索を高速およびコンパ

このためには、機械学習によるエントリ格納位置の予クトに実現する FIB のデータ構造や検索アルゴリズム測に要する時間と、機械学習によるエントリ格納位置に関する研究 [1, 2, 3]、あるいは、最長一致検索をの予測誤差を訂正するための局所探索に要する時間のサポートするハードウェア技術を応用する研究 [4]削減が課題となる。これらの課題に対して、Rashelbachがなされた。

ら [7] は、高速な学習型 FIB の計算に向けて、ニューFIB のデータ構造や検索アルゴリズムに注目すると、ラルネットワークの計算の最適化、計算機のニューラ

高速な検索を実現する FIB のデータ構造を実現するた

ルネットワーク計算最適化技術の利用などに加えて、めのアプローチは大きく 2 つに大別できる。それは、Rectified linear function (ReLU) 関数を用いたニ第一に、検索速度自体が高速であること、第二に、SRAMューラルネットワークが、区分線形関数になることを（CPU キャッシュ）など小容量ながら高速なアクセス応用した学習の最適化技術を提案している。

が可能なメモリに搭載可能なコンパクトさを有することである。これらの観点から、多くの研究が、高速な３．研究の方法検索とコンパクト差を両立できるトライと呼ばれる木3.1．学習型インデックスベースのデータ構造を用いている [1, 3]。

はじめに、本章では、学習型インデックスの詳細を一方で、パケット転送の研究分野とは独立に、デー説明する。学習型インデックスは、キーとそれに対応タベース分野において、Kraska らによって、機械学習する値の格納位置の関係を機械学習の回帰モデルとしを応用したデータベース用のインデックス構造であるて再現するデータ構造である。その概要を図 1 に示す。

学習型インデックス [5] が提案された。インデック

学習型インデックスの構築時は、KVS に格納するエス構造とは、KVS 型のデータベースにおいて、あるキントリーをそのキーの昇順（あるいは、降順）にソーーとそのキーに対応するエントリーの格納位置を保存トして格納する。このとき、エントリの格納位置はキするデータ構造であり、データベース分野では B 木やーに対する単調増加関数と見なすことができる。これハッシュテーブルなどが用いられる。これに対して、を、ターゲット関数と呼ぶ。ターゲット関数を回帰モ

学習型インデックスではキーと対応するエントリーのデルとして学習する。

格納位置の関係性を機械学習の回帰モデルで再現する構築した学習型インデックスを用いてエントリを検アプローチである。学習型インデックス構築時は、キ索するときは、まず、検索するキーに対するエントリーと対応するエントリの格納位置の関係を機械学習のの格納位置を回帰モデルで予測する。回帰モデルによ回帰モデルで学習する。検索時は、回帰モデルを用いる予測には誤差が生じるため、予測された位置の周囲てキーに対するエントリが格納されている位置を予測から真のキーの格納位置を探索する。ここで、誤差は、し、予測誤差を保証するために予測された位置の周辺予測された位置と真の格納位置との差とする。探索にを局所的に探索して真のエントリ格納位置を探索する。

は、線形探索に加えて指数探索などが利用できる。以学習型インデックスは、コンパクトながら、近年の機降、2 つのステップをそれぞれ予測フェーズと探索フ械学習向けの計算高速化技術を応用することで高速にェーズと呼称する。

エントリの検索が可能であることから、様々な応用が回帰モデルによる誤差が大きいと、誤差の訂正のた期待されている。ネットワークの分野においては、めの探索フェーズに要する時間が増加する。したがっRashelbach ら [7] が、Software-defined networkingて、探索フェーズの時間を削減するためには、誤差の(SDN) におけるフローテーブルの検索に応用するなど、縮小が課題である。層数やニューロン数の増やし高精データベース分野以外でも注目されている。

度な回帰モデルを作成することで、誤差を縮小するこ
2

TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structuresとは可能である。一方で、層数やニューロン数の増加

ーラルネットワーク計算を単純なテーブルにともない、予測フェーズに要する時間が増加する。

検索に置換する。これにより、ニューラルネ

この課題に対して、Kraska ら [5]は、予測の精度向上

ットワーク数、ニューロン数、あるいは、ニのために単一の大きなニューラルネットワークを使うューラルネットワークの層数などを増加さのではなく、図 1 に示すように、ニューラルネットワ

せることなく、予測フェーズの時間を短縮すークのモデルを階層的に連結することを提案した。各る。

ステージのモデルは次のステージで利用するモデルを探索フェーズ：探索フェーズの時間は、予測選択し、最終ステージのモデルが位置を予測する。最誤差が小さく短い時間で探索が終了できる終ステージのモデルをエキスパートモデルと呼ぶ。そことに加えて、計算機上の分岐予測ミスによれぞれのエキスパートモデルが回帰を担当する範囲をる計算時間の増加を解決する必要がある。事

限定することで、層数やニューロン数の少ないニュー前実験で、探索フェーズの計算時間のうち、ラルネットワークで精度を向上させる。

44.4%の時間を CPU における分岐予測のミスによるパイプラインストールに費やされていることが分かった。これに対して、予測フェーズにおける予測誤差が事前設計した規定値以内であり、さらに、その規定値が十分に小さい値であることを保証できることを前提に、局所探索のアルゴリズムに単純な線形探索を用いながらも、ループの展開と条件文を排除し、分岐命令を用いないことで、分岐予測によるパイプラインストールを無くし高速な検索を実現する。
実装による高速化：上記の方針に加えて、最図1

新の CPU アーキテクチャを想定した実装に階層型学習型インデックスより学習型インデックスの計算をさらに高速化する。具体的には、Single instruction

3.2．学習型 FIB の高速化方針
本研究では、予測フェーズと探索フェーズの時間短

multiple data (SIMD) 、Advanced vector

縮のため、Rashelbach ら [7] が提唱した知見、つまextensions (AVX) 命令セットの活用、積和演り、ニューラルネットワークをベースとする回帰が区算の活用、CPU キャッシュミスを削減する実分線形関数による回帰に帰着する点を応用する。具体

装法により高速化する。このため、学習型イ的には、学習型インデックスの生成に、ニューラルネンデックスの回帰モデルとして、SIMD/AVX

ットワークの学習アルゴリズムを用いずに、予測誤差命令と積和命令で高速化が可能なニューラが事前に指定した規定値以内となるように区分線形関ルネットワークを採用する。

数による近似回帰を設計することで、最悪時の予測誤差を保証する。予測誤差が規定値以内であることを前

3.3．学習型 FIB の構築法
本章では、この学習型 FIB の構築法を議論する。詳提に、以下の通りに予測フェーズと探索フェーズの時間を短縮する。

細な構築法を議論することは、本稿の趣旨から逸脱す

予測フェーズ：予測誤差が規定値以内であるるため、本稿では重要な箇所のみを議論する。具体的回帰モデルを構成できることを前提に、階層な設計法については文献 [9] に譲る。
図 2 に上記の方針に沿って設計した学習型 FIB の学習型インデックスの上位ステージのニュ
3

TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structures

全体像を示す。学習型インデックスの構成は Kraska
ら [5] の階層型の構成を採用するが、多段のニューラ

回帰モ デル

学習再現

格納位置

ルネットワークによる計算時間の増加を防ぐために、トータルで 2 ステージに限定し、さらに、第一ステー

目標関数
近似関数

ジにはニューラルネットワークではなく、テーブル参キー（ プ レ フ ィ ク ス ）区分線形近似照によりエキスパートモデルを選択できるようにする。

最大誤差を 保証パラ メ ータ 計算

このテーブルは、入力キーである IP アドレスと、そのIP アドレスに対応するエントリが格納された範囲を

図 3 学習型インデックスと学習型 FIB の構築の流れ担当する回帰モデルの ID が記入されている。ただし、IP アドレスに対して上記の対応を保存できないため、IP アドレスの空間を2 の範囲に分割し、回帰モデルが具体的な学習型 FIB の構成法は次の通りである。また、図 4 に概要を示す。

担当する範囲をその分割した範囲に限定させる。これA) IP プレフィクスと FIB エントリの格納位置

により、IP アドレスの上位 ビットをテーブルのキーの関係であるターゲット関数を導出するとして用いることができ、省スペースで高速にエキスB) ターゲット関数を区分線形関数で近似するパートモデルが選択できる。

C) 導出した区分線形関数をニューラルネットワークで表現できるように分割する
D) 分割した区分線形関数と一致するニューラルネットワークの係数を導出する
区分線形関数の設計については、動的計画法を用いた設計 [9]、あるいは、Shrinking Cone を用いた設計[10] などが利用できる。その詳細な説明は、割愛する。
B ) 区分線形近似C ) 分割

D ) パラ メ ータ 計算

格納位置A ) F IB の用意

図2

学習型 FIB の概要

タ ーゲッ ト 関数
近似関数
キー（ プ レ フ ィ ク ス ）続いて、ステージ 2 の回帰モデルの構築法を議論す

図4

学習型 FIB の構築法

る。Kraska ら [5] は、図 3 の上部に示すように、ターゲット関数をニューラルネットワークで学習した。

3.4．ニューラルネットワークと区分線形関数

これに対して、我々は、Kraska らのオリジナルの学習回帰モデルが、ReLU 活性化関数を持つニューラル型インデックス構成法とは逆に、先にターゲット関数ネットワークで構成されている場合、その回帰モデルを区分線形関数で近似し、その後にその区分線形関数は区分線形関数に帰着する [7, 9]。隠れ層が増加すると等価なニューラルネットワークを計算する方法を採と計算速度が低下するため、本稿では隠れ層 1 層のみ用した。これにより、最大誤差を事前指定した閾値以で構成されるニューラルネットワークを考える。隠れ内となるように区分線形関数を設計することができ、層のニューロン数は前章で示した通り、予測フェーズと探索フェーズの実力は IP アドレス、出力は FIB エントリの格納位置で装を高速化することができる。

あるので、入力および出力は 1 次元である。さらに、とする。学習型 FIB では、入回帰モデルの出力層の活性化関数は恒等関数とする。
この場合、このニューラルネットワークは、個の区分を持つ区分線形関数となる。区分線形関数になるこ
4

TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structuresとの証明は、[9] で議論している。
3.5．区分線形関数の分割設計した区分線形関数は、細かいサブ関数に分割する必要がある。それぞれのサブ関数が、前述したニューロンのニューラルネットワークに対応するため、それぞれのサブ関数がの線形区分を持つように分割したい。しかし、IP プレフィクスの先頭ビットを、それぞれのニューラルネットワークへのインデックスとして用いるため、単純に区分線形関数を前方から順に区分ごとに分割することはできない。これに対して、キーの範囲を 2 のべき乗数で等分割し、各区間に含まれる区分の数がを超えない範囲で隣接する区分線形関数を結合する。
この方法で分割した区分線形関数に対応するニューラルネットワークのウェイトおよびバイアスの決定方
図5法については、[9] で議論している。
3.6．学習型 FIB の検索アルゴリズム

学習型 FIB 検索アルゴリズム

3.7．評価結果

学習型 FIB の検索アルゴリズムを図 5 の Algorithm

本章では、学習型 FIB の性能を他の最先端の FIB 用1 にまとめる。予測フェーズは、CPU の SIMD/AVXデータ構造と比較する。比較対象としては、本研究の命令と積和命令を用いて実装できる。探索フェーズに遂行時点で、世界最速の FIB 用のデータ構造である

ついては、指数探索よりも時間計算量は多いものの、Poptrie [3] を用いる。Poptrie は、トライベースのデループと分岐を用いることなく実装できる線形探索をータ構造である。

採用する。予測フェーズの予測位置を 、最大予測誤差比較の指標には、IP アドレス 1 つの転送先の検索にを 、入力 IP アドレスを 、位置 の FIB エントリの要する平均時間を用いる。時間の計測には、CPU サイ

IP プレフィクスをとすると、真の FIB エントリのクル数を用いた。学習型 FIB を構築するための最大誤格納位置 を探索するのは、[ − , + ]の範囲で、 ≤差は 32 とした。FIB の構築には、オレゴン大学 Routeとなる FIB エントリの数を数えることに他ならな

Views Project [11] で 測 定 さ れ た BGP routing

い。したがって、探索フェーズは、線形探索を用いて、

information base (RIB)の 2019 年 11 月 20 日のスナ=−+ ∑ ∈[できる。ここで、,]( ≤( ≤) で求めることが) は、 ≤ップショットを用いる。FIB のネクストホップの情報は、CAIDA [12] で公開されている AS マップを用いが真であれば1、偽であれば 0 をとる関数である。右辺第二項は、ルて作成した。

ープの展開と SIMD 化された cmp 命令である vpcmp

まずメモリサイズについて、学習型 FIB が 1.83

命令を用いることで、Algorithm 1 の 8-9 行目に示しMbytes、Poptrie が 1.98 Mbytes であり、Poptrie よた通り、ループを用いることなく計算できる。

りも小さかった。
次に計算速度について、図 6 と図 7 はマッチしたプ
レフィックス長ごとの計算時間を示す。 各ひげの上/下端は 5/95 パーセンタイル、箱の上/下端は第一/三四分位、箱内部の棒は中央値をそれぞれ表す。
5TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structures

では全ての IP アドレスに対して、第一ステージのテーブル検索と第二ステージのニューラルネットワークの計算を課している。これを、Poptrie と同様に、一部の IP アドレスについてはテーブル検索処理のみで学習型 FIB の検索処理を簡潔させることで、Poptrie と同程度の平均計算速度を実現できる可能性がある。
図 6 学習型 FIB の検索時間
おわりに
本研究では、学習型インデックスと呼ばれるデータベース向けのインデックス構造の提唱に端を発して、IP パケット転送における FIB 検索のデータ構造とアルゴリズムの課題に再訪した。学習型インデックス中のニューラルネットワークによる回帰を区分線形関数に
図 7 Poptrie の検索時間よる近似を用いて設計することで、学習型インデックスによる予測と局所探索フェーズの高速化を実現した。

図から分かるように、学習型 FIB は Poptrie よりも遅いものの、比較可能なレベルの検索速度を実現でき参考文献ている。さらに、学習型 FIB はどのプレフィクス長に[1] S. Nilsson and G. Karlsson, "IP-address

ついても一定の計算時間である一方、Poptrie FIB は

lookup using LC-tries," IEEE Journal on

プレフィクス長によって計算時間に差がある。これはSelected Areas in Communications, vol.17,

Poptrie がプレフィクス長 18 以下の場合はテーブル検no.6, pp. 1083-1092, June 1999.

索のみで探索が終了するため高速であることと、プレ[2] S. Dharmapurikar, P. Krishnamurthy, andフィクス長 18 より大きい場合は木を探索するため、D.E. Taylor, "Longest prefix matching using

木の深さに依存した時間がかかることが理由である。

bloom filters," IEEE/ACM Transactions on

この結果は、将来的に 24 ビット程度の長いの IP プレNetworking, vol.14, pp. 397-409, April 2006.

フィクスが増加した場合、あるいは IPv6 などプレフ[3] H. Asai and Y. Ohara, "Poptrie: A compressedィクス長が長い場合に、学習型 FIB が有利になる可能

trie with population count for fast and性があることを示唆している。

scalable software IP routing table lookup," inProceedings of ACM SIGCOMM, pp. 57-70,
Aug. 2015.

４．将来展望前章の評価結果で議論した通り、トライに基づくデ[4] W. Jiang, Q. Wang and V. K. Prasanna,ータ構造では、エントリの検索に木を辿る操作が必要"Beyond TCAMs: An SRAM-based parallel

であることに起因して、プレフィクス長に依存して計

multi-pipeline architecture for terabit IP

算時間が延びる傾向にある。これに対して、提案手法

lookup," in Proceedings of IEEE INFOCOM,は、プレフィクス長に依らず計算時間が一定である。

Apr. 2018.
[5] T. Kraska, A. Beutel, E.H. Chi, J. Dean, andここから、2 つの展望が見える。
第一に、将来的に 24 ビット程度の長いの IP プレフ

N. Polyzotis, "The case for learned index

ィクスが増加した場合、あるいは IPv6 などプレフィ

structures," in Proceedings of ACM SIGMOD,

クス長が長い場合に、学習型 FIB が有利になる可能性

pp. 489-504, June 2018.
[6] B. Zhang, L. Wang, X. Zhao, Y. Liu, and L.

があることを示唆している。第二に、現在の学習型 FIB
6TELECOM FRONTIER No.116 2022 SUMMER

学習型インデックスを応用した高速なパケット転送
Forwarding Using Learned Index Structures

Zhang, "FIB aggregation," Internet-Draft
draft-zhang-fibaggregation-02,InternetEngineering Task Force, Oct. 2009.
[7] A. Rashelbach, O. Rottenstreich, and M.
Silberstein, "A Computational Approach toPacket Classification," in Proceedings of ACM
SIGSOMM, Aug. 2020.
[8] S. Higuchi, J. Takemasa, Y. Koizumi, A.
Tagami, and T. Hasegawa, "Feasibility ofLongest Prefix Matching Using Learned
IndexStructures,"ACM

SIGMETRICS

Performance Evaluation Review, May. 2021.
[9] S. Higuchi, Y. Koizumi, J. Takemasa, A.
Tagami, and T. Hasegawa, "Learned FIB:
Fast IP Forwarding without Longest Prefix
Matching," in Proceedings of IEEE ICNP, Nov.
2021.
[10] A. Galakatos, M. Markovitch, C. Binnig, R.
Fonseca, and T. Kraska, "FITing-Tree: A
Data-Aware Index Structure," in Proceedingsof ACM SIGMOD/PODS, June 2019.
[11] University of Oregon Route Views Project.
http://www.routeviews.org/routeviews/[12] CAIDA. https://www.caida.org/home/
この研究は、令和元年度ＳＣＡＴ研究助成の対象として採用され、令和２～３年度に実施されたものです。

7TELECOM FRONTIER No.116 2022 SUMMER