Study On IP-address Lookup Algorithms With A Multi-branch Trie-based Forwarding Table For Virtual Routers

In recent years, network service becomes more diverse, which brings usconvenient but also problems. Virtual routing technology, an effective means couldhelp us to solve these problems. However, router’s limited storage space setsrestrictions on the quantities of virtual routing in concurrent operation. In addition,multi-virtual routings in concurrent operation may easily lead to performancereduction of IP search, and then may brings tremendous difficulties to variousapplications of virtual routing technology. Therefore, how to set a rational design onthe structure of virtual routing forwarding table and ensure the high performance of IPsearch becomes the problem demanding prompt solution of virtual routing technology.Focused on the virtual routing search algorithms of Trie architecture, the outlinesof this thesis are as follows:Firstly, this paper starts with a research on the problems results in the merge oftrie-based virtual routing forwarding table. Against to the tanglesome structure whichleads by monobit shared forwarding table, and leads to the storage limitation and lowefficiency, this paper proposes a multi branch Trie-based dynamic shared forwardingtable structure, and then to realize the corresponding virtual routing IP lookupalgorithm. The scheme adopts the multiple bits of IP lookup, reducing the forwardingtable structural consumption and memory access frequency. At the same time, thestructure has dynamic adjustments on Trie per layer node stride value. Theexperiments show that compared with the existing shared forwarding table structure,the structure of dynamic shared forwarding table can save a lot of storage space, andrealize the quick IP search.Secondly, research on the relation of forwarding table space consumption andTrie stride size value selection. Aim at the differentiations of rule sets distribution,proposing an algorithm based on the idea of dynamic programming optimal Trie stridepartition, to construct minimal space consumption dynamic shared forwardingproblem. Algorithm through statistical forwarding rules’ length density automaticallyfor each layer of the Trie node to select the optimal stride values, to further save spaceoverhead of dynamic shared forwarding. Simulation results show that the algorithmcan effectively calculate each layer of Trie nodes required stride value, compare withthe way of fixed step to construct forwarding table,the algorithm can save more storage space..Last but not least, combining above proposed schemes in the dissertation,designing and implementing multi branch Trie-based forwarding table virtual routingIP for simulation platform, and evaluating the proposed to make the structure of the IPsearch performance. Mainly aim at dynamic shared table space consumption and IPlookup properties of precision statistics and monitoring, it has feasibility andscalability. Through the comparison of experimental data, the software can be used asthe proposed structure and algorithm provides an effective means for measuring.