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

Survey on Multi Field Packet Classification Techniques

    ,

Author Affiliations

  • 1Faculty of Electrical Engineering, Universiti Teknologi Malaysia, UTM Skudai, Johor 81310, MALAYSIA
  • 2 Foundation of Technical Education, Baghdad, IRAQ

Res. J. Recent Sci., Volume 4, Issue (2), Pages 98-106, February,2 (2015)

Abstract

The latest research frontier on next-generation routers targets at more integration of advanced networking capabilities and functions including firewall operations, memory access control, quality of service (QoS) management, policy routing, and traffic billing. To realize such services, the router should be able to categorize the packets into different flows depending on already defined rule set called classifier, which contains a range of values of different fields in the packet header. The stated functions are defined as multi field classification. The increase in link rate and the size of classifier creates the challenge in multi field packet classification in the design of faster routers. We present a survey on various algorithms and architectures proposed for multi field packet classification that achieves higher throughput.

References

  1. Casado M., Koponen T., Moon D. and Shenker S., Rethinking packet forwarding hardware, in Proceeding of HotNets, 1-6, (2008)
  2. Gupta P. and McKeown N., Packet classification using hierarchical intelligent cuttings, in Proceeding of HOT Interconnects, VII, 34-41, (1999)
  3. Medhi D. and Ramasamy K., Network Routing Algorithms, Protocols, and Architectures, San Francisco, Morgan Kaufmann, (2007)
  4. Open Flow Foundation, Open Flow Switch Specification, Version 1.0.0, Available at http://www.openflowswitch.org/ documents/openflow-spec-v1.0.0.pdf, (2009)
  5. Chao H.J., Next generation routers, in Proceedings of the IEEE, 90, 1518-1558 (2002)
  6. Taylor D. E., Survey and Taxonomy of Packet Classification Techniques, ACM Computing Surveys, 3(37), 238-275 (2005)
  7. Gupta P. and McKeown N., Algorithms for packet classification, IEEE Network, 2(15), 24–32 (2001)
  8. Gupta P., Packet classification on multiple fields, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, 147-160 (1999)
  9. Lakshman T.V. and Stiliadis D., High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching, In ACM SIGCOMM, 203-214, (1998)
  10. Baboescu F. and Varghese G., Scalable packet classification, IEEE/ACM Transactions onNetworking, 13, 2-14 (2005)
  11. Taylor D.E. and Turner J.S., Scalable packet classification using distributed crossproducing of field labels, 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings IEEE , 269-280, (2005)
  12. Gupta P. and McKeown N., Classifying packets with hierarchical intelligent cuttings, Micro IEEE , 20, 34-41, (2000)
  13. Singh S., Baboescu F., Varghese G. and Wang J., Packet Classification Using Multidimensional Cutting, In Proceedings of ACM SIGCOMM, 213-224, (2003)
  14. Luo Y., Xiang K. and Li S., Acceleration of decision tree searching for IP traffic classification, in Proceeding ANCS, 40–49, (2008)
  15. Vamanan B., Voskuilen G. and Vijaykumar T. N., EffiCuts: optimizing packet classification for memory and throughput, ACM SIGCOMM Computer Communication Review – SIGCOMM, 10, 207-218, (2010)
  16. Lim, H.,Lee N., Jin G.,Lee J., Choi Y. and Yim C., Boundary Cutting for Packet Classification, IEEE/ACM Transactions onNetworking,(2013)
  17. Srinivasan V., Suri S., and Varghese G., Packet classification using tuple space search, in Proceeding ACM SIGCOMM, 99, 135–146, (1999)
  18. Taylor D.E. and Turner J.S., ClassBench: a packet classification benchmark, 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2068-2079 , (2005)
  19. Shah, D. and Gupta P., Fast updating algorithms for TCAM, Micro IEEE, 21, 36-47 (2001)
  20. Liu H. , Routing table compaction in ternary CAM, Micro IEEE, 22, 58-64 (2002)
  21. Liu H., Efficient mapping of range classifier into ternary-CAM, in 10th Symposium on High Performance Interconnects, 95-100, (2002)
  22. Panigrahy R. and Sharma S., Reducing TCAM power consumption and increasing throughput, in 10th Symposium on High Performance Interconnects, 107-112, (2002)
  23. Kasai G., Takarabe Y., Furumi K. and YonedaM., 200MHz/200MSPS 3.2W at 1.5V Vdd, 9.4Mbits ternary CAM with new charge injection match detect circuits and bank selection scheme, Custom Integrated Circuits Conference, Proceedings of the IEEE, 387-390, (2003)
  24. Van Lunteren J. and Engbersen T., Fast and scalable packet classification, IEEE Journal on Selected Areas in Communications, 21, 560-571 (2003)
  25. Spitznagel E., Taylor D. and TurnerJ., Packet classification using extended TCAMs, in Proceeding 11th IEEE International Conference on Network Protocols, 120-131 (2003)
  26. Song H. and Lockwood J., Efficient Packet Classification for Network Intrusion Detection using FPGA, in Proceeding of FPGA, 238–245, (2005)
  27. Lakshminarayanan .K, Rangarajan A. and Venkatachary S., Algorithms for advanced packet classication with ternary CAMs, in ACM SIGCOMM, 193-204, (2005)
  28. Chang Y., Chien S., Lin S. and Hsieh S., Efficient Gray-Code-Based Range Encoding Schemes for Packet Classification in TCAM, , IEEE/ACM Transactions on Networking , 21,.1201-1214, (2013)
  29. Kim Y., Ahn H., Kim S. and Jeong D., A High-Speed Range-Matching TCAM for Storage-Efficient Packet Classification, IEEE Transactions onCircuits and Systems, 56, 1221-1230 (2009)
  30. He X., Peddersen J. and ParameswaranS., LOP_RE: Range encoding for low power packet classification, IEEE 34th Conference on Local Computer Networks, 137-144 (2009)
  31. Jedhe G.S., Ramamoorthy A. and Varghese K., A Scalable High Throughput Firewall in FPGA, 16th International Symposium on Field-Programmable Custom Computing Machines, 43-52, (2008)
  32. Taylor D.E. and Turner J.S., Scalable packet classification using distributed crossproducing of field labels, 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings IEEE , 269-280, (2005)
  33. Kennedy A., Wang X., Liu Z. and Liu B., Low Power Architecture for High Speed Packet Classification, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, 131-140, (2008)
  34. Nikitakis A., and Papaefstathiou L., A Memory-Efficient FPGA-based Classification Engine, in 16th International Symposium on Field-Programmable Custom Computing Machines, 53-62, (2008)
  35. Jiang W. and Prasanna V.K, Large-Scale Wire-Speed Packet Classification on FPGAs, Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, 219-228, (2009)
  36. Puš V. and Korenek J. Fast and Scalable Packet Classification Using Perfect Hash Functions, Proceedings of the ACM/SIGDA international symposium on Field programmable gate arrays, 229-236, (2009)
  37. Antichi G., Di Pietro A., Giordano S., Procissi G., Ficara, D. and Vitucci F., On the use of compressed DFAs for packet classification, 15th IEEE International Workshop on Computer Aided Modeling, Analysis and Design of Communication Links and Networks, 21-25, (2010)
  38. Chang Y.K, Lin Y.S and Su C.C, A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification, 18th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines, 215-218, (2010)
  39. McKeown N., Anderson T., Balakrishnan H., Parulkar G., Peterson L., Rexford J., Shenker S.and Turner J., OpenFlow: Enabling Innovation in Campus Networks, ACM SIGCOMM Computer Communication Review, 69-74, (2008)
  40. Jiang W., and Prasanna V.K, Scalable Packet Classification on FPGA, IEEE Transactions On Very Large Scale Integration (VLSI) systems, 20, 1668-1680, (2012)
  41. Fong J., Wang X., Qi Y., Li J. and Jiang W., Para Split : A Scalable Architecture on FPGA for Terabit Packet Classification, IEEE 20th Annual Symposium on High-Performance Interconnects, 1-8, (2012)
  42. Ohlendorf R., Meitinger M., Wild T. and Herkersdorf A.,A Packet Classification Technique for On-Chip Processing Path Selection, Technische Universität München Arcisstrasse 21 80290 Munich, Germany, Le H., Jiang W. and Prasanna V.K., Scalable high-throughput SRAM-based architecture for IP-lookup using FPGA, International Conference on Field Programmable Logic and Applications, 137-142, (2008)
  43. Papaefstathiou I. and Papaefstathiou V., Memory-Efficient 5D Packet Classification At 40 Gbps, 26th IEEE International Conference on Computer Communications,1370-1378, (2007)
  44. Taylor D.E. and Turner J.S., ClassBench: a packet classification benchmark, 24th Annual Joint Conference of the IEEE Computer and Communications Societies,2068-2079, (2005)