Design On TRIE-Based Soft-forword Route Lookup Module

With the rapid development of Internet, its size, link speed, bandwidth, traffic, etc. show exponential growth, which need a higher route forwarding performance, and an important step of forwarding is to look the routing table up, so fast route lookup algorithm is the key to high-speed data forwarding. Among the commonly used route lookup algorithms, Trie-based algorithm not only has good lookup speed, space complexity and time complexity, but also adapts to ever-increasing performance requirements of routers, the modern novel fast-search algorithms were achieved on the basis of the Trie-tree by optimizing the algorithm.So the Trie-based route lookup algorithm which is used for soft-forward route lookup module is becoming a trend.This paper discusses how to achieve soft-forwarding routing table lookup algorithm on the router, to design and optimize of Trie-based routing table lookup algorithm, to improve route lookup speed, to achieve high-speed packet forwarding. The main contents are as follows:1) Research the basic function of routers and the IP routing lookup process, analyze the Trie structure used fpr the IP routing lookup algorithm, introduce the related concepts of routing and forwarding, the generation of routing table and the principle of routing.2) Analyze the forward module framework and process,research on the basic structure of forwarding tables, detail the design principles and specific process of uplink and downlink sub-module in forwarding module.3) Reseach the importance of soft-forward routing table lookup module to data forwarding. Analyze the present situation of the routing table lookup algorithm, design more effective and practical TRIE-based route table lookup algorithm based on the novel algorithms.4) According to the design of routing lookup algorithm, integrate the source to implement the routing table lookup scheme meeting the requirements. Determine the solutions of the whole soft-forward routing module, optimize the whole module.Compile the source and debug.5) Research Trie-based soft-forward routing table search algorithm in the routers, use the tester to validate the soft-forwarding function cooperating with the router. According to the result of test, analyze whether it meets the user needs or not, summarize the pros and cons.