Dissertation > Excellent graduate degree dissertation topics show

The Research of Fast Packet Classification Algorithm

Author: PanDeng
Tutor: ZhangDaFang
School: Hunan University
Course: Software Engineering
Keywords: Packet classification Trie tree Binary -level search Independent set
CLC: TP393.08
Type: Master's thesis
Year: 2009
Downloads: 56
Quote: 0
Read: Download Dissertation

Abstract


With the rapid development of network technology, as well as an endless stream of network applications, the Internet users on the network service reliability, security, diversity deeper aspirations. Routers need to provide network services to meet different needs of different users, such as packet filtering firewall, traffic accounting, differentiated services, QoS. In order to support these different services, the router must be fast packet classification processing. Fast packet classification algorithm has become a key technology for high-speed routers, is to avoid the router to become the key to network performance bottlenecks. This paper studied the many different types of packet classification algorithm based on binary-level search-based packet classification algorithm and packet classification algorithm based on independent collection optimization and improvement, and improve the running speed of the algorithm, and gives a comparative experiment results. The binary hierarchical search algorithm (BSOL, Binary Search On Levels) in a time-efficient packet classification algorithms. However, its core idea is for Terry tree (Trie) each layer to create a hash table, so when the hash load factor large or hash conflict, would seriously affect the efficiency. To solve this problem, this article by introducing Bloom filters, proposed a new improved algorithm. Improved the level of a binary search algorithm will Trie tree each layer to establish a Bloom filter first before making hash lookup Broome query operators, provides protection in the hash load factor greater still having a good performance. Simulation results show that the hit rate of the data packet is less than 90% and hash the improved algorithm in the loading factor of the case of larger at run-time to than BSOL algorithm. Based on the independent set (IS, Independent Sets) algorithm is a space efficient algorithm, which only need to be processed to the beginning of the rule interval. However, in the process of building a collection of independently algorithms lack the special consideration of the priority rules, so in the the linear packet matching process will affect the efficiency of the implementation of the algorithm, this paper the IS algorithm has been improved for this shortcoming, and put forward a The independent collection algorithm kinds prioritize. The independent collection algorithm can guarantee improved online matching process, the first packet matching rule is the eventual adoption of the rules, no longer need to traverse the entire rule index table. Simulation results show that the improved algorithm running time is better than the IS algorithm. This article also pointed out that a the IS algorithm dynamically updated to create a new the independent collection too frequent shortcomings A through segmentation rules to improve storage efficiency improvement assumption.

Related Dissertations

  1. Phone number classification softswitch platform,TN915.05
  2. Study on Dynamic Spectrum Allocation of Joint Power Control in Cognitive Radio Networks,TN925
  3. Research on Distributed Packet Classification Algorithms with Scalability and High Performance,TP393.06
  4. Research on TCAM Based Packed Classification,TP393.08
  5. Research and Implementation on Optimization Technology of Packet Classification Based on Netfilter,TP393.08
  6. Spectrum Allocation Based on Graph Theory in Cognitive Radio Networks,TN925
  7. Extremal Polyphenyl Chains Concerning κ-matchings and κ-independent Sets and Vertex PI Indices of Some Sums of Graphs,O157.5
  8. An Research on Mining Frequent Itemsets Algorithm Based on Titled-time Window,TP311.13
  9. Study on Some Theories of DNA Computing,TP301.6
  10. The Independents Set of Higher Vocational Normal Education Colleges Teachers Team Construction Research,G715.1
  11. Design on TRIE-Based Soft-forword Route Lookup Module,TP393.02
  12. Packet classification algorithm based on the the NDIS intermediate Windows platform under,TP393.08
  13. Support fast incremental update packet classification algorithm,TP18
  14. Research and Implementation of Packet Classification Technique Based on Varied Step Trie,TP393.07
  15. Multidimensional Packet Classification Algorithm Research and Simulation,TP301.6
  16. Research on IPv6 Packet Classification Algorithm Based on Flow Label,TP393.04
  17. The Design and Realization of Packet Classification Based on Flow Label in IPv6,TP393.04
  18. Research and Implementation of Quick Identification for Application Layer Protocols,TP393.04
  19. Router-based Lawful Interception Implementation and Entire Network-based Monitoring Task Allocation Research,TN915.06
  20. Fast Packet Classification Algorithm,TP393.01
  21. Research on High Performance Packet Classification Based on FPGA,TN791

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Computer network > General issues > Computer Network Security
© 2012 www.DissertationTopic.Net  Mobile