Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-10204
For citation please use:
Main Title: Exploiting Locality of Churn for FIB Aggregation
Author(s): Sarrar, Nadi
Bienkowski, Marcin
Schmid, Stefan
Uhlig, Steve
Wuttke, Robert
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/11319
http://dx.doi.org/10.14279/depositonce-10204
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Snapshots of the Forwarding Information Base (FIB) in Internet routers can be compressed (or aggregated) to at least half of their original size, as shown by previous studies. In practice however, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation: keeping an optimally aggregated FIB in face of these routing updates is algorithmically challenging. A sensible trade-off has to be found between the aggregation gain and the number of changes to the aggregated FIB. This paper is the first to investigate whether the spatial and temporal locality properties of updates to the tree-like FIB data structure can be leveraged by online FIB aggregation. Our contributions include (a) an empirical study of the locality of updates in public Internet routing data, (b) the specification and simulations of our Locality-aware FIB Aggregation algorithm (LFA), and (c) a competitive analysis that sheds light on the performance of online algorithms under worst-case update streams. Our results show that even a simple algorithm like LFA can effectively exploit the locality of FIB churn to keep low the number of updates to the aggregated FIB, as most FIB updates affect only a small number of regions in the FIB.
Subject(s): router
switch design
Forwarding Information Base
FIB
aggregation
optimization
Issue Date: 2012
Date Available: 11-Jun-2020
Language Code: en
DDC Class: 004 Datenverarbeitung; Informatik
Series: Forschungsberichte der Fakultät IV - Elektrotechnik und Informatik / Technische Universität Berlin
Series Number: 2012-12
ISSN: 1436-9915
TU Affiliation(s): Fak. 4 Elektrotechnik und Informatik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
tr_2012-12.pdf
Format: Adobe PDF | Size: 524.32 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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