Blog
About

0
views
0
recommends
+1 Recommend
1 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Comparison of the performance of skip lists and splay trees in classification of internet packets

      1 , 2

      PeerJ Computer Science

      PeerJ

      Read this article at

      ScienceOpenPublisher
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Due to the increasing number of Internet users and the volume of information exchanged by software applications, Internet packet traffic has increased significantly, which has highlighted the need to accelerate the processing required in network systems. Packet classification is one of the solutions implemented in network systems. The most important issue is to use an approach that can classify packets at the speed of the network and show optimum performance in terms of memory usage. In this study, we evaluated the performance in packet classification of two of the most important data structures used in decision trees, i.e. the skip list and splay tree. Our criteria for performance were the time of packet classification, the number of memory accesses, and memory usage of each event. These criteria were tested by the ACL and IPC rules with different numbers of rules as well as by different packet numbers. The results of the evaluation showed that the performance of skip lists is higher than that of splay trees. By increasing the number of classifying rules, both the difference in the speed of packet classification and the superiority of the performance of the skip list over that of the splay tree become more significant. The skip list also maintains its superiority over the splay tree in lower memory usage. The results of the experiments confirm the scalability of this method in comparison to the splay tree method.

          Related collections

          Most cited references 23

          • Record: found
          • Abstract: not found
          • Article: not found

          Self-adjusting binary search trees

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Skip lists: a probabilistic alternative to balanced trees

             William Pugh (1990)
              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Packet classification using tuple space search

                Bookmark

                Author and article information

                Journal
                PeerJ Computer Science
                PeerJ
                2376-5992
                2019
                July 15 2019
                : 5
                : e204
                Affiliations
                [1 ]Computer Engineering Faculty, Sharif University of Technology, Tehran, Iran
                [2 ]Department of Computer Engineering, Engineering Faculty, Bu-Ali Sina University, Hamedan, Iran
                Article
                10.7717/peerj-cs.204
                © 2019

                https://creativecommons.org/licenses/by/4.0/

                Product
                Self URI (article page): https://peerj.com/articles/cs-204

                Comments

                Comment on this article