Logo PTI Logo FedCSIS

Proceedings of the 21st Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 47

EnsembleClassifier: Using Machine Learning to Select Exact Packet Classification Structures for Partitioned Rule Subsets

, ,

DOI: http://dx.doi.org/10.15439/2026F4917

Citation: Ashesh Gaur, ,

Full text

Abstract. Packet classification is a core bottleneck in highspeed networks, where packets must be matched against large and heterogeneous rule sets under strict latency and memory constraints. Existing classifiers apply a single data structure across the entire ruleset, failing to adapt to local geometric diversity and resulting in suboptimal performance. We present EnsembleClassifier, a new architecture that decouples rule-space partitioning from structure selection. The system decomposes the ruleset using connected-component analysis, producing disjoint subsets without rule replication. Each subset is assigned an exact classifier chosen from a portfolio using a learned model trained on Classbench rulesets with exhaustive performance labels. Correctness is guaranteed by construction: learning affects only structure selection, while packet matching remains exact and preserves first-match semantics. Across ClassBench rulesets from 1k to 64k sizes, we generated approximately 70k feature vectors. These feature vectors were used to decide which algorithm was most suitable for the given feature vector. The composition tree then uses multiple algorithms for a given ruleset. Our composition tree reduced average per-packet classification latency by 46\%, memory footprint by 99.14\%, and build time by 98.65\%, in each case measured against the strongest baseline in our portfolio for that metric. These results show that treating packet classification as a composition problem enables adaptive, structure-aware designs that significantly improve performance while preserving strict correctness guarantees. More broadly, EnsembleClassifier demonstrates how learned decision-making can be embedded directly into network data-plane infrastructure without relaxing the exactness guarantees such infrastructure demands.

References

  1. P. Gupta and N. McKeown, “Classifying packets with hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34–41, 2000.
  2. V. Srinivasan, S. Suri, and G. Varghese, “Packet classification using tuple space search,” SIGCOMM Comput. Commun. Rev., vol. 29, no. 4, p. 135–146, aug 1999. [Online]. Available: https://doi.org/10.1145/316194.316216
  3. B. Vamanan, G. Voskuilen, and T. N. Vijaykumar, “Efficuts: Optimizing packet classification for memory and throughput,” in Proceedings of the ACM SIGCOMM 2010 Conference, ser. SIGCOMM ’10. New York, NY, USA: Association for Computing Machinery, 2010, p. 207–218. [Online]. Available: https://doi.org/10.1145/1851182.1851208
  4. W. Li, X. Li, H. Li, and G. Xie, “Cutsplit: A decision-tree combining cutting and splitting for scalable packet classification,” in IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, 2018, pp. 2645–2653.
  5. N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “Openflow: Enabling innovation in campus networks,” SIGCOMM Comput. Commun. Rev., vol. 38, no. 2, p. 69–74, mar 2008. [Online]. Available: https://doi.org/10.1145/1355734.1355746
  6. B. Pfaff, J. Pettit, T. Koponen, E. J. Jackson, A. Zhou, J. Rajahalme, J. Gross, A. Wang, J. Stringer, P. Shelar, K. Amidon, and M. Casado, “The design and implementation of open vswitch,” in Proceedings of the 12th USENIX Conference on Networked Systems Design and Implementation, ser. NSDI’15. USA: USENIX Association, 2015, p. 117–130.
  7. S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ser. SIGCOMM ’03. New York, NY, USA: Association for Computing Machinery, 2003, p. 213–224. [Online]. Available: https://doi.org/10.1145/863955.863980
  8. Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, “Packet classification algorithms: From theory to practice,” in IEEE INFOCOM 2009, 2009, pp. 648–656.
  9. P. He, G. Xie, K. Salamatian, and L. Mathy, “Meta-algorithms for software-based packet classification,” in 2014 IEEE 22nd International Conference on Network Protocols, 2014, pp. 308–319.
  10. W. Li and X. Li, “Hybridcuts: A scheme combining decomposition and cutting for packet classification,” in 2013 IEEE 21st Annual Symposium on High-Performance Interconnects. IEEE, 2013, pp. 41–48.
  11. W. Li, T. Yang, O. Rottenstreich, X. Li, G. Xie, H. Li, B. Vamanan, D. Li, and H. Lin, “Tuple space assisted packet classification with high performance on both search and update,” IEEE Journal on Selected Areas in Communications, vol. 38, no. 7, pp. 1555–1569, 2020.
  12. S. Yingchareonthawornchai, J. Daly, A. X. Liu, and E. Torng, “A sortedpartitioning approach to fast and scalable dynamic packet classification,” IEEE/ACM Transactions on Networking, vol. 26, no. 4, pp. 1907–1920, 2018.
  13. A. Gaur, S. Radhakrishnan, A. Narasimhan, and M. Atiquzzaman, “On packet classification with multidimensional range trees,” in ICC 2024 - IEEE International Conference on Communications, 2024, pp. 1084– 1089.
  14. A. Narasimhan, S. Radhakrishnan, M. Atiquzzaman, and C. R. Subramanian, “High-speed packet classification: A case for approximate sorting,” in GLOBECOM 2022 - 2022 IEEE Global Communications Conference, 2022, pp. 5765–5770.
  15. A. Rashelbach, O. Rottenstreich, and M. Silberstein, “A computational approach to packet classification,” IEEE/ACM Transactions on Networking, vol. 30, no. 3, pp. 1073–1087, 2022.
  16. E. Bakopoulou, B. Tillman, and A. Markopoulou, “Fedpacket: A federated learning approach to mobile packet classification,” IEEE Transactions on Mobile Computing, vol. 21, no. 10, pp. 3609–3628, 2022.
  17. Z. Li, T. Wang, J. Liu, Y. Zhang, T. Ma, and K. Liu, “Tuplepick: A high stability packet classification based on neural network,” in 2024 IEEE 25th International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM), 2024, pp. 377–382.
  18. P. He, G. Xie, K. Salamatian, and L. Mathy, “Meta-algorithms for software-based packet classification,” in 2014 IEEE 22nd International Conference on Network Protocols, 2014, pp. 308–319.
  19. S. Rahul, “Improved bounds for orthogonal point enclosure query and point location in orthogonal subdivisions in r3,” in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’15. USA: Society for Industrial and Applied Mathematics, 2015, p. 200–211.