• 機材スペック
  • Intel Core i7 4770K (3.9 GHz, 8 MiB L3 cache)
  • 8 GB DDR3-1866 DRAM x4
• トラフィックパターン
  • シーケンシャル（省略）
  • リピート（省略）
  • ランダム
  • 実トラフィック（研究教育ネットワーク）
• 経路
  • 3つの非公開経路（Tier 1 ISP x2，研究教育ネットワーク）
  • 32個の公開経路（RouteViews，RIPE NCC RIS）

Tier 1 ISPのbackboneフルルートに対するランダムトラフィックパターンのinternal node数，leaf node数，メモリ使用量，性能，上表にまとめました。　leafvec がメモリ使用量の削減に効果的であることがわかります。また，route aggregationを併用することで，木の深さが削減でき，internal node数も減るため，メモリ使用量をさらに削減でき，240.52 Mlpsの高性能を実現しています。

メモリ使用量がs=16のときにs=18よりも大きくなっているのは，eBGPで交換される経路は一般的に/24よりも短いプレフィックスであるため，s=16だと/23および/24の経路が一段階深くなる一方，s=18の場合は/24まではDirect Pointingから1段で網羅できるためです。

PoptrieではL3キャッシュを効率的に使用することで高性能を実現しています。L3キャッシュの帯域はPoptrieでの経路検索に十分と考えられますが，ここではPoptrieをマルチコアで実行した場合の性能を評価しました。評価に使用したCPUは4コアなので，4スレッドまで線形にスケールしていることがわかります。

これにより，4コア使用すれば914 Mlpsの超高性能経路検索が実現できることが示されました。

既存研究（Tree BitMap [TreeBitMap]，SAIL [SAIL]，DXR (X=16, 18) [DXR]）とPoptrieの性能比較をしました。研究教育ネットワークのコアルータのフルルートに対して，ランダムトラフィック，実トラフィックそれぞれのトラフィックパターンで性能を評価しました。性能は下表にまとめた通りです。

この評価から，SAILはランダムトラフィックには弱いが実トラフィックでは性能が出ていることが分かります。一方，DXRはランダムでは高性能を実現できていますが，実トラフィックについては性能が大幅に下がっています。Poptrie₁₈ではランダムトラフィック，実トラフィックのどちらのトラフィックパターンでも260 Mlps以上の性能を達成しています。この理由については次の節で説明します。

Poptrieも従来の検索技術も，短いプレフィックス長の経路についてはO(1)で検索できてしまうため，平均性能を評価しても実際のトラフィックに対してどの程度性能が出るかわかりません。一方，Poptrieをはじめ高速ルーティングテーブルルックアップアルゴリズムはその性能をCPUキャッシュに大きく依存しているため，入力にランダム性を持たせないと最悪時の性能評価ができません。

Poptrie論文では，シングルタスクOSを使用して，入力をランダムにしながら1検索ごとのCPUサイクル数を計測することで，どの経路に対してどのような傾向があるかを分析しました。実際にはパイプライン処理されるため，1検索ごとのCPUサイクル数は実性能を表すものではありませんが，経路に対する性能の傾向を分析するためには非常に有用です。

上図は従来研究（SAIL，DXR (X=16, 18)）とPoptrie (s=16, 18)の1検索ごとのCPUサイクル数をRadix treeでの検索の深さごとにまとめたものです。箱ひげ図により，メディアン，四分値，5/95パーセンタイル値を示しています。前節でまとめた通り，SAILは実トラフィックに対しては性能が高くなる一方，DXRはランダムトラフィックに対して性能が高くなります。ランダムトラフィックと実トラフィックの違いは，実トラフィックの方はトラフィックの局所性によりランダム性が減る一方で，プレフィックス長の長い経路宛のトラフィックが多くなります。つまり，細かくトラフィック制御をしたい経路へのトラフィックが多くなっています。つまり，上図のBinary radix depthが大きくなるトラフィックが多いです。具体的には，Binary radix depthが24よりも大きいトラフィックの割合は，ランダム，実トラフィックでそれぞれ1.7%，21.8%になります。つまり，DXRが実トラフィックに対して性能が低下するのは，上図のBinary radix depthがXよりも大きい点でCPUサイクル数が大きくなる傾向があります。一方，SAILはBinary radix depthが24よりも大きい点でもCPUサイクル数のメディアンおよび75パーセンタイル値は小さくなっています。95パーセンタイル値が大きくなっているので，ランダム性の高いトラフィックにより，キャッシュミスが発生した際に性能が落ちていると推定できます。このため，ランダム性が低く，Binary radix depthが大きい実トラフィックに対して高性能になっているものと考えられます。Poptrieでは，Binary radix depthが大きい場合も，95パーセンタイル値を低く保っており，ランダム性の高いトラフィックに対しても，Binary radix depthが大きい実トラフィックに対しても高い性能を実現しています。

• [TreeBitMap] W. Eatherton, G. Varghese, and Z. Dittia. Tree Bitmap: Hardware/Software IP Lookups with Incremental Updates. ACM SIGCOMM Comput. Commun. Rev., 34(2):97–122, 2004.
• [SAIL] T. Yang, G. Xie, Y. Li, Q. Fu, A. X. Liu, Q. Li, and L. Mathy. Guarantee IP Lookup Performance with FIB Explosion. In ACM SIGCOMM, pages 39–50, 2014.
• [DXR] M. Zec, L. Rizzo, and M. Mikuc. DXR: Towards a Billion Routing Lookups Per Second in Software. ACM SIGCOMM Comput. Commun. Rev., 42(5):29–36, 2012.