Poptrie: A Compressed Trie with Population Count for Fast and Scalable Software IP Routing Table Lookup (H. Asai et al., ACM SIGCOMM 2015)の日本語解説記事です。気が向いたので書きます。

Poptrieは80万経路以上のルーティングテーブルに対しても高速に経路検索を行うことができるルーティングテーブルルックアップアルゴリズムです。本記事ではPoptrieについて解説します。著者による解説ですが，評価などは省略するので，詳しくは原論文を参照してください。

• 検索性能（1コア）
  • 240.52 Mlps（Tier 1 backbone フルルート531,489経路，ランダムアドレス）
  • 260.60 Mlps (研究教育ネットワークコアルータ516,100経路，実トラフィックパターン)
  • 174.42 Mlps（現在のフルルートから人工的に生成した885,645経路，ランダムアドレス）

補足：評価用マシンのスペック

• CPU: Intel Core i7 4770K (3.9 GHz, 8 MiB L3 cache)
• Memory: DDR3-1866 DRAM (four 8 GiB modules)

github:pixos/poptrieで公開しています。教育，研究，評価目的に限り自由に利用できます。