The week's pick
Random Articles
Reseach Article
A Novel Technique for Fast Parallel Packet Classification
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 76 - Number 4 |
| Year of Publication: 2013 |
| Authors: Balasaheb S. Agarkar, Uday V. Kulkarni |
10.5120/13235-0668
|
Balasaheb S. Agarkar, Uday V. Kulkarni . A Novel Technique for Fast Parallel Packet Classification. International Journal of Computer Applications. 76, 4 ( August 2013), 18-25. DOI=10.5120/13235-0668
Abstract
Packet classification is one of the most important enabling technologies for next generation network services. Four of the main challenges in the packet classification are increase in size of the classifier, link speed, amount of multimedia traffic, and number of media-rich and bandwidth intensive internet applications. Due to this there is a need of memory efficient and high throughput packet classification schemes. In this paper a novel technique for fast parallel packet classification (FPPC) is proposed. A recent paper [14] showed how to construct a hierarchical ?Tree-Trie?_? ?(TT?_?) search structure and a clustering algorithm that partitions a given classifier into a fixed number of clusters. This dramatically enhances memory efficiency and throughput. This idea is extended to address the more challenging problem of general packet classification. The hierarchical search results are passed on to the bloom filter for final classification. Also it is observed that in a large classifier many rules have very poor hit rate. If Top-N selection approach is used, without affecting minimum Quality of Service (QoS) requirements it is possible to reduce mean delay and increase the throughput. The simulation results shows that proposed scheme gives 22. 5% rise in the throughput and 5. 62% decrease in mean delay with slight decrease in memory efficiency as compared to Hierarchical Hybrid Search Structure (HHSS) scheme.
References
- David E. Taylor, "Survey & Taxonomy of Packet Clas-sification Techniques," Technical Report WUCSE-2004-24, Department of Computer Science and Engineering, Washington, May 2004.
- V. Srinivasan, S. Suri, G. Varghese, and M. Waldvogel, "Fast and Scalable Layer Four Switching," in ACM SIGCOMM, June 1998.
- V. Srinivasan, S. Suri, and G. Varghese, "Packet clas-sification using tuple space search," in ACM SIGCOMM, pp. 135–146, 1999.
- F. Baboescu, S. Singh, and G. Varghese, "Packet Clas-sification for Core Routers: Is there an alternative to CAMs?" in IEEE INFOCOM, 2003.
- P. Gupta and N. McKeown, "Packet Classification using Hierarchical Intelligent Cuttings," in Hot Intercon-nects VII, August 1999.
- S. Singh, F. Baboescu, G. Varghese, and J. Wang, "Packet Classification Using Multidimensional Cut-ting," in Proceedings of ACM SIGCOMM, August 2003. Karlsruhe, Germany.
- T. Y. C. Woo, "A Modular Approach to Packet Clas-sification: Algorithms and Results," in IEEE INFOCOM, March 2000.
- R. K. Montoye, "Apparatus for Storing "Don't Care"in Content Addressable Memory Cell. " United States Pa-tent 5,319,590, June 1994. HaL Computer Systems, Inc.
- Young-Deok Kim, Hyun-Seok Ahn, Suhwan Kim, and Deog-Kyoon Jeong, "A High-Speed Range-Matching TCAM for Storage-Efficient Packet Classification," IEEE Transactions on Circuits and Systems-I: Regular Papers, vol. 56, no. 6, June 2009.
- D. E. Taylor and J. S. Turner, "Scalable Packet Clas-sification using Distributed Crossproducting of Field La-bels," Tech. Rep. WUCSE-2004-38, Department of Computer Science and Engineering, Washington.
- J. van Lunteren and T. Engbersen, "Fast and scalable packet classification," IEEE Journal on Selected Areas in Communications, vol. 21, pp. 560–571, May 2003.
- Duo Liu, Zheng Chen, Bei Hua, Nenghai Yu and Xinan Tang, "High-Performance Packet Classification Al-gorithm for Multithreaded IXP Network Processor," ACM Transactions on Embedded Computing Systems, Vol. 7, no. 2, Article 16, February 2008.
- Yaxuan Qi, Lianghong Xu, Baohua Yang, Yibo Xue and Jun Li, "Packet Classification Algorithms: From Theory to Practice," IEEE INFOCOM 2009.
- O˜guzhan Erdem, Hoang Le and Viktor K. Prasanna, "Hierarchical Hybrid Search Structure for High Per-formance Packet Classification," in IEEE INFOCOM, 2012.
- Weirong Jiang and Viktor K. Prasanna, "Large-Scale Wire-Speed Packet Classification on FPGAs," in ACM, 2009.
- Yadi Ma and Suman Banerjee, "A Smart Pre-Classifier to Reduce Power Consumption of TCAMs for Multi-dimensional Packet Classification," in ACM, 2012.
- Alan Kennedy, Xiaojun Wang, Zhen Liu and Bin Liu, "Low Power Architecture for High Speed Packet Clas-sification," in ACM, 2008.
- Ho-Yu Lam, Donghan Wang and H. Jonathan Chao, "A Traffic-aware Top-N Firewall Approximation Al-gorithm," in the first International workshop on secu-rity in computers, networking and communications, 2011.
- Mahmood Ahmadi and Stephan Wong, "K-Stage Pipe-lined Bloom Filter for Packet Classification," in Interna-tional conference on computational science and engineer-ing, 2009.
- Network simulator, http://www. isi. edu/nsnam/ns
- D. E. Taylor and J. S. Turner. "ClassBench: A Packet Classification Benchmark," IEEE/ACM Transactions on Networking, vol. 15, no. 3, pp. 499-511, June 2007.
Index Terms
Keywords