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
项目状态：
已结题

项目摘要

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

当排列由0和1组成的矩阵以使每行中的1或0是连续的，据说矩阵具有圆形的属性（Circ1p）。这项研究试图创建一种新方法，以实现用于大规模数据包分类问题的紧凑型MDD。研究人员和其他研究人员研究了规则清单构建问题和规则顺序优化问题的计算复杂性，这是实现C1P和Circ1p算法的先决条件。据透露，卷轴列表的构建是从Min-DNF依赖于多项式时间的，很难NP。此外，我们对允许列表（白色列表）订单优化问题进行了理论检查，并表明它是从设定覆盖问题（X3C）中得出的，并且在NP上也很难。从这些原因中，可以说很难通过规则列表优化解决大规模数据包分类问题。在进行这些理论考虑的同时，我们一直在努力构建有效的算法，这些算法构建了满足C1P和Circ1p并行的位字符串。我们研究了几种计算每列的位值并根据偏见交换规则顺序和位置的方法，并检查了其有效性。结果，我们通过实验证实可以减小构造决策树的大小。当前，通过将分支限制方法纳入这些方法中，我们正在考虑加快构造和减少决策树规模的方法。同时，我们正在考虑使用SAT求解器快速刻有string构建的方法。位弦构建问题转换为SAT，并使用诸如Minsat和商业求解器（例如CPLEX）等各种求解器进行了比较实验。求解器对于每个问题都有适合性和不适当的性，因此我们同时考虑了每个求解器的适当转换方法，以及适合位弦构建的求解器。将来，我们还将考虑位弦的位置关系的图表，并使用图表枚举讨论解决方案。

项目成果

期刊论文数量（13）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
2020
期刊：
影响因子：
0
作者：
原田崇司;田中賢;三河賢治
通讯作者：
三河賢治

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
影响因子：
0
作者：
Harada T.;Ishikawa Y.;Tanaka K.;Mikawa K.
通讯作者：
Mikawa K.

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 Rule Reordering Method via Dependent Subgraph Enumeration

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

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

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)
影响因子：
0
作者：
Fuchino T.;Harada T.;Tanaka K.;Mikawa K
通讯作者：
Mikawa K