Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/22519
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
URI: http://hdl.handle.net/10397/22519
ISBN: 9781424499212
ISSN: 0743-166X
DOI: 10.1109/INFCOM.2011.5935172
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

20
Last Week
0
Last month
0
Citations as of Sep 23, 2017

Page view(s)

31
Last Week
3
Last month
Checked on Sep 24, 2017

Google ScholarTM

Check

Altmetric



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