虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制

Da-fang ZHANG; Dan CHEN; Yan-biao LI; Kun XIE; Tong SHEN

doi:10.1631/FITEE.1500499

Your Location：

Home >

Browse articles >

虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制

未来网络专题 | Updated：2022-05-19

- 虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制
- A splitting-after-merging approach to multi-FIB compression and fast refactoring in virtual routers
- 信息与电子工程前沿（英文） 2016年17卷第12期页码：1266-1274
- Affiliations：
  
  1College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
  2Department of Electrical and Computer Engineering, State University of New York, New York 11790, USA
- Author bio：
  
  E-mail:dfzhang@hnu.edu.cn
  E-mail:danchen@hnu.edu.cn
- Funds：
  
  Project supported by the National Basic Research Program (973) of China (No. 2012CB315805), the National Natural Science Foundation of China (Nos. 61173167 and 61472130), the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute, China (No. 2013095-1-05), the Hunan Provincial Innovation Foundation for Postgraduate, China (No. CX2014B150), and the State Scholarship Fund of China (No. 201406130048)
- DOI：10.1631/FITEE.1500499
  中图分类号： TP393
- 收稿：2015-12-31，
  
  录用：2016-2-29，
  
  纸质出版：2016-12
- Accepted：
Scan QR Code
虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制[J]. 信息与电子工程前沿（英文）, 2016,17(12):1266-1274.

Da-fang ZHANG, Dan CHEN, Yan-biao LI, et al. A splitting-after-merging approach to multi-FIB compression and fast refactoring in virtual routers[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(12): 1266-1274.
虚拟化路由器中基于融合再拆分的多表压缩及快速重构机制[J]. 信息与电子工程前沿（英文）, 2016,17(12):1266-1274. DOI： 10.1631/FITEE.1500499.

Da-fang ZHANG, Dan CHEN, Yan-biao LI, et al. A splitting-after-merging approach to multi-FIB compression and fast refactoring in virtual routers[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(12): 1266-1274. DOI： 10.1631/FITEE.1500499.

摘要

在未来互联网研究领域中，虚拟化路由器受到越来越多的关注。作为实现网络虚拟化的关键路由设备，虚拟化路由器在一个物理路由平台基础上拥有多个虚拟路由实例，每一个路由实例维护自己的转发表。因此，有限的片上存储限制了存储的扩展性。本文中，我们提出一种基于融合再拆分的方法，用于压缩多个转发表，不仅提高了存储效率，同时为快速系统重构过程提供了一个理想的拆分位置。另外，本文提出了一种优化策略，用于减少快速系统重构的时间。实验表明，我们的方案在处理14个真实路由数据集时，只需要一棵134 188个结点的单步长特里树，而原始方案中需要4 569 133个结点。同时，我们的方案在扩展性中表现出良好的性能，能够支持90 000 000条前缀以及65 600个转发表。

Abstract

Virtual routers are gaining increasing attention in the research field of future networks. As the core network device to achieve network virtualization

virtual routers have multiple virtual instances coexisting on a physical router platform

and each instance retains its own forwarding information base (FIB). Thus

memory scalability suffers from the limited on-chip memory. In this paper

we present a splitting-after-merging approach to compress the FIBs

which not only improves the memory efficiency but also offers an ideal split position to achieve system refactoring. Moreover

we propose an improved strategy to save the time used for system rebuilding to achieve fast refactoring. Experiments with 14 real-world routing data sets show that our approach needs only a unibit trie holding 134 188 nodes

while the original number of nodes is 4 569 133. Moreover

our approach has a good performance in scalability

guaranteeing 90 000 000 prefixes and 65 600 FIBs.

关键词

Keywords

references

M Bando , , , HJ Chao . . FlashTrie: hash-based prefixcompressed trie for IP route lookup beyond 100 Gbps . . 2010 . . Proc. IEEE INFOCOM . . 1 - - 9 . . DOI: 10.1109/INFCOM.2010.5462142 http://doi.org/10.1109/INFCOM.2010.5462142 . .

J Bao , , , Y Chen , , , JS Yu . . A regeneratable dynamic differential evolution algorithm for neural networks with integer weights . . J. Zhejiang Univ. Sci. C (Comput. & Electron.) , , 2010 . . 11 ( ( 12 ): ): 939 - - 947 . . DOI: 10.1631/jzus.C1000137 http://doi.org/10.1631/jzus.C1000137 . .

BM Bass , , , JL Calvignac , , , MC Heddes , , , 等 . . Longest Prefix Match (LPM) Algorithm Implementation for a Network Processor , , 2005 . . : US Patent 7 383 244 : . .

A Broder , , , M Mitzenmacher . . Using multiple hash functions to improve IP lookups . . 2001 . . Proc. IEEE INFOCOM . . 1454 - - 1463 . . DOI: 10.1109/INFCOM.2001.916641 http://doi.org/10.1109/INFCOM.2001.916641 . .

CY Chan , , , YE Ioannidis . . Bitmap index design and evaluation . . 1998 . . Proc. ACM SIGMOD Int. Conf. on Management of Data . . 355 - - 366 . . DOI: 10.1145/276304.276336 http://doi.org/10.1145/276304.276336 . .

M Degermark , , , A Brodnik , , , S Carlsson , , , 等 . . Small forwarding tables for fast routing lookups . . ACM SIGCOMM Comput. Commun. Rev. , , 1997 . . 27 ( ( 4 ): ): 3 - - 14 . . DOI: 10.1145/263109.263133 http://doi.org/10.1145/263109.263133 . .

WN Eatherton , , , Z Dittia . . Data Structure Using a TREE Bitmap and Method for Rapid Classification of Data in a Database , , 2003 . . : US Patent 6 728 732 : . .

W Eatherton , , , G Varghese , , , Z Dittia . . Tree bitmap: hardware/software IP lookups with incremental updates . . ACM SIGCOMM Comput. Commun. Rev. , , 2004 . . 34 ( ( 2 ): ): 97 - - 122 . . DOI: 10.1145/997150.997160 http://doi.org/10.1145/997150.997160 . .

J Fu , , , J Rexford . . Efficient IP-address lookup with a shared forwarding table for multiple virtual routers . . 2008 . . ACM CoNEXT Conf . . 21 DOI: 10.1145/1544012.1544033 http://doi.org/10.1145/1544012.1544033 . .

Z Fu , , , SF Wu , , , H Huang , , , 等 . . IPSec/VPN security policy: correctness, conflict detection, and resolution . . 2001 . . Proc. Int. Workshop on Policies for Distributed Systems & Networks . . 39 - - 56 . . . .

B Han , , , V Gopalakrishnan , , , LS Ji , , , 等 . . Network function virtualization: challenges and opportunities for innovations . . IEEE Commun. Mag. , , 2015 . . 53 ( ( 2 ): ): 90 - - 97 . . DOI: 10.1109/MCOM.2015.7045396 http://doi.org/10.1109/MCOM.2015.7045396 . .

K Huang , , , GG Xie , , , YB Li , , , 等 . . Offset addressing approach to memory-efficient IP address lookup . . 2011 . . Proc. IEEE INFOCOM . . 306 - - 310 . . DOI: 10.1109/INFCOM.2011.5935151 http://doi.org/10.1109/INFCOM.2011.5935151 . .

M Kobayashi , , , T Murase , , , A Kuriyama . . A longest prefix match search engine for multi-gigabit IP processing . . 2000 . . IEEE Int. Conf. on Communications . . 1360 - - 1364 . . DOI: 10.1109/ICC.2000.853719 http://doi.org/10.1109/ICC.2000.853719 . .

H Le , , , T Ganegedara , , , VK Prasanna . . Memoryefficient and scalable virtual routers using FPGA . . 2011 . . Proc. 19th ACM/SIGDA Int. Symp. on Field Programmable Gate Arrays . . 257 - - 266 . . . .

XL Li , , , HM Wang , , , CG Guo , , , 等 . . Topology awareness algorithm for virtual network mapping . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2012 . . 13 ( ( 3 ): ): 178 - - 186 . . DOI: 10.1631/jzus.C1100282 http://doi.org/10.1631/jzus.C1100282 . .

YB Li , , , DF Zhang , , , K Huang , , , 等 . . A memoryefficient parallel routing lookup model with fast updates . . Comput. Commun. , , 2014 . . 38 ( ( 1 ): ): 60 - - 71 . . DOI: 10.1016/j.comcom.2013.10.005 http://doi.org/10.1016/j.comcom.2013.10.005 . .

J Liu , , , T Huang , , , JY Chen , , , 等 . . A new algorithm based on the proximity principle for the virtual network embedding problem . . J. Zhejiang Univ. Sci. C (Comput. & Electron.) , , 2011 . . 12 ( ( 11 ): ): 910 - - 918 . . DOI: 10.1631/jzus.C1100003 http://doi.org/10.1631/jzus.C1100003 . .

LY Luo , , , GG Xie , , , K Salamatian , , , 等 . . A trie merging approach with incremental updates for virtual routers . . 2013 . . Proc. IEEE INFOCOM . . 1222 - - 1230 . . DOI: 10.1109/INFCOM.2013.6566914 http://doi.org/10.1109/INFCOM.2013.6566914 . .

N McKeown , , , T Anderson , , , H Balakrishnan , , , 等 . . OpenFlow: enabling innovation in campus networks . . ACM SIGCOMM Comput. Commun. Rev. , , 2008 . . 38 ( ( 2 ): ): 69 - - 74 . . DOI: 10.1145/1355734.1355746 http://doi.org/10.1145/1355734.1355746 . .

S Nilsson , , , G Karlsson . . IP-address lookup using LCtries . . IEEE J. Sel. Areas Commun. , , 1999 . . 17 ( ( 6 ): ): 1083 - - 1092 . . DOI: 10.1109/49.772439 http://doi.org/10.1109/49.772439 . .

Y Rekhter , , , T Li . . A Border Gateway Protocol 4 (BGP-4) . . RFC 1654, T.J. Watson Research Center & CISCO , , 1994 . . .

NJ Richardson , , , S Rajgopal , , , LB Huang . . Method for Increasing Storage Capacity in a Multi-bit TrieBased Hardware Storage Engine by Compressing the Representation of Single-Length Prefixes , , 2002 . . : US Patent 7 162 481 : . .

K Saravanan , , , A Senthilkumar . . An efficient parallel prefix matching architecture using Bloom filter for multi-bit trie IP lookup algorithm in FPGA . . Optoelectron. Adv. Mat.-Rap. Commun. , , 2015 . . 9 ( ( 5 ): ): 803 - - 807 . . . .

S Sezer , , , S Scott-Hayward , , , PK Chouhan , , , 等 . . Are we ready for SDN? Implementation challenges for software-defined networks . . IEEE Commun. Mag. , , 2013 . . 51 ( ( 7 ): ): 36 - - 43 . . DOI: 10.1109/MCOM.2013.6553676 http://doi.org/10.1109/MCOM.2013.6553676 . .

HY Song , , , J Turner , , , J Lockwood . . Shape shifting tries for faster IP route lookup . . 2005 . . IEEE Int. Conf. on Network Protocols . . 358 - - 367 . . DOI: 10.1109/ICNP.2005.36 http://doi.org/10.1109/ICNP.2005.36 . .

HY Song , , , M Kodialam , , , F Hao , , , 等 . . Scalable IP lookups using shape graphs . . 2009 . . 17th IEEE Int. Conf. on Network Protocols . . 73 - - 82 . . DOI: 10.1109/ICNP.2009.5339697 http://doi.org/10.1109/ICNP.2009.5339697 . .

HY Song , , , M Kodialam , , , F Hao , , , 等 . . Building scalable virtual routers with trie braiding . . 2010 . . Proc. IEEE INFOCOM . . 1 - - 9 . . DOI: 10.1109/INFCOM.2010.5461960 http://doi.org/10.1109/INFCOM.2010.5461960 . .

HY Song , , , M Kodialam , , , F Hao , , , 等 . . Efficient trie braiding in scalable virtual routers . . IEEE/ACM Trans. Netw. , , 2012 . . 20 ( ( 5 ): ): 1489 - - 1500 . . DOI: 10.1109/TNET.2011.2181412 http://doi.org/10.1109/TNET.2011.2181412 . .

V Srinivasan , , , G Varghese . . Fast address lookups using controlled prefix expansion . . ACM Trans. Comput. Syst. , , 1999 . . 17 ( ( 1 ): ): 1 - - 40 . . DOI: 10.1145/296502.296503 http://doi.org/10.1145/296502.296503 . .

Z Wang , , , HF Chen , , , L Xie , , , 等 . . Retransmission in the network-coding-based packet network . . J. Zhejiang Univ.-Sci. C (Comput. & Electron.) , , 2010 . . 11 ( ( 7 ): ): 544 - - 554 . . DOI: 10.1631/jzus.C0910475 http://doi.org/10.1631/jzus.C0910475 . .

KS Wu , , , EJ Otoo , , , A Shoshani . . Optimizing bitmap indices with efficient compression . . ACM Trans. Database Syst. , , 2006 . . 31 ( ( 1 ): ): 1 - - 38 . . DOI: 10.1145/1132863.1132864 http://doi.org/10.1145/1132863.1132864 . .

GG Xie , , , P He , , , HT Guan , , , 等 . . PEARL: a programmable virtual router platform . . IEEE Commun. Mag. , , 2011 . . 49 ( ( 7 ): ): 71 - - 77 . . DOI: 10.1109/MCOM.2011.5936157 http://doi.org/10.1109/MCOM.2011.5936157 . .

H Yu , , , R Mahapatra , , , L Bhuyan . . A hash-based scalable IP lookup using Bloom and fingerprint filters . . 2009 . . Proc. 17th IEEE Int. Conf. on Network Protocols . . 264 - - 273 . . DOI: 10.1109/ICNP.2009.5339676 http://doi.org/10.1109/ICNP.2009.5339676 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

Recent advances in efficient computation of deep convolutional neural networks