A compact packet classification method that realizes large scale NFV

一种实现大规模NFV的紧凑数据包分类方法

• 批准号: 19K11953
• 负责人: 田中 賢
• 金额: $ 2.83万
• 依托单位: Kanagawa University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K11953/
• 关键词: ルールリスト最適化; ルール順序最適化; NP困難; ホワイトリスト; DAG; SATソルバ; GNS3; パケット分類; C1P; Circ1P; 連; NFV; MDD

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

0 1 Circular Ones Property (Circ1P) This study aims to construct a new approach to the large-scale classification problem. Research representatives and contributors to the C1P and Circ1P solutions for the implementation of the premise, structure and sequence optimization problems for computational complexity. The construction of Min-DNF polynomial time is difficult. The sequence optimization problem is discussed in detail in the theory, and the set covering problem (X3C) is discussed in detail in the NP problem. The problem of large-scale classification is solved by optimization. This theory is discussed in detail, and C1P and Circ1P are used to construct the system. The number of columns in each column is up, the order of columns in each column is down, the method of columns in each column is down, and the effectiveness is down. The results of the construction of the decision tree are confirmed. Now, the branch and limit method can be incorporated into the existing methods, and the reduction method for determining wood support equipment can be discussed to make construction speed possible. At the same time, SAT software is used to construct high-speed network. The problem of construction of the train is that SAT changes, MinSAT changes and all kinds of solutions are used to compare CPLEX solutions. The problem is not suitable, the problem is not suitable In the future, the relationship between the position of the column and the performance of the column will be discussed at the same time.

项目成果

ポインタ付連分割トライに基づく決定図構築法

基于指针连续划分尝试的决策图构建方法

• 发表时间: 2020
• 作者: 原田崇司;田中賢;三河賢治
• 通讯作者: 三河賢治

Simulated Annealing Method for Relaxed Optimal Rule Ordering

宽松最优规则排序的模拟退火方法

• DOI: 10.1587/transinf.2019fcp0006
• 发表时间: 2020
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: Harada Takashi;Tanaka Ken;Mikawa Kenji
• 通讯作者: Mikawa Kenji

A Packet Classification Method via Cascaded Circular-Run-Based Trie

一种基于级联循环运行Trie树的数据包分类方法

• DOI: 10.1587/transfun.e102.a.1171
• 发表时间: 2019
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Harada T.;Ishikawa Y.;Tanaka K.;Mikawa K.
• 通讯作者: Mikawa K.

A Rule Reordering Method via Dependent Subgraph Enumeration

一种通过从属子图枚举的规则重排序方法

• DOI: 10.14923/transinfj.2019pdp0019
• 发表时间: 2020
• 期刊: 電子情報通信学会論文誌D 情報・システム
• 作者: 渕野 敬;原田 崇司;田中 賢;三河 賢治
• 通讯作者: 三河 賢治

Acceleration of Packet Classification Using Adjacency List of Rules

使用规则邻接表加速数据包分类

• DOI: 10.1109/icccn.2019.8846923
• 发表时间: 2019
• 期刊: Proceedings of the 28th International Conference on Computer Communication and Networks (ICCCN)
• 作者: Fuchino T.;Harada T.;Tanaka K.;Mikawa K
• 通讯作者: Mikawa K