Research And Implementation Of Packet Classification In Advanced Router

With the rapid development of internet, various net traffics are emerging, and the original"best effort"service is not adaptive,All of above show new requirements to the kernel equipment of internet–backbone router. Service providers would like routers to provide"service differentiation",such as preferential treatment for premium traffic (resource reservation); routing based on traffic type and source (Qos routing) ; virtual private networks and policy-based routing .Traditional routers do not provide service differentiation because they treat all traffics going to the same internet destination address identically. Routers with a packet classification capability however can distinguish traffics based on destination, source and application type. Such classification allows various forms of service differentiation.IP packet classification is a technique to match each incoming IP packet against a database of filters (or rules) according one-domain or multi-domain in the head of the packet ,and forwarding the packet according to the highest priority filter.In the thesis, we first describe some representative classification algorithms, and discuss their time and space request .According to analysis on the parallel ability of Network Processor and class equivalent used in the algorithm of RFC, a high-speed packet classification is presented. It uses the hash lookup and is flexible and scalable.Some techniques in the design of the new algorithm are given, including the mapping of equivalence class ID, the improvement of CBM and the solution of Hash conflict. Comparing to the algorithm of RFC used in the advanced router, the algorithm provides better time and space complexity; supports dynamic update; and the lookup time is independent of the size of the database of rules. Finally, the performance of the new algorithm is tested and the results show well and meet the theory result requirement.