基于集合分割的虚拟路由器转发表查找的实现

doi:10.3969/j.issn.1000-0801.2014.10.016

摘要/Abstract

摘要：

虚拟路由器即在一个物理路由器上并行实现多个独立的虚拟路由器实例，是未来互联网的核心网络设备。针对虚拟路由器转发表的查找技术，采用集合分割的方式，将分割出的两个集合分别利用SRAM 和DRAM实现。对各种方案进行了分析，并提出了使用标志位解决SRAM查找相交前缀的效率低下问题。实验结果表明，提出的解决方案大大减少了存储空间，并在总体上得到了优化。

关键词: 虚拟路由器, 虚拟网, 转发表查找, 集合分割

Abstract:

Virtual router is a core network device of future internet, which runs multiple virtual routers in parallel on a common physical router platform. It is aimed at the looking up technology on virtual router's forwarding table, which using the way of set partition to cut apart the prefixes set into two sets that realized using SRAM and DRAM respectively. Various solutions were analyzed, and new method that to use mark bit solving the problem of inefficient looking up overlapping prefixes in SRAM, was proposed. The experiment results show that the solution greatly reduces storage space, and optimizes the overall effects.

Key words: virtual router, virtual network, forwarding table lookup, set partition

胡颖,庄雷. 基于集合分割的虚拟路由器转发表查找的实现[J]. 电信科学, 2014, 30(10): 103-109.

Ying Hu,Lei Zhuang. Realization of Looking up Virtual Router's FIB Based on Set Partition[J]. Telecommunications Science, 2014, 30(10): 103-109.

图/表 5

图1

图2

图3

图4

表1

参考文献 13

14	Huang K , Xie G , Li Y , et al. Offset addressing approach to memory-efficient IP address lookup. Proceedings of IEEE INFOCOM, Shanghai, China, 2011: 306～310
15	Luo L , Xie G , Xie Y , et al. A hybrid IP lookup architecture with fast updates. Proceedings of IEEE INFOCOM, Orlando, FL, USA, 2012: 2435～2443
16	Ganegedara T , Jiang W , Prasanna V . Multiroot: towards memory-efficient router virtualization. Proceedings of IEEE International Conference, Kyoto, Japan, 2011: 1～5
17	Luo L , Xie G , Uhlig S , et al. Towards TCAM-based scalable virtual routers. Proceedings of the 8th International Conference on Emerging Networking Experiments and Technologies, Nice, France, 2012: 73～84
18	Shah D , Gupta P . Fast incremental updates on ternary-CAMs for routing lookups and packet classification. Proceedings of Hot Interconnects-8, Stanford, CA, USA, 2000: 145～153
19	Fu J , Rexford J . Efficient IP-address lookup with a shared forwarding table for multiple virtual routers. Proceedings of the ACM CoNEXT Conference, New York, NY, USA, 2008: 1～12
1	Anderson T , Peterson L , Shenker S , et al. Overcoming the internet impasse through virtualization. Computer, 2005, 38(4): 34～41
2	Turner J S , Taylor D E . Diversifying the internet. Proceedings of Global Telecommunications Conference, St Louis, MO, USA, 2005
3	Feamster N , Gao L , Rexford J . How to lease the internet in your spare time. ACM SIGCOMM Computer Communication Review, 2007, 37(1): 61～64
4	FIRE. , http: //www. ict-firworks.eu, 2012
5	Zhang L , Estrin D , Burke J , et al. Named Data Networking （NDN）Project. Relatório Técnico NDN-0001, Xerox Palo Alto Research Center-PARC, 2010
6	Egi N , Greenhalgh A , Handley M , et al. Towards high performance virtual routers on commodity hardware. Proceedings of the ACM CoNEXT Conference, New York,NY,USA, 2008: 1～12
7	NWGN. , http:// akari-project.nict.go.jp, 2012
8	Han S , Jang K , Park K S , et al. PacketShader: a GPU-accelerated software router. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 195～206
9	FIF. , http://www.fif.kr, 2012
10	Cisco logical router. , http: //www.cisco.com, 2012
11	Juniper logical router. , http: //www.juniper.net, 2012
12	Netlogic. NL 9000 RA knowledge-based processors, 2009
20	Le H , Ganegedara T , Prasanna V K . Memory-efficient and scalable virtual routers using FPGA. Proceedings of the 19th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Monterey, California, USA, 2011: 257～266
13	The BGP instability report. , http://bgpupdates.potaroo.net/instability/bgpupd.html, 2014

FIB	总IPv4前缀数	特里树节点数	叶子前缀数	剪枝后前缀数	剪枝后节点数
Rrc00	475 101	1 124 306	428 562	46 539	470 698
Rrc01	465 890	1 098 720	420 138	45 752	458 428
Rrc03	479 201	1 132 898	432 333	46 868	473 650
Rrc04	475 101	1 124 306	428 562	46 539	470 698
Rrc05	467 751	1 103 188	421 906	45 845	460 172
Rrc06	473 920	1 119 093	427 144	46 776	467 970
Rrc07	468 235	1 105 746	422 572	45 663	461 627
Rrc10	473 264	1 124 407	426 899	46 365	473 143
Rrc11	475 567	1 122 722	429 088	46 479	468 522
Rrc12	482 544	1 144 723	434 829	47 715	481 489
Rrc13	512 776	1 215 634	464 831	47 945	504 693
Rrc14	476 914	1 123 758	429 761	47 153	468 842
Rrc15	476 057	1 122 188	428 316	47 741	469 755
本FIB	541 921	1 291 949	488 900	53 021	543 916
参考文献[15]	6 202 321	14 661 716	5 594 941	607 380	6 129 714
参考文献[17]	541 921	1 291 949	488 900	607 380	6 129 714

[1]	潘洁,薛曌. 基于Docker的DPI虚拟化部署[J]. 电信科学, 2019, 35(12): 131-136.
[2]	魏亮,李蓉,吴正东,张玉亮,程智炜,黄韬. 基于SDN/NFV的未来网络实验平台[J]. 电信科学, 2017, 33(4): 39-47.
[3]	董晓东,郭志强,陈胜,周晓波,齐恒,李克秋. 面向SDN网络虚拟化平台的控制器放置算法[J]. 电信科学, 2017, 33(4): 56-64.
[4]	余建军,吴春明. 基于成本约束的虚拟网映射策略及竞争分析[J]. 电信科学, 2016, 32(2): 47-54.
[5]	曲桦,樊斌,郭涯,王力,赵季红. 应用粒子群优化的绿色虚拟网络映射算法[J]. 电信科学, 2016, 32(1): 11-17.
[6]	樊勇兵,陈天,陈楠,黄志兰,吕翠娥. 云数据中心的虚拟机放置问题[J]. 电信科学, 2015, 31(2): 140-146.
[7]	王力,赵季红,曲桦,郭涯. 软件定义承载网中基于负载均衡的虚拟网络资源分配算法[J]. 电信科学, 2015, 31(11): 36-42.
[8]	陈晓华,李春芝,陈良育,曾振柄. 虚拟网络映射最小费用流模型及算法[J]. 电信科学, 2014, 30(6): 90-94.
[9]	余建军,吴春明. 基于二分图K优完美匹配的虚拟网映射算法设计[J]. 电信科学, 2014, 30(2): 70-75.
[10]	曲桦,王丽霞,赵季红,王贺男. 面向差异化业务请求的虚拟网络映射算法[J]. 电信科学, 2014, 30(12): 64-70.
[11]	黄胜,吴川川,杨晓非,王辉,张卫. 一种基于临近原则的虚拟网络映射算法[J]. 电信科学, 2013, 29(12): 38-44.
[12]	李文,吴春明,陈键,平玲娣. 节点可重复映射和链路可分流的虚拟网映射算法[J]. 电信科学, 2010, 26(10): 114-120.