Exploiting Order Independence for Scalable and Expressive Packet Classification
Exploiting Order Independence for Scalable and Expressive Packet Classification
复制标题
DOI：
10.1109/tnet.2015.2407831
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Kirill Kogan;S. Nikolenko;Ori Rottenstreich;W. Culhane;P. Eugster
中科院分区：
文献类型：
--
作者：
Kirill Kogan;S. Nikolenko;Ori Rottenstreich;W. Culhane;P. Eugster
有效的数据包分类是网络服务的核心问题。传统的多字段分类方法，在软件和三进制内容寻址存储器（TCAM），需要（存储器）空间和（查找）时间之间的权衡。TCAM不能有效地表示范围规则，这是一种将数据包字段的值限制在给定范围内的常见分类规则。当多个字段包含范围时，TCAM条目相对于字段数量的指数空间增长会加剧。在这项工作中，我们提出了一种新的方法，它确定了许多分类器，可以在线性空间中实现，并与最坏情况下保证对数时间的属性，并允许添加更多的字段，包括范围约束，而不影响空间和时间的复杂性。在Cisco Systems的真实分类器和ClassBench的附加分类器（具有真实的参数）上，因此可以处理90-95%的规则，而其他5-10%的规则可以存储在TCAM中以进行并行处理。
Efficient packet classification is a core concern for network services. Traditional multi-field classification approaches, in both software and ternary content-addressable memory (TCAMs), entail tradeoffs between (memory) space and (lookup) time. TCAMs cannot efficiently represent range rules, a common class of classification rules confining values of packet fields to given ranges. The exponential space growth of TCAM entries relative to the number of fields is exacerbated when multiple fields contain ranges. In this work, we present a novel approach which identifies properties of many classifiers which can be implemented in linear space and with worst-case guaranteed logarithmic time and allows the addition of more fields including range constraints without impacting space and time complexities. On real-life classifiers from Cisco Systems and additional classifiers from ClassBench (with real parameters), 90-95% of rules are thus handled, and the other 5-10% of rules can be stored in TCAM to be processed in parallel.