International E-publication: Publish Projects, Dissertation, Theses, Books, Souvenir, Conference Proceeding with ISBN.  International E-Bulletin: Information/News regarding: Academics and Research

Packet Classification Algorithm Based on Geometric Tree by using Recursive Dimensional Cutting (DimCut)

Author Affiliations

  • 1Department of Computer Studies and Research, Symbiosis International University, Pune, INDIA
  • 2 Allana Institute of Management Science, Pune University, Pune, INDIA

Res. J. Recent Sci., Volume 2, Issue (8), Pages 31-39, August,2 (2013)


The Packet classification is a key function of the firewalls and routers. Internet firewalls, routers and service providers perform different operations at different flows. With the increasing demands on router performance, there is a need for algorithms that can classify packets quickly with minimal storage requirements. This paper presents a heuristic, called Packet Classification Algorithm Based on Geometric Tree by using Recursive Dimensional Cutting (DimCut), which exploits the structure found in classifiers. It, like the previously well-known algorithm, HiCutsis based on a decision tree structure. After examinationDimCut algorithm, to classify packets based on five header fields, it is found that the algorithm can classify packets quickly. Our proposal extends HiCuts with new heuristics ideas and new implementing techniques while retaining HiCuts’ basic framework. The DimCut algorithm has two separated levels, pre-processinglevel (tree construction and making index table) and search level. The algorithm provides a full description of the chief data structures and tuneable parameters. We explain details that describe the pre-processing algorithm and the search process, also provide the source code that permits the actual implementation.


  1. Song H. and Turner J., Toward Advocacy-Free Evaluation of Packet Classification Algorithms, in IEEE Transactions on Computers, 60, (2011)
  2. Bauer M., Paranoidpenguin: Using Iptables for local security, in Linux Journal, Available at, August (2002)
  3. Napier D., IPTables/NetFilter – Linux’s next generation stateful packet filter, in Sys Admin - Security: The Journal for UNIX Systems Administrators, 10(12), 8, 10, 12, 14, 16, (2001)
  4. Woo T., A Modular Approach to Packet Classification: Algorithms and Results, in Proceedings of INFOCOM 2000, Nineteenth Annual Joint Conference of the IEEEComputer and Communications Societies, , 26-30 (2000)
  5. Decasper D., Dittia Z., Pantlkar G. and Plattner Scottberg B., Router plugins: A software architecture for next generation routers, in Proceedings of ACM Sigcomm, 191-202, Vancouver, Canada, (1998)
  6. Srinivasan V., Varghese G., Suri S. and Waldvogel M., Fast and scalable layer four switching, in Proceedings of ACM Sigcomm '98 , 191-202,Vancouver, Canada, (1998)
  7. Stihdis D. and Lakslunan T.V., High-speed policy-based packet forwarding using efficient multi-dimensional range matching, in Proceedings of ACM Sigcomm, 203-214, Vancouver, Canada, August 31 - September 4 (1998)
  8. Singh S., Baboescu F., Varghese G. and Wang J., Packet Classification using Multidimensional Cutting, in Proceedings of the ACM SIGCOMM ’03 Conference on Applications, Tech., Archi., and Protocols for Computer Communication (SIGCOMM ’03), 213 – 224(2003)
  9. Gupta P. and McKeown N., Packet Classification Using Hierarchical Intelligent Cuttings, in Proceedings of IEEE Symp. High Performance Interconnects (HotI), 7, (1999)
  10. Vamanan B., Voskuilen G., Vijaykumar T.N., EffiCuts: optimizing packet classification for memory and throughput, in Proceedings of Proceedings of the ACM SIGCOMM 2010 conference on SIGCOMM, New Delhi, India, (2010)
  11. Taylor D., Survey and Taxonomy of Packet Classification Techniques, in Proceedings of ACM Computing Surveys (CSUR), 37(3), 238 - 275 (2005)
  12. Ahmadi M. and Wong, S., Modified Collision Packet Classification using Counting Bloom Filter in Tuple Space, in Proceedings of International Conference on Parallel and Distributed Computing and Networks (PDCN 2007) Innsbruck, Austria, (2007)
  13. Gupta P. and McKeown N., Packet Classification on Multiple Fields, in proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication in ACM SIGCOMM ’99, 147-160 (1999)
  14. Baboescu F. and Varghese G., Scalable Packet Classification, in Proceedings of the ACM SIGCOMM, 199–210 (2001)
  15. Feldmann A. and Muthukrishnan S., Tradeoffs for Packet Classification, in Proceedings of the IEEE INFOCOM, Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, , 1193–1202 (2000)
  16. Waldvogel M., Varghese G., Turner J. and Plattner B., Scalable High Speed IP Routing Lookups, in Proceedings of the ACM SIGCOMM, 25-38 (1997)
  17. Srinivasan V. and Varghese G., Fast Address Lookups Using Controlled Prefix Expansion, in Proceedings of the ACM Trans. Computer Systems, 17, 1-40 (1999)
  18. Eatherton W., Varghese G. and Dittia Z., Tree Bitmap: Hard- ware/Software IP Lookups with Incremental Updates, ACM SIGCOMM Computer Comm. Rev., 34(2), 97-122 (2004)
  19. Song H., Turner J. and Lockwood J., Shape Shifting Tries for Faster IP Lookup, in Proceedings of the IEEE Int’l Conf. Network Protocols (ICNP’05), (2005)
  20. Song H., Turner J. and Dharmapurikar S., Packet Classification Using Coarse-Grained Tuple Spaces, in Proceedings of the ACM/IEEE Symp, Architecture for Networking and Comm., Systems (ANCS ’06), 41- 50 (2006)
  21. Srinivasan V., Suri S. and Varghese G., Packet Classification Using Tuple Space Search, in Proceedings of the ACM SIGCOMM’99, 135-146 (1999)