I. Introduction
A. The Network Update Problem
B. Our Contributions
C. Paper Organization
II. History of the Network Update Problem from the Origins to SDN
A. IGP Reconfigurations
B. Generalized Routing Reconfigurations in Traditional Networks
C. Updates of Software-Defined Networks
III. Taxonomy of Update Techniques
A. Generalized Network Update Problem (GNUP)
B. Classifying Update Techniques According to the Addressed GNUP Instance
C. Summary and Insights
IV. Update Techniques to Guarantee Connectivity Consistency
A. Guaranteeing Loop-Freedom
B. Guaranteeing Blackhole-Freedom
C. Summary and Insights
D. Open Problems
V. Update Techniques to Guarantee Policy Consistency
A. Definitions
B. Algorithms and Complexity
C. Related Optimization Problems
D. Summary and Insights
E. Open Problems
VI. Update Techniques to Guarantee Congestion-Aware Consistency
A. Definitions
B. Algorithms
C. Complexity
D. Related Optimization Problems
E. Summary and Insights
F. Open Problems
VII. Further Considerations in Network Updates
A. Relaxing Consistency Guarantees
B. Updates in Distributed Control Planes
C. Summary and Insights
VIII. From Theory to Practice
A. Ensuring Basic Communication with Network Devices
B. Applying Operational Sequences, Step by Step
C. Working Around Device Limitations
D. Avoiding Conflicts between Multiple Control-Planes
E. Updating the Control-Plane
F. Dealing with Events Occurring during an Update
IX. Future Research Directions
A. Charting the Complexity Landscape
B. Tailoring Update Mechanisms to Specific Networks
C. Refining our Models for Specific Technologies
D. New Update Problems Raised by Stateful Applications
E. Update Frequency
F. Dealing with Distributed Control Planes
G. Supporting In-Band Updates
X. Conclusion