Dissertation > Excellent graduate degree dissertation topics show

The Research of High-performance Multi-dimensional Packet Classification Algorithm

Author: ZhaoZuoZuo
Tutor: XieZuo
School: Hunan University
Course: Computer Science and Technology
Keywords: packet classification counting bloom filter hash table tuple space bitmap
CLC: TP393.02
Type: Master's thesis
Year: 2010
Downloads: 50
Quote: 0
Read: Download Dissertation


With the rapid development of network technology and the emerging network applications, internet users have made deeper demands on the network service reliability, security and diversity. The routers need to provide diverse services such as firewalls, traffic billing, traffic control, differentiated services and QoS to satisfy different users. In order to support these new network services, the traditional one-dimensional packet classification algorithm which matching the packets by destination address can not meet the new various demands and the routers need to process multi-dimensional packet classification by the multi-field information from the header of data, such as the data packets of five-tuple (source IP, destination IP, source port, destination port, protocol). Today, research has shown that the rapid progress of Internet is continuously posing great demands and challenges on the multi-dimensional packet classification algorithm performance. It requires not only high matching speed, low memory occupation, but also the dynamic update and scalability performance for algorithms. Therefore, the research on the high-performance multi-dimensional packet classification algorithm is the necessary requirement of the large-scale and high-speed network. In this paper, we proposed two high-performance multi-dimensional packet classification algorithms, one belongs to software algorithm, and another belongs to hardware algorithm. As follows:Aspects of the software algorithm, we proposed a high-performance two-dimensional packet classification algorithm called TB (Joint Tuple Space and Bitmap). From dimensions decomposition idea, TB combined tuple space and bitmap technology to design and implement. TB first processed one-dimension matching for SIP and DIP respectively, then used cross-combination method to form tuple space access route, and also reduced the number of tuple space to access further by bitmap filtering technique. Compared to traditional tuple space algorithm, the structure of TB is clear, concise and easy to implement, has better time and space performance, easier to update, and also has a better scalability. The experimental results show that TB saves 35.1% of the space requirement than RSFR and the number of average memory accesses lower than RSFR 26.6%.Aspects of the hardware algorithm, we proposed an efficient multi-dimensional packet classification algorithm called CBHT(Counting Bloom filter and Hash Table). Considering the aggregation property of the rules which a packet matched, CBHT combined counting bloom filter and hash table to design and implement. Based on the aggregation property, for five-dimensional packet classification, we first got the small-scale rule set which matching the IP address using counting bloom filter. In this limited rule set we processed search on the other three dimensions. CBHT improves traditional structure of the hardware algorithm by considering the aggregation property, also improved the speed of packet matching effectively and supports rule set’s dynamic update. We use Stanford University’s PALAC platform to assess the performance of CBHT algorithm, the experimental results show that CBHT has better time performance, save hardware resources, and support rule set’s dynamic update effectively.

Related Dissertations

  1. One snapshot technology research and implementation,TP274
  2. SSD controller wear leveling algorithm,TP333.35
  3. Phone number classification softswitch platform,TN915.05
  4. Monte Carlo program point energy nuclear data processing method research and Optimization,TL329.2
  5. Research on Distributed Packet Classification Algorithms with Scalability and High Performance,TP393.06
  6. Research on TCAM Based Packed Classification,TP393.08
  7. Research and Implementation on Optimization Technology of Packet Classification Based on Netfilter,TP393.08
  8. RETE-based HLA Distributed Data Distribution Management Research and Implementation,TP391.9
  9. A Data Sorting and Entities Joining Algorithm in Relational Database Management Systems,TP311.13
  10. Design and Study of Autonomous Download System Based on Embedded Platform,TP311.52
  11. Improving the P2P Resource Locating Methods Based on Kademlia,TP393.02
  12. The GDI Graphics Engine and Print Principle and Realization under Windows 2k or XP,TP316.7
  13. Research and Application of Three-Dimension Area Rainfall Analytic Technique,TP391.41
  14. Character recognition technology based on BP neural network,TP391.41
  15. Frequent Pattern Mining Algorithm Research for Data Stream,TP311.13
  16. Design and Implementation of a Memory Allocator,TP333.1
  17. Research on the Thermal Power Plant Operation Optimization Value Determining Based on Association Rule,TM621
  18. The Software System for Acquisition and Resolution of Ultrafast Electron Diffraction Imaging,O463.1
  19. Development of Information Transmission Management Platform Based on VXWORKS,TP311.52
  20. Research on Keytechniques Ofthe Resource Addressing in the Internet Ofthings Based on DHT,TN929.5
  21. Implementation of Web Virtual Scene Based on Bitmap,TP391.41

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