FIFA: Fast incremental FIB aggregation

Yaoqing Liu, Beichuan Zhang, Lan Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations


The fast growth of global routing table size has been causing concerns that the Forwarding Information Base (FIB) will not be able to fit in existing routers' expensive line-card memory, and upgrades will lead to higher cost for network operators and customers. FIB Aggregation, a technique that merges multiple FIB entries into one, is probably the most practical solution since it is a software solution local to a router, and does not require any changes to routing protocols or network operations. While previous work on FIB aggregation mostly focuses on reducing table size, this work focuses on algorithms that can update compressed FIBs quickly and incrementally. Quick update is critical to routers because they have very limited time to process routing updates without impacting packet delivery performance. We have designed three algorithms: FIFA-S for smallest table size, FIFA-T for shortest running time, and FIFA-H for both small tables and short running time, and operators can use the one best suited to their needs. These algorithms significantly improve over existing work in terms of reducing routers' computation overhead and limiting impact on the forwarding plane while maintaining a good compression ratio.

Original languageEnglish (US)
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Number of pages9
StatePublished - 2013
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: Apr 14 2013Apr 19 2013

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'FIFA: Fast incremental FIB aggregation'. Together they form a unique fingerprint.

Cite this