TY - JOUR
T1 - Online Aggregation of the Forwarding Information Base
T2 - Accounting for Locality and Churn
AU - Bienkowski, Marcin
AU - Sarrar, Nadi
AU - Schmid, Stefan
AU - Uhlig, Steve
PY - 2018/2/1
Y1 - 2018/2/1
N2 - This paper studies the problem of compressing the forwarding information base (FIB), but taking a wider perspective. Indeed, FIB compression goes beyond sheer compression, as the gain in memory use obtained from the compression has consequences on the updates that will have to be applied to the compressed FIB. We are interested in the situation where forwarding rules can change over time, e.g., due to border gateway protocol (BGP) route updates. Accordingly, we frame FIB compression as an online problem and design competitive online algorithms to solve it. In contrast to prior work which mostly focused on static optimizations, we study an online variant of the problem where routes can change over time and where the number of updates to the FIB is taken into account explicitly. The reason to consider this version of the problem is that leveraging temporal locality while accounting for the number of FIB updates helps to keep routers CPU load low and reduces the number of FIB updates to be transferred, e.g., from the network-Attached software-defined network controller to a remote switch. This paper introduces a formal model which is an interesting generalization of several classic online aggregation problems. Our main contribution is an O(w)-competitive algorithm, where {w} is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms, based on so-called sticks.
AB - This paper studies the problem of compressing the forwarding information base (FIB), but taking a wider perspective. Indeed, FIB compression goes beyond sheer compression, as the gain in memory use obtained from the compression has consequences on the updates that will have to be applied to the compressed FIB. We are interested in the situation where forwarding rules can change over time, e.g., due to border gateway protocol (BGP) route updates. Accordingly, we frame FIB compression as an online problem and design competitive online algorithms to solve it. In contrast to prior work which mostly focused on static optimizations, we study an online variant of the problem where routes can change over time and where the number of updates to the FIB is taken into account explicitly. The reason to consider this version of the problem is that leveraging temporal locality while accounting for the number of FIB updates helps to keep routers CPU load low and reduces the number of FIB updates to be transferred, e.g., from the network-Attached software-defined network controller to a remote switch. This paper introduces a formal model which is an interesting generalization of several classic online aggregation problems. Our main contribution is an O(w)-competitive algorithm, where {w} is the length of an IP address. We also derive a lower bound which shows that our result is asymptotically optimal within a natural class of algorithms, based on so-called sticks.
KW - competitive analysis
KW - Prefix aggregation
KW - software-defined networking
UR - http://www.scopus.com/inward/record.url?scp=85041229567&partnerID=8YFLogxK
U2 - 10.1109/TNET.2017.2787419
DO - 10.1109/TNET.2017.2787419
M3 - Journal article
AN - SCOPUS:85041229567
SN - 1063-6692
VL - 26
SP - 591
EP - 604
JO - IEEE/ACM Transactions on Networking
JF - IEEE/ACM Transactions on Networking
IS - 1
ER -