Nexthop-Selectable FIB aggregation: An instant approach for internet routing scalability

Qing Li, Mingwei Xu, Dan Wang, Jun Li, Yong Jiang, Jiahai Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Abstract Recently, the core net routing table is growing at an alarming speed which has become a major concern to Internet Service Providers. One effective solution is Forwarding Information Base (FIB) aggregation. All the previous studies assume every prefix has only one next hop. In this paper, we argue that a packet can be delivered to its destination by multiple selectable next hops. Based on this observation, we propose Nexthop-Selectable FIB aggregation. Prefixes, including those which originally have different next hops, are aggregated if they share one common next hop. We provide a systematic study on this Nexthop-Selectable FIB aggregation problem. We present several practical choices to build selectable next hops for prefixes. We propose a non-trivial O(N) algorithm to optimally solve the problem. We then study a generalized problem where we assign weights for different next hops to bound path stretch. We further develop an optimal incremental updating algorithm with constant running time. We evaluate our algorithms through a comprehensive set of simulations with BRITE and real world topologies. Our evaluation shows that the aggregated FIB is one order of magnitude smaller than the original one.
Original languageEnglish
Article number5130
Pages (from-to)11-22
Number of pages12
JournalComputer Communications
Volume67
DOIs
Publication statusPublished - 1 Aug 2015

Keywords

  • FIB aggregation
  • Internet routing
  • Routing scalability

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this