On the Network Update Problem for Software Defined Networks.
This paper initiates a systematic study of Network Update Problem (NUP) which is the problem of correct and safe reconfiguration of Software Defined Networks (SDNs) by installing, disabling and modifying forwarding rules in flow-tables of network switches. We introduce an abstract formal model of SDN, use it to set up formally NUP, and focus on the problem of network configuration maintenance which is the basic variant of NUP: to restore a given SDN configuration after the loss of some forwarding rules as it may happens e.g. due to expiry of their time-outs. As the result we present two algorithms for safe and correct insertion of lost forwarding rules in SDN flow-tables.
Proceedings of the 5th Workshop "Program Semantics, Specification and Verification: Theory and Applications", 2014, Издательский дом ГУ ВШЭ Москва, pp. 26-37.