panda's tech note

Poptrie

Multiway trie

前述したRadix treeについて,探索の深さを削減する手法として,経路検索を二分木から多分木(2^k分木)にします。Radix treeでは,入力アドレス(Key IP address)に対して1ビットずつ評価しながら木を辿りますが,2^k分木ではkビットずつ評価しながら木を辿ります。

RIBとFIB

ルーティングテーブルと言った場合,属性などを含めた経路情報を保持するRouting Information Base (RIB)と転送に必要な情報を保持するForwarding Information Base (FIB)があります。Radix treeは,RIBとしてもFIBとしても使えます。一方で,Poptrieは検索の高速化のためにFIBに特化したデータ構造にしているため,RIBとしては使えません。実装では,RIBにRadix treeを使い,Poptrieの逐次更新ではこのRIBを元にデータ構造の再構成をしています。

Radix treeでは,各ノードが経路に対応しています。そのため,Radix treeを2^k-ary multiway trie(2^k分木)にする際にプレフィックス長がkビット単位に合わない場合,多分木のノード内に二分木を持つ必要があります。しかし,この方法はFIBとして使う場合に二分木の探索を行う必要があるため,効率的ではありません。そこで,Poptrieでは,Radix treeからMultiway trieとして表現する際にする段階でFIBに特化したデータ構造にします。

二分木の探索を行わないようにするために,子ノードを持つinternal nodeと子ノードを持たないleaf nodeとしたときに,leaf nodeをFIBエントリ(転送先情報)を保持するノードとします。前述したRadix treeを例として,k=2の多分木(4分木)を作ると下図のようになります。プレフィックス長がkビット単位に合わない場合は,下図のa, cのように複数のleaf nodeに分割します。また,dのように最長一致規則で参照されない経路については,Multiway trie表現では削除されます。

multiway

子ノードの配列表現によるメモリ使用量の削減

木構造の問題点の一つは,子ノードへのポインタが大量のメモリを使用するという点です。例えば64ビットCPUでは,ポインタは8バイトであり,64分木の場合,子ノードへのリンクだけで512バイトも使用してしまいます。Poptrieでは,ポインタによるメモリ使用量を削減するために,下図の通り,子ノードを配列として表し,親ノードから子ノード配列へのポインタを1つにします。このとき,2^kビットのビット列(図中vector)を導入することで,子ノードがinternal node(vectorの対応するビットが1)であるか,leaf node(vectorの対応するビットが0)であるかを判定できるようにしています。

multiway array

なお,Poptrieでは,上述のノード配列を連続したメモリ空間(すべてのノード配列を割り当てるのに十分な長さのノード配列)から割り当てるメモリアロケータを実装することで,8バイトのポインタではなく4バイトのインデックスとして表現しています。