Brief Announcement:Dynamic Forwarding Table Aggregation withoutUpdate Churn: The Case of Dependent Prefixes
Marcin Bieńkowski, Nadi Sarrar, Stefan Schmid, Steve Uhlig · 2013
Abstract. This paper considers the problem of a route or SDN controller which manages a FIB table. The controller wants to aggregate the FIB entries as much as possible while minimizing the interactions with the FIB. We present a O(w)-competitive online algorithm for the aggregation of FIB tables in presence of routing updates, where w is the maximum length of an IP address. Our result is asymptotically optimal within a natural class of algorithms. Introduction and Model. This paper studies a new online problem arising in the context of forwarding table aggregation in a router or Software Defined Network (SDN) switch. The Forwarding Information Base (FIB) contains the rules used by the router to decide, for each packet, to which port it should be forwarded; a rule is simply an (IP prefix, port) pair. We will identify ports with