Please use this identifier to cite or link to this item:
Title: On the scalability of router forwarding tables : Nexthop-Selectable FIB aggregation
Authors: Li, Q
Wang, D 
Xu, M
Yang, J
Issue Date: 2011
Source: Proceedings - IEEE INFOCOM, 2011, p. 321-325 How to cite?
Abstract: In recent years, the core-net routing table, e.g., Forwarding Information Base (FIB), is growing at an alarming speed and this has become a major concern for Internet Service Providers. One effective solution for this routing scalability problem, which requires only upgrades on individual routers, is FIB aggregation. Intrinsically, IP prefixes with numerical prefix matching and the same next hop can be aggregated. Very commonly, all previous studies assume that each IP prefix has one corresponding next hop, i.e., towards one optimal path. In this paper, we argue that a packet can be delivered to its destination through a path other than the one optimal path. Based on this observation, we for the first time propose Nexthop-Selectable FIB Aggregation that is fundamentally different from all previous aggregation schemes. IP prefixes are aggregated if they have numerical prefix matching and share one common next hop. Consequently, IP prefixes that cannot be aggregated, due to lack of the same next hop, are aggregated; and we achieve a substantially higher aggregation ratio. In this paper, we provide a systematic study on this Nexthop-Selectable FIB Aggregation problem. We present several practical choices to build the sets of selectable next hops for the IP prefixes. To maximize the aggregation, we formulate the problem as an optimization problem. We show that the problem can be solved by dynamic programming. While the straightforward application of dynamic programming has exponential complexity, we propose a novel algorithm that is O(N). We then develop an optimal online algorithm with constant running time. We evaluate our algorithms through a comprehensive set of simulations with BRITE with RIBs collected from RouteViews. Our evaluation shows that we can reduce more than an order of the FIB size.
Description: IEEE INFOCOM 2011, Shanghai, 10-15 April 2011
ISBN: 9781424499212
ISSN: 0743-166X
DOI: 10.1109/INFCOM.2011.5935172
Appears in Collections:Conference Paper

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


Last Week
Last month
Citations as of Nov 6, 2018

Page view(s)

Last Week
Last month
Citations as of Nov 12, 2018

Google ScholarTM



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