Toward Advocacy-Free Evaluation of Packet Classification Algorithms

摘要

Understanding the real performance of a proposed algorithm is a basic requirement for both algorithm designers and implementers. However, this is sometimes difficult to achieve. Each new algorithm published is evaluated from different perspectives and based on different assumptions. Without a common ground, it is almost impossible to compare different algorithms directly. Choosing an incompetent algorithm for an application can incur significant cost. This is especially true for packet classification in network routers, since packet classification is intrinsically a hard problem and all existing algorithms are based on some heuristics and filter set characteristics. The performance of the packet classification subsystem is critical to the overall performance of the network routers. Although numerous algorithms have been proposed so far, a benchmark that can give them consistent evaluation and reveal their comparable performance is still missing. This paper summarizes our efforts toward improving this situation. First, we conduct a high-level survey on the existing algorithms and extract some insights on the general design ideas. Second, we describe an open-source platform dedicated for advocacy-free evaluation of packet classification algorithms. Many representative algorithms are actually implemented under a set of uniform conditions and assumptions. The freely available implementations allow other researchers to easily test them under different scenarios. We also enforce some consistent and fundamental criteria for the algorithm evaluation, so that their performance and potentials are directly comparable, regardless of the actual implementation platforms. This project serves dual purpose: It helps the researchers to accelerate the innovation in the area of packet classification algorithm development by relieving them from the labor of replicating the previous work and by enabling them to quickly compare and evaluate algorithms. Meanwhile, it also helps the system -n-nimplementers to easily choose the capable algorithm for their particular applications. Aiming to build an open-source library, we encourage external contributions of new algorithm implementations and evaluations under the same framework. We believe the practice will benefit the research and design community as a whole.