NeTS: Small: Collaborative Research: Distributed Approximate Packet Classification

网络流量分类-根据模式匹配规则将传入数据包分配到类别进行处理-对于许多网络管理任务（包括性能监控和故障诊断）至关重要。 然而，随着分类任务数量的增长，存储和应用规则所需的资源（特别是交换机内存）可能会变得稀缺。 该项目采取了一个端到端的流量分类的观点，观察到，除了在交换机的内存使用，其他，更便宜的资源参与数据包处理，特别是带宽传输选定的数据包到接收器，和接收器系统本身。所提出的方法通过引入过度选择来权衡内存和带宽，其中在减少的内存中进行的近似分类引入了额外的不需要的流量。这个想法是，在许多应用程序中，过度选择的副作用是相当可控的;该项目将研究多种类型的应用程序，如中间盒和数据包洗涤器，可以容忍过度选择。该方法涉及一个布谷鸟过滤器为基础的近似前缀匹配器在交换机，存储不同的前缀长度的分类规则。支持分布式近似数据包分类的关键挑战包括：（1）最好地支持内存和过度选择之间的权衡的新数据结构;（2）处理具有过度选择的流量动态和网络动态的新算法和系统;（3）过度选择对不同网络功能的影响的系统分析;以及（4）交换机和接收机的空间和时间协调。 该项目将使这些管理应用程序的创新和重新设计依赖于软件定义网络（SDN）中的流量分类，从而导致更有效地管理企业和数据中心网络。此外，这项工作将促进理论和系统研究之间的互动。最后，主要研究人员有参与研究的代表性不足的群体和本科生的记录，并计划继续这些参与作为本项目的一部分。

Network traffic classification - assigning incoming packets to classes for processing based on pattern-matching rules - is critical for many network management tasks, including performance monitoring and fault diagnosis. However, as the number of classification tasks grows, the resources required to store and apply the rules (switch memory in particular) can become scarce. This project takes an end-to-end view of traffic classification, observing that in addition to the memory usage at switches, other, cheaper resources are involved in packet processing, specifically bandwidth to transfer selected packets to the receivers, and the receiver systems themselves. The proposed approach trades off memory for bandwidth by introducing overselection, in which approximate classification made in reduced memory introduces additional unwanted traffic. The idea is that in many applications, the side-effects of overselection are quite manageable; the project will investigate multiple types of applications such as middleboxes and packet scrubbers that can tolerate overselection. The approach involves a Cuckoo-filter-based approximate prefix matcher at switches, which stores classification rules with different prefix lengths. The key challenges in supporting distributed approximate packet classification include: (1) new data structures that best support the tradeoffs between memory and overselection; (2) new algorithms and systems that handle traffic dynamics and network dynamics with overselection; (3) systematic analysis of the impact of overselection on different network functions; and (4) spatial and temporal coordination of switches and receivers. This project will enable innovations and redesign of these management applications relying on traffic classification in software defined networks (SDN), and thus lead to more efficiently managed enterprise and datacenter networks. Moreover, the work will facilitate interactions among theoretical and systems research. Finally, the principal investigators have a record of engaging underrepresented groups and undergraduates in research and plan to continue these engagements as part of this project.