基于Bloom Filter的虚拟路由合并与查找算法的研究

t present,virtual routers have become a hot topic with the developping of network virtualization.There are plenty of virtual router instances in a physic router,each with its own FIB(Forwding Information Base).How to achieve high forwarding performance is a challenge.In this paper,we combine trie-merging and prefix bloom filter to conduct IP lookup.We first merge all the prefixes from FIBs on the leaf-pushing trie.Then we bulid a bloom filter and a hash table for the prefixes at each level of the merged trie. As the access of on-chip memory such as TCAM is tens of times of that of off-chip memory,we add an extra bloom filter and adust each level's bloom filter to reduce the false positive of the bloom filter and the access of off-chip memory.