Abstract
In a shared software-defined network (SDN), the controller should provide isolation guarantees across flows (users) to predict network performance and minimize disruption from some malicious flows. In an SDN, packets are forwarded by flow rules installed in flow tables, and the capacity of flow tables is usually limited by power and cost constraints so that a limited number of flows can be accommodated. To date, OpenFlow 1.4.0 introduces the flow rule replacement, which allows replacing existing flow rules with new ones once the flow table is full. This is called flow table overflow. Although flow table overflow may lead to an increase in packet delay, our experiments on an SDN testbed show that the network performance could benefit by admitting more flows through slightly overbooking the flow table resource. In this paper, we address the Flow table Overbooking isoLation guArantees problem (FOLA), which aims to maximize minimum progress of flows and minimize maximum flow table overflow. To that end, an algorithm with guaranteed minimum progress and bounded maximum flow table overflow is proposed. Trace-driven experiments on an SDN testbed show that our solution outperforms state-of-the-art methods for maximizing minimum progress in terms of the minimum progress and network throughput.