Please use this identifier to cite or link to this item:
Title: Nexthop-Selectable FIB aggregation: An instant approach for internet routing scalability
Authors: Li, Q
Xu, M
Wang, D 
Li, J
Jiang, Y
Yang, J
Keywords: FIB aggregation
Internet routing
Routing scalability
Issue Date: 2015
Publisher: Elsevier
Source: Computer communications, 2015, v. 67, 5130, p. 11-22 How to cite?
Journal: Computer communications 
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.
ISSN: 0140-3664
EISSN: 1873-703X
DOI: 10.1016/j.comcom.2015.07.003
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Checked on Sep 18, 2017

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.