Reference : A Trie Merging Approach with Incremental Updates for Virtual Routers
Scientific congresses and symposiums : Paper published in a book
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/167804
A Trie Merging Approach with Incremental Updates for Virtual Routers
English
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 mailto [Université de Liège - ULg > 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 > > >]
2013
Annual International Conference on Computer Communications
[en] Infocom
IEEE
Yes
International
IEEE Infocom
2013
[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.
Researchers ; Professionals
http://hdl.handle.net/2268/167804
10.1109/INFCOM.2013.6566914

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
infocom 2013_luo.pdfPublisher postprint458.75 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.