Abstract :
Packet classification is a very basic technique in supporting various advanced network services, for example, network measurement, quality of service, flow routing, and so on. Traditional decision tree-based packet classification algorithms often generate many redundant rules. To solve this issue, we propose GroupCuts, which employs two novel ideas. (1) Space relationship-based rule clustering: according to the analysis of classifiers, GroupCuts clusters the rules of similar size and then partitions the classifiers into subgroups. Building decision trees in these sub-groups achieves fine space performance. (2) Dynamic Point Split: in order to reduce the rule duplication in decision trees, we select multiple rule projection points to accomplish space decomposition. Using simulations of 1,000 to 100,000 rule classifiers, we show that, compared with other existing algorithms, the proposed algorithm achieves an improvement in memory requirement without reducing the search performance.
Keywords :
Internet; decision trees; pattern clustering; quality of service; telecommunication network routing; GroupCuts; advanced network services; clustered dynamic point split algorithm; decision tree-based packet classification algorithms; dynamic point split; flow routing; multiple rule projection points; network measurement; next generation Internet equipment; quality-of-service; rule duplication reduction; space decomposition; space relationship-based rule clustering; Algorithm design and analysis; Arrays; Classification algorithms; Clustering algorithms; Decision trees; Heuristic algorithms; Quality of service; decision tree; memory optimization; packet classification; quality of service;
