トラヒック局所性を利用した拡張パトリシアトリーの提案と評価

摘要

本論文ではパトリシアトリーを縮約し，探索コストを低減する拡張パトリシアトリーを提案，評価rnする．拡張パトリシアトリーは従来のパトリシアトリーに存在する空きボインタにもエントリを登録することでrn木を縮約する．また大多数のアクセスが少数のエントリに集中するというトラヒック局所性を利用し，アクセスrnが集中するエントリを木の浅い位置に登録することでルーチングルックアップの平均コストを削減する．プレrnフィックスの一致度に従って構築した拡張パトリシアトリーは従来のパトリシアトリーよりも木を縮約し，多進rn木に拡張することで縮約の度合を高めた．またトラヒック局所性を利用して木を最適化する場合，Guptaらによrnる提案手法よりも平均コストが可能である．また提案手法はGuptaらの提案手法では困難であったインクリメrnンタル更新にも対応可能である．