Update Algebra: Toward Continuous, Non-Blocking Composition of Network Updates in SDN

摘要: The ability to support continuous network configuration updates is an important for enabling Software Defined Networks (SDN) handle frequent or bursty changes. Current solutions updating SDN configurations focus on one single update at a time, leading slow, sequential (i.e., blocking) execution. In this paper, we develop algebra, novel, systematic, theoretical framework based abstract enable continuous, non-blocking, fast composition of multiple updates. Specifically, by modeling each data-plane operation in the set operations be executed as set-theoretical projection, algebra defines novel so that number projections same match remains constant regardless composed, substantial performance benefits. Specifying dependencies subset free monoid general case and partial ordering basic consistency, preserves even under partially-executed updates, guarantee correctness. We conduct asymptotic analysis, extensive benchmarking using real controller, integration with application demonstrate benefits algebra. particular, our analysis demonstrates independent-update dominant settings, completion time asymptotically despite growth executed. Our shows can achieve 16x reduction latency settings arrival rate only 1. 6/s. Hedera, traffic engineering application, reduce average link bandwidth utilization 30% compared