[en] Virtual routers are increasingly being studied, as an important building block to enable network virtualization.
In a virtual router platform, multiple virtual router instances coexist, each having its own FIB (Forwarding Information Base).
In this context, memory scalability and route updates are two major challenges. Existing approaches addressed one of these challenges but not both. In this paper, we present a trie merging approach, which compactly represents multiple FIBs by a merged trie and a table of next-hop-pointer arrays to achieve good memory scalability, while supporting fast incremental updates by avoiding the use of leaf pushing during merging. Experimental results show that storing the merged trie requires limited memory space, e.g., we only need 10MB memory space to store the merged trie for 14 full FIBs from IPv4 core routers, achieving a memory reduction by 87% when compared to the total size of the individual tries. We implement our approach in an SRAM (Static Random Access Memory)-based lookup pipeline. Using our approach, an on-chip SRAM-based lookup pipeline with
5 external stages is sufficient to store the 14 full IPv4 FIBs. Furthermore, our approach can guarantee a minimum update overhead of one write bubble per update, as well as a high lookup throughput of one lookup per clock cycle, which corresponds to a throughput of 251 million lookups per second in the
implementation.
Disciplines :
Computer science
Author, co-author :
Luo, LAYONG; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Xie, Gaogang; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Salamatian, Kavé; Université de Haute-Savoie
Uhlig, Steve; Queen Mary University - QMUL
Mathy, Laurent ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes informatiques répartis et sécurité
Xie, Yingke; Chinese Academy of Sciences - CAS > Institute of Computing Technology - ICT
Language :
English
Title :
A Trie Merging Approach with Incremental Updates for Virtual Routers
Publication date :
2013
Event name :
IEEE Infocom
Event date :
2013
Audience :
International
Main work title :
Annual International Conference on Computer Communications
N. M. M. K. Chowdhury and R. Boutaba, A survey of network virtualization, Computer Networks, 2010.
G. Xie, P. He, H. Guan, Z. Li, Y. Xie, L. Luo, J. Zhang, Y. Wang, and K. Salamatian, PEARL: a programmable virtual router platform, IEEE Communications Magazine, 2011.
N. Egi, A. Greenhalgh, M. Handley, M. Hoerdt, F. Huici, and L. Mathy, Towards high performance virtual routers on commodity hardware, in Proc. ACM CoNEXT, 2008.
M. B. Anwer, M. Motiwala, M. bin Tariq, and N. Feamster, Switchblade: a platform for rapid deployment of network protocols on programmable hardware, in Proc. ACM SIGCOMM, 2010.
J. Fu and J. Rexford, Efficient IP-address lookup with a shared forwarding table for multiple virtual routers, in Proc. ACM CoNEXT, 2008.
H. Song, M. Kodialam, F. Hao, and T. Lakshman, Building scalable virtual routers with trie braiding, in Proc. IEEE INFOCOM, 2010.
T. Ganegedara, W. Jiang, and V. Prasanna, Multiroot: Towards memory-efficient router virtualization, in Proc. IEEE ICC, 2011.
H. Le, T. Ganegedara, and V. K. Prasanna, Memoryefficient and scalable virtual routers using FPGA, in Proc. FPGA, 2011.
T. Ganegedara, H. Le, and V. K. Prasanna, Towards Onthe-Fly Incremental Updates for Virtualized Routers on FPGA, in Proc. FPL, 2011.
V. Srinivasan and G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems, 1999.
L. Luo, G. Xie, Y. Xie, L. Mathy, and K. Salamatian, A hybrid IP lookup architecture with fast updates, in Proc. IEEE INFOCOM, 2012.
D. Unnikrishnan, R. Vadlamani, Y. Liao, A. Dwaraki, J. Crenne, L. Gao, and R. Tessier, Scalable network virtualization using FPGAs, in Proc. FPGA, 2010.
G. Gibb, J. W. Lockwood, J. Naous, P. Hartke, and N. McKeown, NetFPGA-an open platform for teaching how to build gigabit-rate network switches and routers, IEEE Transactions on Education, 2008.
M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, Survey and taxonomy of IP address lookup algorithms, IEEE Network, 2001.
W. Eatherton, G. Varghese, and Z. Dittia, Tree bitmap: Hardware/software IP lookups with incremental updates, Computer Communication Review, 2004.
RIPE RIS Raw Data. [Online]. Available: http://www.ripe.net/data-tools/ stats/ris/ris-raw-data
S. Sikka and G. Varghese, Memory-efficient state lookups with fast updates, in Proc. ACM SIGCOMM, 2000.
J. Hasan and T. N. Vijaykumar, Dynamic pipelining: Making IP-lookup truly scalable, in Proc. ACM SIGCOMM, 2005.
A. Basu and G. Narlikar, Fast incremental updates for pipelined forwarding engines, in Proc. IEEE INFOCOM, 2003.
W. Jiang and V. K. Prasanna, A memory-balanced linear pipeline architecture for trie-based IP lookup, in Proc. IEEE HOTI, 2007.
Xilinx Inc. [Online]. Available: http://www.xilinx.com/
W. Jiang and V. Prasanna, Towards practical architectures for SRAM-based pipelined lookup engines, in Proc. IEEE INFOCOM Work-in-Progress Track, 2010.