Splay Tree and Skip List: Effectiveness and Analysis in Internet Packet Categorization

Authors

  • Prof. Sumit S Shevtekar  Department of Computer Engineering, Pune Institute of Computer Technology, Pune, Maharashtra, India
  • Harish Sumant  Department of Computer Engineering, Pune Institute of Computer Technology, Pune, Maharashtra, India
  • Abhijit Suryawanshi  Department of Computer Engineering, Pune Institute of Computer Technology, Pune, Maharashtra, India

DOI:

https://doi.org//10.32628/CSEIT228623

Keywords:

Skip list, Splay tree, Decision Tree, Packet classification, Data Structures

Abstract

Internet packet traffic has expanded rapidly as a result of the rising number of world wide web users and the amount of information sent by software applications which has highlighted the necessity of speeding up the processing required in network systems. Packet categorization is among the strategies utilized across network architecture. Skip List and Splay Tree, two of the most important data structures used in decision trees, will be investigated for their effectiveness in packet categorization in this study. The period of packet identification, the amount of memory accesses, and memory consumption per event make up our performance criterion. These criteria are used to judge whether data structure, between Skip List and Play Tree, is the preferable one to use for accurate packet classification.

References

  1. Efficient Packet Classification using Splay Tree Models Srinivasan, T., Nivedita, M. Mahadevan, V.: Efficient Packet Classification Using Splay Tree Models. IJCSNS International Journal of Computer Science and Network Security 6(5), 28–35 (2020)
  2. Khezrian N, Abbasi M.2019. Comparison of the performance of skip lists and splay trees in classification of internet packets.PeerJ Computer Science 5:e204
  3. Analysis of an optimized search algorithm for skip lists. Theoretical Computer Science.2018 by Kirschenhofer, Mart´ınez Prodinger (2018) Kirschenhofer P, Mart´ınez C, Prodinger HJTCS.
  4. Efficient memristor-based architecture for intrusion detection and high-speed packet classification by V Bontupalli , C Yakopcic, HasanR,TahaTM. 2021. ACM Journal on Emerging Technologies in Computing Systems 14(4):41.
  5. Fast packet classification algorithm for network-wide forwarding behav- iors by Inoue T, Mano T, Mizutani K, Minato S-I, Akashi O. 2018. : A fast and scalable IP lookup engine for GPU-based softwarerouters by Li Y, Zhang D, Liu AX, Zheng J. 2013 In: The proceedings of the ninth ACM/IEEE conference on networking and communications system designs. Piscataway: IEEE Press.
  6. A survey and classification of Several different packet classifying techniques by B. Nagpal, N. Singh, N. Chauhan, and R. Murari. 2015.

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2022-12-30

Issue

Volume 8, Issue 6, November-December-2022

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Prof. Sumit S Shevtekar, Harish Sumant, Abhijit Suryawanshi, " Splay Tree and Skip List: Effectiveness and Analysis in Internet Packet Categorization, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 8, Issue 6, pp.285-294, November-December-2022. Available at doi : https://doi.org/10.32628/CSEIT228623