# パケット分類 ## 定義 パケット分類(packet classification)とは、到着したパケットのヘッダフィールド(Ethernet アドレス・IP アドレス・トランスポートポート・スイッチ入力ポート等の任意の組み合わせ)を、フローテーブル中で条件を満たす最高優先度のルールと照合し、適用すべきアクションを決定する処理である。[[OpenFlow]] のようにマッチ条件が任意のフィールド組み合わせを許す一般的な形式を取る場合、分類は特に高コストになる。汎用プロセッサ上でこの処理を高速に行うことは、ソフトウェアスイッチの性能を左右する中心的な技術課題である。(Source: [[@2015__NSDI__The Design and Implementation of Open vSwitch]] §3.2) [[Open vSwitch (OVS)|Open vSwitch]] はカーネル・ユーザ空間の両方で**タプル空間探索(tuple space search)分類器**(Srinivasan, Suri, and Varghese, SIGCOMM 1999)を採用する。同一フィールド集合にマッチするフロー群を1つのハッシュテーブル(「タプル」)にまとめ、異なるマッチ形式が追加されるたびに新しいタプルを生成する。探索は該当しうる全タプルへのハッシュルックアップとなり、複数タプルにマッチがあれば最高優先度のフローが採用される。決定木ベースの分類アルゴリズムと比べ、(1) 効率的な定数時間更新(1回のハッシュテーブル操作で済む)、(2) 任意個数のフィールドへの一般化が容易、(3) フロー数に対して線形なメモリ使用量、という3つの利点を持つ一方、ルックアップ複雑度自体は最先端の分類アルゴリズムに劣る。(Source: [[@2015__NSDI__The Design and Implementation of Open vSwitch]] §3.2) ### キャッシュを意識した分類器の最適化 OVS はさらに、素朴なタプル空間探索が生成する「必要以上に厳しいキャッシュエントリ(メガフロー)」の問題に対処する4つの最適化を導入している(いずれも正当性——必要なフィールドへのマッチを削らないこと——を犠牲にしない)。 - **タプル優先度ソート**: 各タプルの最大優先度を追跡し、優先度の高いタプルから探索することで、それ以上高優先度のマッチが存在しえないと分かった時点で早期終了する。 - **ステージドルックアップ**: 1つのタプルをメタデータ・L2・L3・L4 の4段階のハッシュテーブルに分割し、早い段階で不一致と判定できればそれ以降のフィールドをメガフローの条件に含めずに済む。 - **プレフィックストラッキング**: IP アドレスに対しトライ構造で最長プレフィックスマッチ探索を事前に行い、メガフローに含めるべきビット数を最小化するとともに、影響を与えないタプルの探索をスキップする。 - **分類器パーティショニング**: OpenFlow のメタデータフィールドでタプル集合をパーティション分割し、現在のメタデータ値が存在しないタプルの探索を丸ごとスキップする。 これら4つの最適化は独立に効果を持つが、組み合わせるとカーネルフロー数を数桁削減し(マイクロベンチマークで1,051,884→15)、スループットを最大3倍以上向上させることが実証されている。(Source: [[@2015__NSDI__The Design and Implementation of Open vSwitch]] §5, Table 1) ### フローキャッシュとの関係 パケット分類のコストは、フローキャッシュ(マイクロフローキャッシュ+メガフローキャッシュの2層構造)と表裏一体である。メガフローは「実際に分類で参照されたパケットフィールドのビット集合」だけをマッチ条件とする形で、ユーザ空間の分類結果からインクリメンタルに生成される。分類器の最適化(上記4つ)は、この生成されるメガフローをできるだけ一般化する(=より多くのパケットにヒットする)ことでキャッシュヒット率を高めるものであり、「分類アルゴリズムの高速化」と「キャッシュの有効性向上」が同一の最適化群によって同時に達成される点が OVS の設計の要点である。(Source: [[@2015__NSDI__The Design and Implementation of Open vSwitch]] §4, §5) ## 横断的知見 - (単一ソースからの導入のため、現時点では横断的知見は蓄積されていない。今後、他のソフトウェアスイッチ・ハードウェア分類アルゴリズム(TCAM ベース等)の ingest 時に比較知見を追加する。) ## 未解決の問い - タプル空間探索(OVS)と TCAM ベースのハードウェア分類、決定木ベースの分類アルゴリズム(HiCuts・EffiCuts 等、OVS 論文が引用する関連研究)は、フロー数・フィールド数が大きい条件下でどの程度の性能差を持つか。OVS 論文は「タプル空間探索は最先端の分類アルゴリズムに劣る」と述べるにとどまり、定量比較は示さない。 - ステージドルックアップにおける「メタデータ→L2→L3→L4」という層順の固定分割は、OpenFlow 以外のマッチフィールド体系(P4 の任意ヘッダ定義等)にも一般化できるか。論文はこの分割がプロトコル層の直感に基づく設計判断であり、技術的に必須ではないと明言している。 - OVS のキャッシュ無効化機構(Bloom フィルタベースのタグから全数再検証への転換、§6)は、パケット分類器自体の設計選択(タプル空間探索)にどこまで起因する制約か。異なる分類アルゴリズムを採用した場合、より精密なキャッシュ無効化が可能になるか。 ## 関連 - 概念: [[ソフトウェア定義ネットワーク]] / [[ネットワーク仮想化]] - 実体: [[Open vSwitch (OVS)]] / [[OpenFlow]] / [[Ben Pfaff]] - [[@2015__NSDI__The Design and Implementation of Open vSwitch]] — タプル空間探索分類器の4つの最適化とフローキャッシュ設計の一次資料。 ## 出典 - [[@2015__NSDI__The Design and Implementation of Open vSwitch]](Pfaff, B., et al., NSDI '15。§3.2 タプル空間探索の基礎、§5 キャッシュを意識した分類器の4最適化、Table 1 の定量評価)