An Optimal Trie Merging Algorithm
Rui Li · Jisuanji gongcheng · 2013
Dozens or even hundreds of virtual routers may be deployed in a memory limited physical router.To save memory overhead,this paper proposes an algorithm named optimal trie merging algorithm.It adopts dynamic programming approach to find the nodes for initial merging of each trie,and computes the number of nodes of the optimal trie.The sub-node arrangements of any two nodes,which achieve optimal matching,are written down in the process of dynamic programming computation.Then,according to the three computation results,it constructs a data structure named optimal trie.Experimental results show that the algorithm saves 20%~90% memory overhead than simple trie merging algorithm.