Acceleration of Packet Classification Using Adjacency List of Rules
Acceleration of Packet Classification Using Adjacency List of Rules
复制标题
使用规则邻接表加速数据包分类
DOI：
10.1109/icccn.2019.8846923
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Mikawa K
中科院分区：
文献类型：
--
作者：
Fuchino T.;Harada T.;Tanaka K.;Mikawa K
数据包分类用于确定传入网络设备的数据包的行为。由于它是通过对分类规则列表进行线性搜索来实现的，因此大量规则会导致较长的通信延迟。为了减少这种延迟，该问题被概括为最佳规则排序（ORO），其目的是确定规则的顺序，以最大限度地减少数据包分类引起的分类延迟，同时保留分类策略。由于 ORO 被认为是 NP 完全的，因此已经提出了 ORO 的各种启发式方法。子图合并 (SGM) 是 ORO 最先进的启发式算法。然而，SGM算法在大多数情况下不会终止，因为存储可达规则数量的数组更新不当。而且，由于SGM使用相邻矩阵来维护规则上的前置关系，因此当前置关系复杂时会消耗大量的时间。在本文中，我们提出了对 SGM 的修正，可以在任何情况下终止。与 SGM 相比，所提出的算法将重新排序时间减少了约 99%。此外，我们提出了一种比 SGM 更全面地选择子图的重新排序算法。与 SGM 相比，这样做可以减少延迟。我们通过实验展示了算法的效率。
Packet classification is used to determine the behavior of packets incoming to network devices. Since it is achieved using linear search on a classification rule list, a large number of rules leads to longer communication latency. To decrease this latency, the problem is generalized as optimal rule ordering (ORO), which aims to identify the order of rules that minimizes the classification latency caused by packet classification while preserving the classification policy. Since ORO is known to be NP-complete, various heuristics for ORO have been proposed. Sub-graph merging (SGM) is the state-of-the-art heuristic algorithm for ORO. However, the SGM algorithm does not terminate in most cases because of inappropriate updates of the array that stores the number of reachable rules. Moreover, since SGM uses the adjacent matrix to maintain the preceding relation on the rules, a considerable amount of time is consumed when the preceding relation is complex. In this paper, we propose a correction for SGM that can terminate for any instance. The proposed algorithm decreases reordering time by about 99\% compared to SGM. Furthermore, we propose a reordering algorithm that selects sub-graphs more comprehensively than SGM. Doing so decreases the latency in comparison with SGM. We show the efficiency of the algorithms through experiments.