NeTS: Small: Collaborative Research: Distributed Approximate Packet Classification Grant uri icon


  • 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.This award reflects NSF''s statutory mission and has been deemed worthy of support through evaluation using the Foundation''s intellectual merit and broader impacts review criteria.

date/time interval

  • 2016 - 2020