panda's tech note

Poptrie

Poptrie (leafの圧縮)

Poptrie (basic)では,ノード配列の空ノードを削減しました。しかし,多分木を導入した時点でプレフィックス長が2^k分木の区切りに合わない場合は,経路を分割しているため,leaf nodeには同一経路に由来する同一の転送先が複数連続していることがあります。kが大きくなるほど,leafに冗長なノードが多くなることが予想されます。

経路分割により生じた同一のleaf nodeを圧縮するために,新たなビット列 leafvec を導入します。leafvec は,基本的に多分木の探索キーに対応する子ノードがleaf nodeである場合,それに対応するビットを1にします。ただし,同じleaf nodeが連続する場合は下図のように0にします。

array compression

internal node配列のインデックスの決定については,Poptrie (basic)と同じです。leaf node配列のインデックスを決定する際に leafvec を使用し,以下のように決定します。

popcnt( (2 << N) - 1) & leafvec ) - 1 // if ((1 << N) & vector) == 1

これにより,連続する同一のleaf nodeの冗長性を排除することができ,leaf node配列を大幅に圧縮することができます。

経路圧縮

上図では,同一経路のleaf nodeのみを圧縮しましたが,FIBでは転送先のみが必要なので,転送先が同じであれば経路が異なっていても同様に圧縮することができます。