Paper published in a book (Scientific congresses and symposiums)
A Trie Merging Approach with Incremental Updates for Virtual Routers
Luo, LAYONG; Xie, Gaogang; Salamatian, Kavé et al.
2013In Annual International Conference on Computer Communications
Peer reviewed
 

Files


Full Text
infocom 2013_luo.pdf
Publisher postprint (469.76 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Abstract :
[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
Main work alternative title :
[en] Infocom
Publisher :
IEEE
Peer reviewed :
Peer reviewed
Available on ORBi :
since 17 May 2014

Statistics


Number of views
99 (3 by ULiège)
Number of downloads
351 (0 by ULiège)

Scopus citations®
 
15
Scopus citations®
without self-citations
9
OpenCitations
 
7

Bibliography


Similar publications



Contact ORBi