Brief Announcement: Dynamic Forwarding Table Aggregation without Update Churn: The Case of Dependent Prefixes

摘要

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.