首页> 外文期刊>Networking, IEEE/ACM Transactions on >Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing
【24h】

Scalable Packet Classification Through Rulebase Partitioning Using the Maximum Entropy Hashing

机译:通过使用最大熵散列的规则库划分实现可伸缩的数据包分类

获取原文
获取原文并翻译 | 示例

摘要

In this paper, we introduce a new packet classification algorithm, which can substantially improve the performance of a classifier. The algorithm is built on the observation that a given packet matches only a few rules even in large classifiers, which suggests that most of rules are independent in any given rulebase. The algorithm hierarchically partitions the rulebase into smaller independent subrulebases based on hashing. By using the same hash key used in the partitioning a classifier only needs to look up the relevant subrulebase to which an incoming packet belongs. For an optimal partitioning of rulebases, we apply the notion of maximum entropy to the hash key selection. We performed the detailed simulations of our proposed algorithm on synthetic rulebases of size 1 K to 500 K entries using real-life packet traces. The results show that the algorithm can significantly outperform existing classifiers by reducing the size of a rulebase by more than four orders of magnitude with just two-levels of partitioning. Both the time complexity and the space complexity of the algorithm exhibit linearity in terms of the size of a rulebase. This suggests that the algorithm can be a good scalable solution for medium to large rulebases.
机译:在本文中,我们介绍了一种新的分组分类算法,该算法可以显着提高分类器的性能。该算法基于以下观察结果:给定的数据包即使在大型分类器中也仅匹配少数规则,这表明大多数规则在任何给定的规则库中都是独立的。该算法基于哈希将规则库分层划分为较小的独立子规则库。通过使用在分区中使用的相同哈希键,分类器仅需要查找传入数据包所属的相关子规则库。为了对规则库进行最佳划分,我们将最大熵的概念应用于哈希键选择。我们使用现实的数据包跟踪在大小为1 K到500 K的综合规则库上对提出的算法进行了详细的仿真。结果表明,该算法通过将规则库的大小减少了四个数量级(而仅进行了两级划分),可以大大优于现有的分类器。就规则库的大小而言,算法的时间复杂度和空间复杂度均表现出线性。这表明该算法对于中型到大型规则库可能是一个很好的可扩展解决方案。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号