C-Engine の構成

C-Engineは，BSPの中央部に位置し，A-Engineから受信したトークンを処理結果や処理方法を 含むトークンに置き換えてR-Engineへ渡す処理を担う，CBNPの中心的役割を果たす機能ブロッ

3.3. CBNP^{各部の構成}

クである．第2章で紹介したネットワークプロセッサの機能に当てはめると，パケットのボトル ネック処理(テーブルルックアップやカプセリングヘッダ生成等)の結果を即座に取り出す部位に 相当する．図3.3にC-Engineのブロックダ イアグラムを示す．

図3.3: C-Engineのブロックダ イアグラム

C-Engineは，Process Learning Cache (PLC)と呼ぶパケット処理結果や処理方法を記録するキャッ シュメモリ機構とCache-Miss Handler (CMH)と呼ぶPLCに未登録のトークンを処理する機構を 備える．また，CMH経由でP-Engineを接続しており，C-Engineだけで処理ができない場合，補 助的にP-Engineを利用する．PLCはHTQ (Hit Queue)と呼ぶFIFOキュー経由でR-Engineと接続 されている．HTQは，後述のPLCヒットしたトークンを一時的に保持し ，CMHからPLCミス して処理されたトークンが発行されていないタイミングで保持しているトークンをR-Engineへ送 信する．R-Engine側から観測すると，HTQの存在により，A-Engineから送信されてくるトーク ンがPLCにヒットしてもミスしても，常時，C-Engineから連続的にトークンを受信できるように なり，CBNPのスループット低下を防ぐことができる．以下に，PLCとCMHに関してそれぞれ の詳細を説明する．

PLC (Process Learning Cache)の役割と構成

PLCは，パケット処理のうちボトルネックとなる処理の結果，特に各種のルックアップやカプセ リングヘッダ生成等の結果，更に，BSPのR-Engineにおける処理結果の適用方法を記録するため のキャッシュメモリである．PLCは，最初は全エントリが空の状態であるが，A-Engineからトー クンを受信し始めると次々と登録されていく．登録されるのは，パケットフローの先頭のトーク ンのP-Engineでの処理結果(R/P-Info)である．尚，この登録は，トークンを受信してからCMH

経由でP-Engineにトークンが渡され，P-Engineでの処理が完了してからであるため，その分のタ

イムラグがある．この点に関しては，CMHの項で追加説明するため，ここでは省略する．PLCに 登録後は，後続の同一ヘッダとみなせるヘッダを持つパケットのトークン(A/E-Infoが同一)には，

P-Engineを一切利用せずに，PLCの内容をそのまま利用できる(R/P-Infoを即座に渡す)．通信の

3.3. CBNP^{各部の構成}

時間的局所性の存在が強く期待できる場合，大多数のパケットのトークンに対し ，PLCから直接 R/P-Infoを与えることができるため，P-Engine(通常のネットワークプロセッサのPE集積部分)の スループットが低くてもCBNPは高スループットのパケット処理を実現できる．

図3.4: PLCのブロックダ イアグラム

PLCは，通常のキャッシュメモリと同様，図3.4に示すように，タグ メモリとデータメモリで構 成する．複数ウェイ構成の場合，リプレースウェイを決定するためのLRUメモリも備える．また，

ダ イレ クトマップ 方式(割当てエントリを一意に決定)やセットアソシアティブ 方式(割当てエン トリをセット中のウェイのいずれかに決定)，フルアソシアティブ方式(割当てエントリを自由に 決定)等の構成をとることができ，図3.4の例では，4ウェイのセットアソシアティブ 方式の場合 を示している(LRUメモリは省略している)．PLCの格納内容は，表3.3に示す通りである．

表3.3: PLCの格納内容 項目 格納内容

PLC TAG トークンのA/E-InfoとValid bit PLC DATA トークンのR/P-Info

複数の情報(例：A-InfoとE-Info)はスラッシュで区切って表記(A/E-Info)する．

PLC TAGが有効な状態(Valid bitが1)において，入力トークンのA/E-Infoが ，PLC TAGの A/E-Infoと一致すれば「PLCヒット 」，不一致であれば「PLCミス」と呼ぶ．PLCのアクセス方 法は以下の通りである．

1. トークンのA/E-InfoをCRCハッシングし ，PLC TAGを参照する．PLCヒットなら2へ，

PLCミスなら3へ進む

3.3. CBNP^{各部の構成}

2. 該当するPLC DATAを読み出し ，トークンのE-InfoをR-Infoに置き換え，P-Infoを付加し てHTQ経由でR-Engineへ送信し終了

3. CMHへPLCミスしたトークンを渡す．当該トークンの処理がCMHで完了したら，PLC

TAGをA/E-Infoで，PLC DATAをR/P-Infoで更新する．また，PLCミスを起こしていた トークンはCMHでトークンのE-InfoをR-Infoに置き換え，P-Infoを付加してR-Engineへ 送信し 終了(詳細は次に示す「CMHの役割と構成」を参照)

PLCは，パケット処理結果や処理方法を記録するため，通常のキャッシュと異なる点を幾つか 備えている．その違いは，タグ格納内容，ハッシング方法，キャッシュライン格納量，アクセス種 類である．それぞれに関して説明する．

• タグ格納内容： 通常のプロセッサのキャッシュでは，アクセスアドレスのうちキャッシュを インデックスする下位数ビットを除いた上位ビットをタグとして利用する．PLCでは，トー クンのA/E-Infoをタグとして利用する．

• ハッシング方法： ハッシング方法とは，PLCへのトークン(データ)格納位置(インデック ス)を決定するための方法である．通常のプ ロセッサのキャッシュでは，データがど のアド レスに存在するかによって区別しており，目的のデータへのアクセスアドレスの下位数ビッ トをそのままインデックスとして利用している．PLCでは，個々のパケットをトークンとし て表現しており，同一フローに属するパケットからは解析結果(A-Info)と抽出内容(E-Info) が同じトークンが生成される仕組みである．そこで，トークンのA/E-Infoが同じであれば PLCで同一のインデックスを利用する必要がある．しかしながら，A/E-Infoは，単純なア ドレスではなく，解析した情報と，パケットから抽出した複数のフィールドを結合したもの であり， 大きさが400bit強に達するため，従来のように単純な一部のビットだけを利用す ることが極めて困難である．単純なIPフォワーデ ィングでは，従来のキャッシュの研究の ように，宛先IPアドレ スだけを利用しその一部のbitをインデックスとして利用すること も可能であるが，5-tupleのような5フィールド の情報を抽出して優先度や宛先，処理方法 を決定する場合には扱いが極めて困難である．そこでPLCでは，A/E-Info全体に対しCRC (Cyclic Redundancy Check，巡回冗長検査)ハッシングを行ない，得られた剰余をインデック スとして利用する．CRCは，連続する誤りを検出するための誤り検出符号の一種であり，十 分な撹拌能力を持つため，誤り検出だけでなく，データ検索のハッシングキーとしても利 用できる．また，入力データビット列から任意の長さのキーを生成することができるため，

400bit強の非常に長いビット列であるA/E-Infoから，十数bit前後の比較的短いビット列で あるPLCのインデックスを生成するために適している．CRC回路は，複数段のXORゲー トで容易に構成することができる利点もある．表3.4にCRCハッシングの演算多項式の例 を挙げておく．

• キャッシュライン格納量： 通常のプロセッサのキャッシュでは，データの空間的局所性を利 用するために，キャッシュタグが示すキャッシュデータ位置には複数のデータをキャッシュ ラインとして格納している．通常，キャッシュラインは複数データで構成されており，アク セスアドレスの最下位数ビットを利用して個々のデータを区別する．キャッシュラインに複 数のデータを含んでいるのは，通常のプログラムでは，あるアドレ スを始点にアドレ スが 連続する複数のデータを扱うことが多いため，連続したデータを同一タグで参照するキャッ シュデータとして登録した方がキャッシュヒット率が向上するためである．PLCでも，宛先

3.3. CBNP^{各部の構成}

表3.4: CRC多項演算式の例

剰余のビット数 メモリのエントリ数 CRC多項演算式 8 256 X⁸+X⁶+X³+X²+1

9 512 X⁹+X⁵+1

10 1K X¹⁰+X⁷+1

11 2K X¹¹+X²+1

12 4K X¹²+X³+1

13 8K X¹³+X⁴+X³+X¹+1

14 16K X¹⁴+X⁵+1

15 32K X¹⁵+X¹+1

16 64K X¹⁶+X⁵+X³+X¹+1

17 128K X¹⁷+X³+1

18 256K X¹⁸+X³+1

IPアドレ スだけをインデックスに利用するのであれば，最下位数ビットが異なるIPアドレ スは同一の宛先ネットワークである可能性が高いので，若干の空間的局所性がありヒット 率向上が期待できる．しかしながら，PLCでは5-tupleのような複雑なトークン内容にも対 応するため，トークンのA/E-Info^をCRCハッシングしてアクセスする．このため，従来の プロセッサで見られるようなアドレスの空間的局所性を直接利用することができない．よっ て，PLCのデータはキャッシュラインの概念を持たず，持ったとしても1データのみで構成 するキャッシュラインとなる．

• アクセス種類(リード オンリー)： 通常のプロセッサのキャッシュは，データの読み出し ，書 き込みの両方を行なう．PLCは，先行トークンの処理結果を後続の同一フローのトークン (同一A/E-Infoを持つトークン)に適用するためのキャッシュであるため，読み出しを行なう だけであり，動作としては命令キャッシュに近い．このため，データキャッシュで問題とな る書き戻し 問題(ライトスルーやライトバックポリシーの選択，そのための処理方法)が発 生しない．ただし ，後述するように，ルーティングテーブルとの間で情報を同期させるため のPLCエントリ廃棄動作が存在する．

時間の経過と共にPLCには有効なエント リが増えていき，やがて，あるフローのトークンに とって空きエントリが無い状態が発生する．この場合，通常のプロセッサのキャッシュと同様に，

PLCエントリのリプレースを行なってエントリを確保する．すなわち，PLCの有効なエントリと 同一のエントリに割り当てられる後続の別フローのトークンが来た場合，PLCが既に古いフロー に割当て済みであれば，古いフローのエントリを新しいフローで上書きする．上書きされた後は，

古いフローは再びPLCミスを起こし ，新しいフローがPLCヒットするようになる．これら新旧 のフローが継続的に存在する場合，PLCの同一エントリは両フローで絶えず更新され続ける．こ れは，通常のプロセッサのキャッシュで，異なるアドレスのデータが同一のキャッシュエントリに 割り当てられるために発生するピンポン現象に類似する．尚，あるフローがあるPLCエントリを 更新する前に別のフローが同一のPLCエントリを要求することもありうる．この場合，最終的に PLCに登録されるのは後続のフローである．尚，古いフローも新しいフローも，後述のCMHの 異なるCMTエントリに割り当てられ，PLC登録されるまではCMHでキャッシュヒットと同等の 扱いを受けることができる．CMTで同一のエント リに割り当てられるフローが続出しない限り

3.3. CBNP^{各部の構成}

は，後続のトークン群は，ノンブロッキングでPLCアクセスを続けることができるため，CBNP は高いスループットを維持できる．

通常，PLCに一旦エントリが登録されると，当該エントリは新しいフローで上書きされるか，後 述のルーティングテーブル更新が発生するまで存在し続ける．セットアソシアティブ方式のPLC の場合，新しいフローで上書きされる場合は，LRU等のアルゴ リズムによって上書きされるセッ トのエントリが決まるが，既に不要なエントリであることがわかるのであれば ，不要なエントリ を消去した方が効率が良い．クラシフィケーションの種類によっては，不要なエントリを明示的 に削除する方法を採ることも可能である．例えば，5-tupleの場合，TCPフローを意識することが 可能であり，TCPのFIN bitが1，かつACK bitが0であれば，当該TCPフローの最後のパケット であるので，PLCにエントリが存在する場合，当該エントリを明示的に消去することができる．

CMH (Cache Miss Handler)の役割と構成

PLCの項で触れたように，PLCへのR/P-Info登録には，P-Engineでの処理が完了するまでのタ イムラグがある．ネットワークのパケット転送処理においては，このタイムラグを放置すると致命 的な性能低下を引き起こし うる．何故なら，PLC登録が完了するまで，ネットワークから次々と やってくるパケットの処理が停止してしまうからである．このため，PLC参照をノンブロッキン グ化するための仕組みが重要となる．PLC参照のノンブロッキング化とは，PLCのhit under miss 処理とmiss under miss処理を意味する．

• hit under miss処理：先行トークンでPLCミス発生中に後続トークンのPLCヒットを許し ， PLCミス処理のレ イテンシの一部をPLCヒット処理で隠蔽すること

• miss under miss処理：先行トークンでPLCミス発生中に後続トークンのPLCミスを許し ， 複数のPLCミス処理をオーバーラップさせて進めることでPLCミス処理のレ イテンシの一 部を隠蔽すること

CMHは，PLCミスしたトークンを連続的に受信してPLC参照をノンブロッキング化する機能，

受信したトークンをP-Engineに処理を割り当てる機能，また，P-Engineから処理済のトークン を受信しPLCを更新する機能を持つ．図3.5にCMHのブ ロックダ イアグラムを示す．また，表 3.5にCMH内の機能部位と格納するトークンの内容一覧を示す．

表3.5: CMH内の機能部位と格納内容

機能部位 格納内容 備考

CMT A/E-Info PLCミス中の全フローを管理するテーブル．

(Cache Miss Table) フローの先頭トークンのみP-Engineで処理．

CMQ U-Info 同一フロー中の各トークンを管理するFIFOキュー．

(Cache Miss Queue) 各CMQはCMTの各エントリに対応．

EWQ U/A/E-Info P-Engine処理待ちのトークンを管理するFIFOキュー

(Ex. Waiting Queue)

PRQ R/P-Info P-Engine処理済みトークンを管理するFIFOキュー

(Processing Result Queue)