Home| Contact Us| New Journals| Browse Journals| Journal Prices| For Authors|

Print ISSN:
Online ISSN:


  About JDP
  DLINE Portal Home
Home
Aims & Scope
Editorial Board
Current Issue
Next Issue
Previous Issue
Sample Issue
Upcoming Conferences
Self-archiving policy
Alert Services
Be a Reviewer
Publisher
Paper Submission
Subscription
Contact us
 
  How To Order
  Order Online
Price Information
Request for Complimentary
Print Copy
 
  For Authors
  Guidelines for Contributors
Online Submission
Call for Papers
Author Rights
 
 
RELATED JOURNALS
Journal of Digital Information Management (JDIM)
Journal of Multimedia Processing and Technologies (JMPT)
International Journal of Web Application (IJWA)

 

 
Journal of Data Processing
 

Increasing the Efficiency of Packet Classifiers with Closed Descriptions
Elizaveta F. Goncharova, Sergei O. Kuznetsov
National Research University Higher School of Economics & Moscow, Russia
Abstract: Efficient representation of packet classifiers has become a significant challenge due to the rapid growth of data stored and processed in the forwarding, or routing, tables. In our work we propose two algorithms for reducing the size of forwarding tables both in length and width by the deletion of redundant bits and unreachable rules based on FCA analysis. We consider the task of transferring the forwarding packet to the correct destination as the task of multinomial classification. Thus, the process of reducing the forwarding table size corresponds to feature selection procedure with slight modifications. The presented techniques are based on closed descriptions and decision trees. The main challenge in applying decision trees to the task is processing the overlapping rules. To overcome this challenge we propose to employ concept-based hypotheses to delete unreachable actions assigned to the overlapping rules. The experiments were performed on data generated by the ClassBench software. The proposed approach results in significant decrease in bits in the forwarding tables as features.
Keywords: FIB Optimization, Concept-based Hypotheses, Decision Tree Increasing the Efficiency of Packet Classifiers with Closed Descriptions
DOI:https://doi.org/10.6025/jdp/2020/10/1/30-39
Full_Text   PDF 386 KB   Download:   669  times
References:

[1] Gupta, P., McKeown, N. (2000). Classifying packets with hierarchical intelligent cuttings. IEEE Micro 20 (1) 34-41.
[2] Singh, S., Baboescu, F., Varghese, G., Wang, J. (2003). Packet classification using multidimensional cutting. In: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, 213-224. ACM.
[3] Kogan, K., Nikolenko, S. I., Rottenstreich, O., Culhane, W., Eugster, P. (2015). Exploiting order independence for scalable and expressive packet classification. IEEE/ACM Transactions on Networking, 24 (2) 1251-1264.
[4] Kogan, K., Nikolenko, S., Eugster, P., Ruan, E. (2014). Strategies for mitigating TCAM space bottlenecks. In: 2014 IEEE 22nd Annual Symposium on High-Performance Interconnects, p. 25-32. IEEE.
[5] Ganter, B., Kuznetsov, S. (2001). Pattern Structures and Their Projections, Proceedings 9th International Conference on Conceptual Structures, ICCS’01, G. Stumme and H. Delugach, Eds., Lecture Notes in Artificial Intelligence, 2120, 129-142.
[6] Kaytoue, M., Kuznetsov, S. O., Napoli, A., Duplessis, S. (2011). Mining gene expression data with pattern structures in formal concept analysis. Information Sciences, 181 (10) 1989-2001.
[7] Kuznetsov, S. O. (1999). Learning of simple conceptual graphs from positive and negative examples. European Conference on Principles of Data Mining and Knowledge Discovery. Springer, Berlin, Heidelberg, 1999, p. 384-391.
[8] Kuznetsov, S. O.(2001). Machine learning on the basis of formal concept analysis. Automation and Remote Control, 62 (10) 1543-1564
[9] Finn, V. K. (1991). Plausible reasoning in systems of JSM type. Itogi Nauki i Tekhniki, Seriya Informatika, 1991 [in Russian].
[10] Breiman, L., Friedman, J. H., Olshen, R. A., Stone, C. J. Classification and regression trees. Belmont, CA: Wadsworth. International Group, 432 (1984).
[11] ClassBench: A packet classification benchmark, http://www.arl.wustl.edu/classbench/.


Home | Aim & Scope | Editorial Board | Author Guidelines | Publisher | Subscription | Previous Issue | Contact Us |Upcoming Conferences|Sample Issues|Library Recommendation Form|

 

Copyright © 2011 dline.info