A compact packet classification method that realizes large scale NFV

点击翻译按钮获取中文摘要

0と1からなる行列に対し、各行の1または0が連続するように列を並べられるとき，その行列はCircular Ones Property (Circ1P)をもつという。本研究では、大規模なパケット分類問題に対して、コンパクトなMDDを実現する新たな手法を構築しようとしている。研究代表者と分担者は、C1PおよびCirc1Pに対するアルゴリズムを実現する前提として、ルールリスト構築問題とルール順序最適化問題に対する計算複雑さの検討を行った。リールリストの構築はMin-DNFから多項式時間帰着可能でありNP困難であることを明らかにした。さらに、許可リスト（ホワイトリスト）順序最適化問題に対する理論的検討を行い、それが集合被覆問題(X3C)から帰着され同様にNP困難であることを示した。これらのことから大規模なパケット分類問題をルールリスト最適化によって解決することは困難であるといえる。これらの理論的な検討を行いつつ、並行してC1PおよびCirc1Pを満たすビット列を構築する効率的アルゴリズムの構築を行ってきた。各列のビット値を数え上げ、その偏りによってルール順序とビット位置を入れ替えるいくつかの方法を検討し、その有効性を検討した。その結果、構築される決定木のサイズを削減できることを実験的に確認した。現在は、それらの方法に分枝限定法を取り入れることにより、構築の高速化を可能にするとともに、決定木サイズの削減法を検討している。同時に、SATソルバを用いてビット列構築を高速に行う方法を検討している。ビット列構築の問題をSATに変換し、MinSATなどの各種ソルバやCPLEXなどの商用ソルバを用いて比較実験を行っている。ソルバには、問題ごとの適、不適があることから、ビット列構築に適したソルバとともに、それぞれに応じた適切な変換方法を同時に検討している。今後はビット列の位置関係をグラフ表現し、グラフ列挙による解法も同時に検討していく。