CNIR - V05, Issue I

A SCALABLE APPROACH FOR PACKET CLASSIFICATION USING RULE-BASES PARTITION

Mr. S J Wagh ¹ and Dr. T. R. Sontakke ²

[1] Assistant Professor in Information Technology, Army Institute of Technology. (Affiliated to University of Pune, MS)

[2] Director & Professor, S.G.G.S. College of Engineering and Technology, Vishnupuri, Nanded-431603 MS.

Abstract:

This paper focuses on a new direction for packet classification, which can substantially improve the performance of a classifier by decreasing the rule-base lookup latency. The classifier partitions the rule-base into smaller independent sub-rule bases by using the hash key of hashing technique. We apply the concept of maximum entropy to select the hash key for optimal partitioning of rule-base. We performed the detailed simulations of our proposed algorithm on synthetic rule-bases of size 1K to 200K entries using packet traces. From the simulation results we found that the algorithm significantly outperforms by reducing the size of a rule-base by more than four orders of magnitude with just two-levels of partitioning. Both the space and time complexity of the algorithm exhibit linearity in terms of the size of a rule-bases. The proposed idea suggests a good scalable solution for the packet classification with a large rule-base.

Keywords:  Packet classification, scalability, Lookup latency, Rule-bases, Space & Time complexity

Biographies:

Mr. S J Wagh is an Assistant professor in Dept. of Information Technology at Army Institute of Technology, Pune. He had completed his graduation in computer Engineering from  SGGS College of Engineering & Technology, Nanded in 1996 , Post graduation in Computer Engineering from Government College of Engineering Pune in 2003 (Affiliated to University of Pune)  He had published various research Papers & He is a Member of Various professional bodies. . His main research interests include Computer networks & Internet, distributed Systems and Algorithms for router to manage traffics in Networks.

Dr. T R Sontakke, currently Director & Professor at SGGS College of Engineering & Technology, Nanded. He had obtained his B. Tech degree in 1972 in Electronics, M. Tech. degree in Electronics (Power) & Ph. D in Power in1984 from Indian Institute of Technology, Bombay. He had published various research Papers, He had guided number of research students & He is a Member of Various professional bodies. His main Subject interests include Operating Systems, System Programming & Computer Networks.

(Full Paper 455KB)