data-structures - IPv6 ルックアップ データ構造

Question

パトリシア トライは、IPv4 割り当て/割り当てを格納し、ルックアップを実行するための、よく知られた推奨されるデータ構造です。

これは IPv6 アドレスにも当てはまりますか? 余分な96ビットに対応するために、より深く/より高くしようとしていますか？トライはまだパトリシアですか、それとも別の基数のトライですか?

Answer 1

パトリシア トライをより深い深さで使用することはできますが、問題は、トライの深さに比例してパフォーマンスが低下することです。IPv6 ルックアップに特化したデータ構造の設計は、活発な分野です。最近の出版物には次のものがあります。

• IPv6 ルックアップ用の動的バイナリ ハッシュ スキーム(PDF)
• 100Gbps コア ルーター ラインカード用の分散型および負荷分散型ブルーム フィルターを使用した IPv6 ルックアップ(PDF)
• FlashTrie: 100Gbps を超える IP ルート ルックアップ用のハッシュベースのプレフィックス圧縮トライ(PDF)

これらのデータ構造の利用可能な (オープン ソース) 実装については知りません。