MP-ROOM: Optimal Matching on Multiple PDUs for Fine-Grained Traffic Identification

This paper studies the fine-grained traffic identification (FGTI) for better understanding and managing networks.Instead of only indicating which application/protocol that a packet is related to, FGTI maps the traffic packet to ameaningful user behavior or application context. In this paper, we first propose rule organized optimal matching (ROOM),which splits the identification rules into several fields and elaborately organizes the matching order of the fields. Asa result, ROOM can only activate the matching operations on a (small) part of the rules that could be possibly hit. Weformulate the optimal rule organization problem of ROOM mathematically and demonstrate it to be NP-hard, and then wepropose a heuristic algorithm to solve the problem with the time complexity of O(N²) (N is the number of fields in the rule set). Based on ROOM, wefurther propose MP-ROOM, which is extended to well support the rules cross multiple protocol data units (PDUs) fortraffic identification. In addition, we implement a prototype system including MP-ROOM and related work for evaluations.The evaluations show very promising results: 1.5 ~71.3 times throughput improvement is obtained by MP-ROOM inthe real system with less than 300-MB memory consumption. With multiple-thread parallel programming, we successfullyachieve the throughput over 40 Gb/s for real traces.