Evaluating Partitions in Packet Classification with the Asymmetric Metric of Disassortative Modularity

At present, the method of using rule set partitioning technology to assist in constructing multiple decision trees for packet classification has been widely recognized. Rule set partitioning demonstrates a unique symmetry-breaking mechanism, systematically transforming the initial overlapping rule space into a more structured and balanced configuration. By separating overlapping rules in the initial stage, this method significantly reduces rule replication within trees, thereby improving the algorithm’s classification performance. The asymmetric characteristics of this partitioning process are particularly noteworthy: through the strategic disruption of the initial rule set’s symmetric distribution, it creates asymmetric subspaces with enhanced computational efficiency. However, existing research lacks standardized metrics for evaluating the effectiveness of rule set partitioning schemes. The purpose of this paper is to investigate the impact of partitioning on algorithm performance. Based on community structure theory, we construct a weighted graph model for rule sets and propose a disassortative modularity metric to evaluate the effectiveness of rule set partitioning. This metric not only examines intra-community connections but also emphasizes the asymmetric connections between communities. By quantifying these structural features, it provides a novel perspective on rule set partitioning strategies. The experimental results demonstrate a significant positive correlation between disassortative modularity and classification throughput. This metric offers valuable guidance for packet classification partitioning techniques, highlighting the practical significance of symmetry and asymmetry in algorithm design.