SplitTrieとは

アルゴリズムの講義で論文紹介をする必要があるので、アルゴリズム系の論文を探して読んでいる。 結局、選んだのはSplitTrie: A Fast Update Packet Classification Algorithm with Trie Splittingだ。SplitTrieはネットワークスイッチなどが行うパケットのルールマッチング構造のアップデートを高速化する。 トライ木をfield type vectorを元に分割してサイズを抑えることでアップデート時の計算量を抑える。 一旦field type vectorによるインデックスを作成する感じだと理解している。 SDNなどのルールセットが複雑なネットワーク環境において、より効果を発揮する。