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

梁飞; 徐明伟

0
0
浏览
下载

摘要
关键词
基金信息
论文图表
同行评议
相关论文
评论

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

首发时间：2014-12-26

梁飞 ¹
梁飞（1989-），男，硕士研究生，网络虚拟化
徐明伟 ²
徐明伟（1971-），男，教授，计算机网络，路由算法

1、北京邮电大学网络技术研究院,北京 100876
2、清华大学计算机系,北京 100083

摘要：当前，随着网络虚拟化的发展，对虚拟路由器的研究也成为热点。通常有多个虚拟路由器部署在一台物理路由器上，导致路由表的增加，如何实现路由的高效查找成为虚拟路由器研究领域的热点问题。本文通过使用Trie树合并和Bloom Filter来实现路由的快速查找。首先，根据路由表生成Trie树，对Trie树进行Leaf-pushing后将多个Trie树合并，之后为合并后的Trie树每一层构建一个布隆过滤器存储在片内存储器如TCAM中，将对应的前缀与下一跳映射的Hash表存在片外存储器中。因片内存储器的存取速度远远大于片外存储器，通过增加额外布隆过滤器和对每层Bloom Filter哈希函数个数的调整，减小Bloom Filter假阳性，减少多次片外访存的次数，提高算法性能。

关键词：计算机网络虚拟路由器路由查找 Trie树 Bloom Filter

For information in English, please click here

Research of virtual ip-address merging and lookup based on bloom filters

Liang Fei ¹
梁飞（1989-），男，硕士研究生，网络虚拟化
Xu Mingwei ²
徐明伟（1971-），男，教授，计算机网络，路由算法

1、Network Technology Institute,Beijing University of Posts and Telecommunications,Beijing 100876
2、Computer Science Department,Tsinghua University,Beijing 100083

Abstract：At 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.

Keywords： computer network virtual router route lookup trie bloom filter

基金：

论文图表：

引用

导出参考文献

.txt

.ris

.doc

梁飞，徐明伟. 基于Bloom Filter的虚拟路由合并与查找算法的研究[EB/OL]. 北京：中国科技论文在线 [2014-12-26]. https://www.paper.edu.cn/releasepaper/content/201412-833.

No.4623859102534714****

同行评议

共计0人参与

全部评论

0/1000

论文编号	201412-833
论文题目	基于Bloom Filter的虚拟路由合并与查找算法的研究
文献类型
收录期刊	上传封面中文期刊英文期刊期刊名称（中文）期刊名称（英文）年，卷（）上传封面中文专著英文专著书名（中文）书名（英文）出版地出版社出版年上传封面中文译著英文译著书名（中文）书名（英文）出版地出版社出版年上传封面中文论文集英文论文集编者.论文集名称（中文） [c]. 出版地出版社出版年， - 编者.论文集名称（英文） [c]. 出版地出版社出版年，- 上传封面中文文献英文文献期刊名称（中文）期刊名称（英文）日期-- 在线地址http:// 上传封面中文文献英文文献文题（中文）文题（英文）出版地出版社,出版日期-- 上传封面中文文献英文文献文题（中文）文题（英文）出版地出版社,出版日期--
英文作者写法：中外文作者均姓前名后，姓大写，名的第一个字母大写，姓全称写出，名可只写第一个字母，其后不加实心圆点“.”, 作者之间用逗号“，”分隔，最后为实心圆点“.”, 示例1：原姓名写法：Albert Einstein,编入参考文献时写法：Einstein A. 示例2：原姓名写法：李时珍；编入参考文献时写法：LI S Z. 示例3：YELLAND R L,JONES S C,EASTON K S,et al.