![](https://csdnimg.cn/release/download_crawler_static/16111396/bg3.jpg)
Q. Li et al. / Information Sciences 412–413 (2017) 101–1 15 103
Fig. 1. Router model with NSFIB aggregation.
The rest of the paper proceeds as follows. In Section 2 , we discuss the background and related works of FIB aggregation.
Section 3 describes NSFIB construction method. Section 4 specifies the NSFIB-based aggregation algorithms. In Section 5 , we
provide the method of controlling the path stretch and the architecture of routing protection by generalized SPO next hops.
In Section 6 , we demonstrate the performance of our algorithms by comprehensive simulations. Finally, we conclude the
paper in Section 8 .
2. Background and motivation
It is widely accepted that the Internet routing system is facing severe routing scalability problem [1] . To solve this prob-
lem, numbers of solutions [6–14] have been proposed to change or upgrade the architecture of Internet. However, these
long-term solutions involve protocol change or nontrivial configuration overhead, thus they demand a long deploying time.
Therefore, several FIB aggregation schemes [15–18] , which are router-level incrementally deployable, have been proposed to
handle the immediate requirement of ISPs. However, these single-nexthop FIB aggregation schemes cannot provide a satis-
factory compression performance. Therefore, Nexthop-Selectable FIB (NSFIB) aggregation [21] has been proposed to further
compress FIB by constructing multiple selectable next hops for each prefix.
Given the source/destination nodes R
s
/ R
d
, there are some no-loop next hops (except the optimal one) that can be used
to forward the packets from R
s
to R
d
[28] . Suppose R
d
is the egress router for a prefix p , these no-loop next hops can also
be used to forward the packet of p . In this way, the NSFIB can be constructed, where the prefix has multiple selectable next
hops (not just the optimal one).
In NSFIB aggregation, a covered prefix sharing one common next hop with the covering prefix can be aggregated. As
the possibility of two prefixes sharing one common next hop is higher than the possibility of two prefixes having the same
optimal next hop, NSFIB aggregation aggregates more entries than the traditional single-nexthop FIB aggregation. However,
as a first-step work, NSFIB aggregation has several challenges to be addressed before practical deployment:
• An efficient NSFIB construction algorithm. As the first challenge, constructing the intra-domain nexthop-selectable
routing table is the key to construct NSFIB (shown in Fig. 1 ).
• The NSFIB aggregation algorithms. After NSFIB construction, different levels of aggregation algorithms are required to
generate the final FIB, as shown in Fig. 1 .
• An approach to control the path stretch. In order to shrink more entries, NSFIB aggregation would use next hops
without optimality, which inevitablely introduces path stretch.
3. NSFIB construction based on generalized SPO next hop
In this section, we focus on the first challenge of constructing the NSFIB. We first define the concepts of SPO next hop
and generalized SPO next hop; we then provide the efficient NSFIB construction algorithms according to the concepts, which
have the same time complexity as the algorithm of shortest path first (SPF); finally, we prove that based on the construction
approach of SPO next hop, the performance of NSFIB aggregation increases as the density (average degree) of the network
increases. We propose the concepts and algorithms based on the intra-domain routing system. The NSFIB can be finally
constructed by mapping the egress BGP router (one intra-domain router) to the corresponding next hops.
3.1. Next hop of strict partial order
Open Shortest Path First (OSPF) is widely used as the intra-domain routing protocol in the Internet. Loop Free Alternates
(LFA) [28] is an intra-domain scheme for failure protection, which is based on OSPF and thus well compatible with the
current Internet. In LFA, there are several conditions for backup next hops (alternates) selection, including DownStream
Condition (DSC). In [21] , we directly used DownStream Condition to construct NSFIB. However, we found that this method
could be improved for better performance. Therefore, we propose the next hop of strict partial order (SPO next hop).