ROOM: Rule Organized Optimal Matching for fine-grained traffic identification

Fine-grained traffic identification (FGTI) reveals the context/purpose of each packet that flows through the network nodes/links. Instead of only indicating the application/protocol that a packet is related to, FGTI further maps the packet to a meaningful user behavior or application context. In this paper, we propose a Rule Organized Optimal Matching (ROOM) for fast and memory efficient fine-grained traffic identification. ROOM splits the identification rules into several fields and elaborately organizes the matching order of the fields. We formulate and model the optimal rule organization problem of ROOM mathematically, which is demonstrated to be NP-hard, and then we propose an approximate algorithm to solve the problem with the time complexity of O(N²) (N is the number of fields in a rule). In order to perform evaluations, we implement ROOM and related work as real prototype systems. Also, real traces collected in wired Internet and mobile Internet are used as the experiment input. The evaluations show very promising results: 1.6X to 104.7X throughput improvement is achieved by ROOM in the real system with acceptable small memory cost.