The Research On IP Address Lookup And Packet Classification Algorithm

With the rapid development of Internet, link rate have been able to meet therequirements of growing traffic, but packet forwarding rate of router can’t keep upwith their pace. At the same time, the space efficiency of router has also become animportant bottleneck which affect router performance. IP address lookup and packetclassification are two important routing functions. How to design time-efficient andmemory-efficient IP address lookup or packet classification algorithm is the hot issuein the current research.This paper proposes three kinds of high-performance IP address looking up andpacket classification algorithms.1) Optimized Trie Merging Algorithm is proposed.We adopt dynamic programming approach to compute the nodes for initial mergingand optimal sub-node arrangements. Then, according the two computation results, weconstruct a data structure named optimal trie. Compared with the existing trie mergingalgorithms, Optimized Trie Merging Algorithm effectively saves the memory overhead.2) Optimized Pipelined Indexing Hash Tree (OPIHT) Algorithm is proposed. Trie isconstructed with all prefixes in a route table and preprocessed, then adopts dynamicprogramming approach to determine the optimal prefix dividing scheme. Comparedwith the existing PIHT algorithm, OPIHT algorithm effectively saves memoryoverhead.3) Fast Multiway Most Specific Tree (FMMSPT) Algorithm is proposed. B+tree is constructed with the most specific prefixes as keywords, prefixes in a leaf nodewhich contain keywords are compressed and storaged with an unsigned integer.Compared with the existing MMSPT, FMMSPT effectively improved lookupperformance.In this paper, the research has significant theoretical and practical applicationvalue. Compared with existing IP address lookup and packet classification algorithms,three kinds of proposed algorithms for different application background effectivelyimproves the search speed and reduce the memory overhead. In the context of specificapplications, these high performance algorithms can satisfy the growing traffic demandfor packet forwarding rate of router and space efficiency of router. The algorithm isscalable, and can adapt to the requirement of Internet upgrade.