DocumentCode :
266091
Title :
Leveraging locality for FIB aggregation
Author :
Sarrar, Nadi ; Wuttke, Robert ; Schmid, Stefan ; Bienkowski, Marcin ; Uhlig, Steve
Author_Institution :
Tech. Univ. Berlin, Berlin, Germany
fYear :
2014
fDate :
8-12 Dec. 2014
Firstpage :
1930
Lastpage :
1935
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. However, the permanent stream of updates to the FIB due to routing updates complicates FIB aggregation in practice: keeping a (near-)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 complexity of handling routing updates. This paper investigates whether the spatial and temporal locality properties of routing updates conceal opportunities for improving this trade-off in online FIB aggregation. Our contributions include an empirical study of the locality of updates in public Internet routing data. To facilitate this study, we design the Locality-aware FIB Aggregation (LFA) algorithm. We show, that an algorithm as simple as LFA can effectively leverage the locality of FIB churn to keep low the number of updates to the aggregated FIB, as within time periods of a few seconds or minutes, routing updates affect only a limited number of regions in the FIB.
Keywords :
Internet; telecommunication network routing; FIB aggregation; Internet routers; forwarding information base; locality-aware FIB aggregation algorithm; public Internet routing data; Algorithm design and analysis; Internet; Memory management; Next generation networking; Ports (Computers); Routing; Routing protocols;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Global Communications Conference (GLOBECOM), 2014 IEEE
Conference_Location :
Austin, TX
Type :
conf
DOI :
10.1109/GLOCOM.2014.7037090
Filename :
7037090
Link To Document :
بازگشت