PaperlayerView exact revision on arXiv

Source-linked AI summary

Survey of Consistent Software-Defined Network Updates

Klaus-Tycho Foerster, Stefan Schmid, Stefano Vissicchio

arXiv:1609.02305v3cs.NIcs.DCcs.DS

TL;DR

Network updates must remain correct, available, performant, flexible, and fast despite diverse models and objectives. This survey organizes consistency properties, update techniques, costs, historical foundations, and open problems across SDN and legacy networks.

  • Problem

    The field lacks an accessible overview because research results, models, consistency notions, optimization objectives, and algorithmic techniques are rapidly multiplying.

  • Method

    The survey classifies consistent network updates, summarizes and tabularizes results, relates update problems to classic graph-theoretic optimization, and provides historical context.

  • Results

    The survey places diverse models, techniques, impossibility results, and practical challenges into context while identifying overlooked gaps and open technical and algorithmic problems.

  • Takeaways & Limitations

    Consistent network-update research spans SDN and legacy networks, with future work involving new technologies, network types, and complex stateful applications.

  • Takeaways & Limitations

    Update performance remains constrained by device behavior, including rule-installation delays that vary from seconds to minutes and depend on runtime factors.

Abstract

from arXiv · show

Computer networks have become a critical infrastructure. In fact, networks should not only meet strict requirements in terms of correctness, availability, and performance, but they should also be very flexible and support fast updates, e.g., due to policy changes, increasing traffic, or failures. This paper presents a structured survey of mechanism and protocols to update computer networks in a fast and consistent manner. In particular, we identify and discuss the different desirable consistency properties that should be provided throughout a network update, the algorithmic techniques which are needed to meet these consistency properties, and the implications on the speed and costs at which updates can be performed. We also explain the relationship between consistent network update problems and classic algorithmic optimization ones. While our survey is mainly motivated by the advent of Software-Defined Networks (SDNs) and their primary need for correct and efficient update techniques, the fundamental underlying problems are not new, and we provide a historical perspective of the subject as well.

I. INTRODUCTION

Computer networks require correctness, availability, performance, flexibility, and fast updates, but traditional operation remains error-prone and SDN introduces asynchronous coordination challenges. This survey organizes the growing literature on consistency properties, update techniques, tradeoffs, historical foundations, and open problems.

  • Motivation: Networks are critical infrastructure yet remain cumbersome and error-prone to operate, with misconfigurations causing issues such as forwarding loops.The paper contrasts strict network requirements with management practices described as largely unchanged since 1996.
  • Software-Defined Networking: SDN centralizes control logically and separates the control plane from forwarding hardware, enabling programmability and more principled network operation.OpenFlow expresses switch behavior through controller-installed match-action forwarding rules.
  • Software-Defined Networking: Asynchronous communication among controllers, switches, and their interconnecting network can produce delayed or inconsistent views and undesirable network behavior.The paper identifies correct and efficient updating under this asynchrony as a fundamental challenge.
  • Consistency and Performance: Consistency requirements and performance priorities depend on context, ranging from strong correctness in security-critical networks to basic guarantees such as loop-freedom.Short transient inconsistencies may be acceptable in some settings when basic consistency is preserved.
  • Survey Scope: The survey addresses a rapidly expanding field by comparing consistency properties, algorithmic techniques, performance tradeoffs, traditional-network foundations, and classic optimization connections.It also highlights that some update techniques can make consistent updates impossible and identifies open technical questions.

C. Paper Organization

The paper traces consistent network updates from traditional distributed routing protocols to SDN, using a forwarding-path example to show how asynchronous changes can create transient inconsistencies. It then frames the survey around historical techniques and the broader consistency problems enabled by controller-based networking.

  • Historical Scope: The survey begins with historical contributions addressing consistency during updates in traditional networks and later examines SDN-specific update problems.Traditional networks compute forwarding through distributed routing protocols, while SDN separates controllers from dataplane elements.
  • Running Example: Updating nodes one by one can create forwarding loops when links are traversed in opposite directions before and after the update.The example identifies links (v1, v2) and (v2, v3) as producing this risk.
  • Running Example: The generic update example changes forwarding paths between two network states, with arrows denoting active traffic paths and gray links denoting unused links.The example is used throughout the historical discussion to illustrate forwarding changes.
  • IGP Reconfigurations: In traditional IGP networks, operators change link weights, routers independently compute shortest paths, and the resulting configurations determine forwarding paths.The survey illustrates this with pre- and post-update IGP graphs corresponding to the two forwarding states.
  • IGP Reconfigurations: IGP convergence does not guarantee message timing or ordering, so temporary disagreement among routers can cause forwarding disruptions during topology changes.The survey describes a link-removal example in which routers receive the change at different times.
  • IGP Reconfigurations: Early IGP extensions addressed planned operations by coordinating router changes, including graceful restart and explicit synchronization to avoid forwarding loops.oFIB constrains when a router changes an entry until downstream next-hops have switched to their final next-hops.

1) Protocol extensions:

Traditional-network reconfiguration techniques evolved from protocol extensions to coordinated, progressively scheduled operations and Ships-in-the-Night updates. These approaches improve safety but face limits in flexibility, scalability, implementation complexity, and computational tractability.

  • Protocol extensions:: Protocol modifications cannot easily support custom reconfiguration objectives, broad configuration changes, or practical deployment across proprietary router software.They may be destination-specific, case-specific, complex, and operationally costly.
  • Coarse-grained operation scheduling:: Coarse-grained operation scheduling orders macro-operations to preserve consistency, but cannot prevent loops when a single operation itself creates a transient hazard.Examples include node additions, link-weight changes, and link removals.
  • Fine-grained operation scheduling:: Progressive link reweighting computes intermediate weights that can provably avoid transient forwarding loops during single-link changes.Multiple links can be handled by safely reweighting them one by one.
  • Ships-in-the-Night techniques:: Ships-in-the-Night runs initial and final routing processes simultaneously, then swaps configuration preferences across routers to support broader and faster reconfigurations.Because routers may use different configurations during the transition, the swap order must itself be chosen carefully.
  • Ships-in-the-Night techniques:: SITN reconfiguration-order existence is NP-complete to assess in some cases, while proposed methods include loop-enumerating linear programs and final-path-based heuristics.No SITN-based order guarantees loop freedom in every case.

B. Generalized Routing Reconfigurations in Traditional

Traditional reconfiguration techniques extend across multiple protocols and network settings, while SDN centralizes rule computation and installation. This increases update flexibility and frequency but also makes consistency during asynchronous updates a central concern.

  • Generalized Routing Reconfigurations in Traditional: Reconfiguration research covers routing domains, BGP, MPLS, route redistribution, global connectivity, and protocol-independent mechanisms.These settings introduce interactions that can produce transient anomalies even when individual protocol updates are safe.
  • Generalized Routing Reconfigurations in Traditional: Protocol-specific techniques depend on the considered protocols and their implementations, motivating protocol-independent approaches.One such design lets routers run multiple configurations and select one per packet using a header bit, with a loop-free commit protocol.
  • Updates of Software-Defined Networks: In pure SDN, a controller computes and installs packet-processing rules on network devices instead of relying on distributed device-side control logic.The controller can direct switches to use specified next-hops for destination traffic.
  • Updates of Software-Defined Networks: SDN updates are more frequent and critical because controllers support performance, security, and packet-processing requirements while devices do not independently react to topology changes.Updates may therefore be needed after failures, traffic surges, or requirement changes.
  • Updates of Software-Defined Networks: The 2-phase commit technique installs final rules before switching packets to them, using ingress tags so packets consistently follow either the old or final configuration.Subsequent work extends this approach with guarantees such as congestion freedom and with ordered rule-replacement algorithms.

III. TAXONOMY OF UPDATE TECHNIQUES

The survey abstracts network updates as consistency-preserving sequences of operations that transform an initial state into a final state. It organizes the problem around ordering, incremental execution, and optimization of update performance.

  • III. TAXONOMY OF UPDATE TECHNIQUES: The generalized formulation classifies update research by network setting, techniques, and algorithms independently of whether the setting is traditional networking or SDN.It abstracts assumptions such as rule granularity and supported operations.
  • III. TAXONOMY OF UPDATE TECHNIQUES: A network update computes operations that modify packet-processing rules and transform an initial network state into a final state.Operations may be direct rule replacements or coarse-grained actions such as IGP reweighting and configuration swapping.
  • III. TAXONOMY OF UPDATE TECHNIQUES: Consistency depends on the order in which operations are executed, because an unsafe sequence can create forwarding anomalies during the transition.The same operations can therefore be safe or unsafe depending on their ordering.
  • III. TAXONOMY OF UPDATE TECHNIQUES: Consistency requirements force updates to be incremental and require algorithms to compute operational sequences that preserve the target properties.Intermediate states must be provably disruption-free.
  • III. TAXONOMY OF UPDATE TECHNIQUES: Update performance is commonly optimized by minimizing time spent installing intermediate configurations and completing the overall update.Solutions are represented as rounds whose operations can be started in parallel while preserving consistency.

5) Final Operational Sequences:

The taxonomy classifies consistent update problems by routing model, operation type, consistency property, and performance goal. It distinguishes rule replacement, rule addition, and mixed techniques while emphasizing connectivity, policy, and capacity consistency.

  • Final Operational Sequences:: Update problems differ in network setting, admitted operations, consistency properties, and performance goals.The survey presents these dimensions independently of the underlying network setting.
  • Final Operational Sequences:: Network-update techniques target destination-based or per-flow routing, which differ in whether forwarding paths are confluent.Per-flow routing can depend on source, destination, or other flow identifiers.
  • Final Operational Sequences:: Rule-replacement techniques compute orders for replacing initial rules with final rules at granularities ranging from individual rules and devices to groups of rules and devices.The supported granularity depends on the target setting, such as OpenFlow or IGP link reweighting.
  • Final Operational Sequences:: Rule-addition techniques install both configurations or introduce helper rules so traffic can remain consistent while the update proceeds.Packet tags can select either the initial or final rules, while helper rules temporarily divert traffic.
  • Final Operational Sequences:: Mixed techniques combine rule replacement and rule addition to reduce device-memory overhead while retaining the flexibility of added rules.This combines the two principal update-operation categories.
  • Final Operational Sequences:: Connectivity consistency prevents blackholes and forwarding loops, policy consistency constrains allowable paths, and capacity consistency prevents transient link-capacity violations.The survey generally assumes these properties must hold at every moment under a strong consistency model.

4) Performance goals:

Consistent network-update research pursues three broad performance goals: maximizing parallel updates, minimizing update rounds, and addressing objectives across multiple flows. These goals are constrained by consistency properties and may trade off against one another.

  • Performance-goal classes: Three performance-goal classes are distinguished: link-based, round-based, and cross-flow objectives.The survey organizes update performance around parallel availability, total makespan, and objectives arising with multiple flows.
  • Link-based objectives: Link-based objectives maximize the number of switch rules that can be updated simultaneously without violating consistency.
  • Round-based objectives: Round-based objectives minimize makespan by scheduling safe switch-rule updates into simultaneous rounds or steps.
  • Cross-flow objectives: Cross-flow objectives include limiting capacity oversubscription and reducing controller-to-switch update messages.Message minimization concerns the number of interactions with switches, while congestion objectives may seek entirely congestion-free updates.
  • Objective-model relationships: Link-based and round-based objectives are commonly used with node-ordering algorithms and weak-consistency models, whereas congestion objectives fit capacitated consistency models.

2) Algorithms and Complexity:

The surveyed update problems connect scheduling objectives to graph optimization and complexity theory. Strong loop-free scheduling can be computationally difficult and vulnerable to greedy choices, while relaxed loop-freedom admits faster schedules and touch-minimizing combinations.

  • Objective trade-offs: Node-based and round-based objectives can conflict and produce vastly different update schedules.
  • Node-based complexity: Greedy node-based optimization is NP-hard under both strong and relaxed loop-freedom, despite polynomial-time algorithms for specific scenarios.The node-based objective maximizes the number of nodes updated in a round and is treated as a heuristic for minimizing rounds.
  • Round-based complexity: Strong loop-free scheduling is NP-complete for three rounds, and some instances require Ω(n) rounds even though greedy schedules can be Ω(n) rounds when O(1)-round schedules exist.
  • Relaxed loop-freedom: Relaxed loop-freedom has a deterministic worst-case schedule of O(log n) rounds.
  • Message-minimization: Optimal polynomial-time algorithms can merge individually consistent policy schedules into a global schedule with a minimal number of controller-to-switch touches.The merging result applies beyond loop-freedom when the consistency property holds for each individual policy.
  • Related optimization problems: The link-based problem corresponds to maximum acyclic subgraph, or equivalently to the dual minimum feedback arc set problem.These formulations support hardness results and connect network-update scheduling to classic graph optimization.

C. Summary and Insights

Loop- and blackhole-freedom are fundamental but difficult to optimize, motivating relaxed guarantees and continued work on complexity and memory limits. Policy-preserving methods extend these challenges to waypoint, path, and packet-consistency requirements, with tagging techniques trading consistency for switch-memory and packet overhead.

  • Connectivity consistency: Loop- and blackhole-freedom prevent disconnection of the logical routing graph, while loops additionally create congestion.
  • Optimization limits: Both node-based and round-based objectives are NP-hard to optimize, and logarithmically competitive round schedules currently require slightly relaxed consistency guarantees.Greedy methods can perform well for some node-based settings but poorly on adversarial makespan instances.
  • Open problems: Open questions include the complexity of relaxed loop-free scheduling, the necessity of Ω(log n) rounds, and the relationship between blackhole-free speedups and available memory.
  • Policy preservation: Policy-preserving updates address requirements such as firewall traversal, middlebox chains, and service-level path constraints beyond basic connectivity.
  • Policy consistency levels: Per-packet consistency restricts each packet to its initial or final path, whereas waypoint enforcement can preserve a required waypoint without requiring every transient path to be initial or final.The survey presents waypoint enforcement as less constraining than per-packet consistency in some settings.
  • Two-phase commit: Two-phase commit guarantees per-packet consistency using packet tags and dual forwarding rules, but requires additional switch rules and may consume memory, packet-header space, and tagging overhead.These requirements can interfere with other applications that need to install flow rules during updates.
  • Alternative techniques: Controller buffering can save switch resources during updates, but it adds packet-delivery delay, consumes network bandwidth, and requires temporary controller storage.

2) SDN-based update protocols:

Policy-preserving SDN updates balance rule-replacement ordering against tagging-based protocols and mixed techniques. The literature shows tradeoffs among solvability, algorithmic complexity, switch memory, and update speed.

  • Rule replacement ordering: Rule-replacement ordering can preserve waypoint enforcement, but some instances make simultaneous waypoint and loop-free guarantees impossible.The problem is NP-hard even to decide whether a safe replacement sequence exists.
  • Rule replacement ordering: GPIA computes polynomial-time replacement sequences that preserve per-packet consistency while maximizing updated switches and parallelism.It iteratively simulates candidate switch updates and adds safe replacements round by round.
  • Rule replacement ordering: Ordered replacements can safely update many switches but rarely complete an entire update in realistic topologies.This motivates combining ordering with a scope-limited 2-phase commit.
  • Mixed approaches: FLIP jointly optimizes rule replacements and tag-matching additions, using fewer additional rules than either 2-phase commit or sequential combination in the illustrated example.In Fig. 10, FLIP needs 1 additional rule, compared with 4 for 2-phase commit and 3 for sequential combination.
  • Protocol and algorithm tradeoffs: 2-phase commit avoids some ordering difficulties through packet tagging but consumes switch memory, whereas ordering-based methods may be unsolvable.Mixed approaches interleave rule additions and replacements to seek a better balance.

VI. UPDATE TECHNIQUES TO GUARANTEE CONGESTION-AWARE CONSISTENCY

Congestion-aware updates migrate flows between capacitated network states while preserving link capacities and minimum demands. The surveyed techniques range from staged movement and slack creation to linear programming, flow splitting, and dependency-based scheduling.

  • Definitions: Congestion-aware consistency requires respecting link capacities and avoiding rate-limiting any flow below min(Fold, Fnew).The model captures migration between an old and a new multi-commodity flow.
  • Definitions: The standard model abstracts away buffers and switch computation times, focusing instead on ongoing bandwidth violations from a mathematical flow-theory perspective.This abstraction does not exactly pinpoint every source of congestion.
  • Update mechanisms: 2-phase commit alone can cause congestion when one flow moves before another reaches its new path.The flow-migration example avoids this by sequencing the orange flow before the green flow.
  • Update mechanisms: Flow swapping is necessary for throughput optimization in the general case, requiring algorithms that preserve capacities beyond simple swaps.This establishes a stronger requirement than merely coordinating two predetermined paths.
  • Algorithms: With free capacity slack s on every flow link, SWAN guarantees migration in ⌈1/s⌉−1 updates.For 10% free capacity, the method requires 9 updates; slack can also be created by temporarily rate-limiting background traffic.
  • Algorithms: An LP formulation for splittable flows finds a consistent schedule with x updates when one exists, and binary search minimizes the update count.The formulation permits intermediate paths and can reroute flows anywhere in the network.
  • Algorithms: Splitting flows along old and new paths can create slack that makes consistent migration possible.Brandt et al. show splittable migration is always decidable in polynomial time using this strategy.

3) Spread flows over the network:

Flow-migration research increasingly combines route selection with update scheduling and studies the resulting complexity. Flexibility from intermediate paths and repeated moves can improve solvability, but also leaves major complexity questions open.

  • Spread flows over the network: Dependency graphs schedule updates after prerequisite flows complete, while dynamic variants adapt to uncertain switch and migration times.Multiple candidate paths can also be selected to reduce dependency stages and speed execution.
  • Spread flows over the network: Jointly computing new paths with the migration schedule can speed updates and solve more instances than treating paths as fixed input.For a single destination with multiple commodities, consistent migration is always possible when all flows can be admitted without capacity violations.
  • Spread flows over the network: Removing flow version tags reduces complexity overhead but prevents using 2-phase commit, leaving update ordering to avoid congestion and forwarding loops.Each node conceptually maintains old and new forwarding rules for each flow.
  • Complexity: Splittable-flow migration is polynomial-time decidable in some models, whereas unsplittability or memory restrictions can make the problem NP-hard.The complexity depends strongly on whether intermediate paths and repeated moves are allowed.
  • Complexity: Linear or integer programming can search for schedules by fixing the number of intermediate configurations and binary-searching for the fastest feasible value.The approach is complete only under restricted models when the number of updates is bounded.
  • Complexity: Allowing each flow to move only once makes the capacitated update problem NP-complete.This restriction limits the number of updates by the number of flows.
  • Complexity: Approximation and hardness theory remain limited, with few inapproximability results and most existing hardness proofs based on Partition.A known exception uses a reduction from MAX 3-SAT and applies to unit-size flows.

D. Related Optimization Problems

Flow migration connects consistent-update design to practical routing, optimization, and distributed-control problems. The survey highlights computational and deployment limits, unresolved complexity classifications, and tradeoffs introduced by relaxed consistency and synchronization.

  • Related optimization problems: Practical flow splitting may require multiple unsplittable paths, itself an NP-hard optimization, and can introduce packet reordering.Hash-based splitting, caches, and round-robin methods are alternative implementations.
  • Related optimization problems: Polynomial-time linear-programming methods can still be too slow for timely migration in large networks with many intermediate states.Integer programming for unsplittable flows worsens this deployment challenge.
  • Related optimization problems: Dependency-graph methods support old-or-new path restrictions, while tagging and 2-phase commit provide policy consistency for individual flows.The surveyed techniques address different combinations of congestion and policy requirements.
  • Open problems: The complexity of arbitrary repeated flow moves, especially with intermediate paths, remains unresolved across several complexity classes.Open questions include whether fastest schedules are linear, polynomial, or exponential and whether decision problems lie in NP, PSPACE, or EXPTIME.
  • Open problems: Formal guarantees are still missing for splittable migration without memory limits and intermediate paths.The authors suggest existing methods may apply, but a proof has not been provided.
  • Open problems: Jointly optimizing update schedules, route selection, and helper rules remains an open direction, including how to incorporate helper rules into dependency graphs.Current approaches may require manually defining intermediate states.
  • Relaxing consistency guarantees: Relaxed consistency can minimize inconsistent-state duration, while synchronized updates may reduce congestion but do not by themselves guarantee packet consistency.Clock synchronization also remains vulnerable to variable command execution times and failures.
  • Distributed control planes: Distributed control planes require additional coordination for consistent updates, which can add substantial latency in wide-area networks.Strongly consistent updates are unlikely when the control plane itself is weakly consistent.

C. Summary and Insights

Consistent updates require more than carefully computed sequences: practical systems must handle unreliable devices and communication, device-performance limits, and distributed controllers. The survey reviews these challenges and the mechanisms used to address them.

  • Practical systems: The survey complements theoretical results with practical challenges and reviews systems that automate consistent updates.Table VI summarizes the current status of these practical challenges.
  • Operational reliability: Unreliable devices and communication channels can prevent operations from being applied as computed, requiring execution verification.Messages may be lost or not applied by all devices upon reception.
  • Device limitations: Rule installation delays can vary from seconds to minutes, and depend on runtime factors such as installed rules and data-plane load.These limits matter especially for real-time SDN updates.
  • Mitigation mechanisms: Dionysus reduces multi-switch update latency by scheduling operations according to dynamic switch conditions.CoVisor and another approach reduce updates by eliminating redundant rule changes.
  • Distributed control planes: Distributed SDN controllers require additional coordination so concurrent updates reach a consistent state.Physically distributed control planes remain possible even when control is logically centralized.

F. Dealing with Events Occurring during an Update

The survey identifies concurrent events, limited complexity results, network-specific assumptions, application diversity, update frequency, and distributed in-band control as open challenges. It concludes that consistent network updates remain a broad research landscape spanning algorithms, technologies, and deployments.

  • Events during updates: Update algorithms assume stable network conditions, but unpredictable failures can change network behavior concurrently and independently.Such events cannot be prevented, although some work assesses their impact on update safety.
  • Algorithmic complexity: Many general update formulations are NP-hard, while polynomial-time optimal algorithms and approximation results are known for only limited cases.This applies across connectivity, policy, and capacity consistency models.
  • Network models: Existing models are relatively simple and leave mechanisms for specific graph classes, reconfigurable links, and diverse network contexts poorly understood.Datacenter and wide-area topologies may permit different update algorithms.
  • Application requirements: Different applications may require different consistency properties, especially when complex stateful applications modify network state.Traffic engineering and load balancing can impose different requirements.
  • Update frequency: Update frequency creates a computation-speed trade-off: multi-minute updates can be unsuitable for interactive traffic, while failures may demand rapid policy-consistent responses.The cited smart-grid approach uses fast two-phase commit but does not provide capacity consistency.
  • Distributed and in-band control: In-band control further complicates consistency because controllers may lose connectivity to switches that still require updates.The survey identifies distributed control and in-band operation as areas needing further study.
  • Survey conclusion: The survey organizes existing models, techniques, impossibility results, and practical challenges while identifying open technical and algorithmic problems.It also relates SDN update challenges to classic graph-theoretic optimization problems.
Loading 1609.02305v3…