Dissertation > Excellent graduate degree dissertation topics show

High Performance Packet-classification Algorithm Study

Author: ZhangQingHong
Tutor: HuoHongWei
School: Xi'an University of Electronic Science and Technology
Course: Computer Software and Theory
Keywords: Packet-classification Multi-pattern matching Tuple Trie
CLC: TP393.01
Type: Master's thesis
Year: 2008
Downloads: 86
Quote: 1
Read: Download Dissertation

Abstract


Nowadays, more and more PCs link to the Internet and this makes Internet data flow growing much faster than any time before. Consequently, good quality of Internet services much more difficulty to obtain. With the rapid development of fiber and DWDM technology, the networks transmission rate is satisfying basically. As a basic equipment of networks, router becomes a bottle neck of the Internet now and the basic technology of router is packet classification.In this paper, we first do a systemic, detail research on almost all the classical packet classification algorithms and analyze the time and space request of all the algorithms and compare on time/space consumption between them. Our research shows: the most of the classical packet classification algorithms only suit for one or to type of matching. Nowadays, the packet filter becomes to be more and more complexity. One filter usually comprises longest prefix matching, accurate matching, rang matching and so on. That one algorithm fits all the type of matching remains a problem.As to the problem above, we introduce a new algorithm named multidimensional subsection on field algorithm and this algorithm uses strategy of filter-division on matching type. Concretely says, this algorithm deals different matching field in one rule with different strategy. In our new algorithm, we use Tuple Space Search algorithm for the longest prefix matching parts, hashing table for accurate matching parts and develop state transmission tree algorithm for the last parts of the rule. We introduced the parallel algorithm soon. Finally we coded in C language for our algorithm for verifying.It is obvious that our algorithm can fit various filters well. We analyzed the time and space requirement of the algorithm. The result shows that time complexity is O( log n) and space complexity is O(N), the n is the number of the Tuple, the N is the number of rule and n<N.

Related Dissertations

  1. Research of Multiple Emails Automatic Summarization,TP391.1
  2. Zombie control behavior recognition and detection method of,TP393.08
  3. Express different preferences based on group decision making Consistency,C934
  4. Cloud computing task -dependent mechanism of dynamic parallel scheduling,TP3
  5. Phone number classification softswitch platform,TN915.05
  6. Research on Distributed Packet Classification Algorithms with Scalability and High Performance,TP393.06
  7. Research on TCAM Based Packed Classification,TP393.08
  8. Research and Application of Multi-Pattern Matching Engine Based on Bloom Filter,TP393.08
  9. Research and Implementation on Optimization Technology of Packet Classification Based on Netfilter,TP393.08
  10. Study on Clustering Method Based on Linguistic Information,O159
  11. Semantics Based Top-k Keyword Search Technology in Relational Databases,TP311.13
  12. Research on the Evaluation Method of Trust between Virtual Enterprise Partners,F224
  13. Research of Network Content Monitoring Based on Parallel Protocol Analysis,TP393.08
  14. Research and Implementations of a Search Model Based on the Fusion of DB and IR,TP311.13
  15. K neighbors phased approach in the wireless LAN intrusion detection research,TN925.93
  16. The Research on Extracting Bilingual Translation Tuples from Web,TP391.2
  17. Packet classification algorithm based on the the NDIS intermediate Windows platform under,TP393.08
  18. Meat processing enterprises of food safety management system,F203
  19. Support fast incremental update packet classification algorithm,TP18
  20. Research and Implementation of Packet Classification Technique Based on Varied Step Trie,TP393.07
  21. Multidimensional Packet Classification Algorithm Research and Simulation,TP301.6

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