Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/75848
Title: Scale the internet routing table by generalized next hops of strict partial order
Authors: Li, Q
Xu, MW
Li, Q
Wang, D 
Jiang, Y
Xia, ST
Liao, QM
Keywords: Routing scalability
Forwarding information base
FIB aggregation
SPO next hop
Issue Date: 2017
Publisher: Elsevier
Source: Information sciences, 2017, v. 412, p. 101-115 How to cite?
Journal: Information sciences 
Abstract: The Internet routing tables have been expanding at a dramatic and increasing rate. Although the latest high-performance routers provide enough capacities, Internet Service Providers (ISPs) cannot afford to upgrade their routers at the pace of routing table growth. Shrinking the routing table, especially the TCAM-based Forwarding Information Base (FIB), is more feasible. In this paper, we propose a scheme to aggregate the FIB based on generalized next hops of strict partial order (SPO). We first use generalized SPO next hops to construct the Nexthop-Selectable FIB (NSFIB), where each prefix has multiple next hops. Our NSFIB aggregation avoids the aggregation performance degrading with the network density increasing, which is one main defect of the traditional single-nexthop FIB aggregation. We then design different levels of aggregation algorithms to aggregate the NSFIB. Besides, we control the path stretch by setting an upper limit to filter bad next hops. We also introduce routing protection by the pre-computed SPO next hops. According to our simulation, our aggregation algorithms shrink the FIB to 5-15%, compared with 20-60% of single-nexthop FIB aggregation algorithms; our method works very well in controlling the path stretch; and SPO next hops protect 50-95% (topology-related) failure-affected packets.
URI: http://hdl.handle.net/10397/75848
ISSN: 0020-0255
EISSN: 1872-6291
DOI: 10.1016/j.ins.2017.05.033
Appears in Collections:Journal/Magazine Article

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

Google ScholarTM

Check

Altmetric


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