Computer networks have become a critical infrastructure. Designing dependablecomputer networks however is challenging, as such networks should not only meetstrict requirements in terms of correctness, availability, and performance, butthey should also be flexible enough to support fast updates, e.g., due to achange in the security policy, an increasing traffic demand, or a failure. Theadvent of Software-Defined Networks (SDNs) promises to provide suchflexiblities, allowing to update networks in a fine-grained manner, alsoenabling a more online traffic engineering. In this paper, we present astructured survey of mechanisms and protocols to update computer networks in afast and consistent manner. In particular, we identify and discuss thedifferent desirable update consistency properties a network should provide, thealgorithmic techniques which are needed to meet these consistency properties,their implications on the speed and costs at which updates can be performed. Wealso discuss the relationship of consistent network update problems to classicalgorithmic optimization problems. While our survey is mainly motivated by theadvent of Software-Defined Networks (SDNs), the fundamental underlying problemsare not new, and we also provide a historical perspective of the subject.
展开▼
