PaperlayerView exact revision on arXiv

Source-linked AI summary

SNAP: Stateful Network-Wide Abstractions for Packet Processing

Mina Tahmasbi Arashloo, Yaron Koral, Michael Greenberg, Jennifer Rexford, David Walker

arXiv:1512.00822v2cs.NI

TL;DR

Stateful data-plane mechanisms make per-packet processing possible, but distributed stateful networks remain difficult to program efficiently and correctly. SNAP provides a one-big-switch abstraction with compiler-driven state distribution and routing, and its prototype was evaluated on about 20 applications.

  • Problem

    Distributed stateful devices are difficult to program efficiently and correctly, while controller-based stateful programs incur delay for per-packet processing.

  • Method

    SNAP uses a one-big-switch model with persistent arrays, atomic network transactions, xFDD analysis, and MILP-based joint state placement and traffic routing.

  • Results

    The SNAP language and compiler were implemented and evaluated on about 20 applications.

  • Takeaways & Limitations

    SNAP provides a centralized stateful programming model for distributing persistent state across networks.

  • Takeaways & Limitations

    No known hardware switch can implement an arbitrary number of SNAP stateful operations at line rate with strong consistency.

Abstract

from arXiv · show

Early programming languages for software-defined networking (SDN) were built on top of the simple match-action paradigm offered by OpenFlow 1.0. However, emerging hardware and software switches offer much more sophisticated support for persistent state in the data plane, without involving a central controller. Nevertheless, managing stateful, distributed systems efficiently and correctly is known to be one of the most challenging programming problems. To simplify this new SDN problem, we introduce SNAP. SNAP offers a simpler "centralized" stateful programming model, by allowing programmers to develop programs on top of one big switch rather than many. These programs may contain reads and writes to global, persistent arrays, and as a result, programmers can implement a broad range of applications, from stateful firewalls to fine-grained traffic monitoring. The SNAP compiler relieves programmers of having to worry about how to distribute, place, and optimize access to these stateful arrays by doing it all for them. More specifically, the compiler discovers read/write dependencies between arrays and translates one-big-switch programs into an efficient internal representation based on a novel variant of binary decision diagrams. This internal representation is used to construct a mixed-integer linear program, which jointly optimizes the placement of state and the routing of traffic across the underlying physical topology. We have implemented a prototype compiler and applied it to about 20 SNAP programs over various topologies to demonstrate our techniques' scalability.

1. INTRODUCTION

SNAP addresses the limitations of controller-based stateful SDN programming by offering a one-big-switch abstraction with persistent global arrays and atomic network transactions. Its compiler translates these programs into low-level switch mechanisms while jointly optimizing state placement and traffic routing, and the system is evaluated on about 20 applications.

  • Motivation: Controller round trips make simple stateful programs, including SYN-flood and DNS-amplification detection, inefficient because they incur significant delay.The earlier two-tiered model placed stateful logic on the controller while stateless rules ran on OpenFlow switches.
  • SNAP abstraction: SNAP provides a stateful, compositional language with persistent global arrays and a one-big-switch model that hides physical state placement from programmers.Arrays can be indexed by packet fields and modified as network conditions change.
  • SNAP abstraction: SNAP supports network transactions so multiple array updates occur atomically, enabling programs to learn network conditions and record state, per-flow information, or statistics.The introduction also describes applications such as stateful firewalls and fine-grained traffic monitoring in the paper context.
  • Compilation: The compiler uses extended forwarding decision diagrams to detect errors such as race conditions and generate a mixed-integer linear program for joint array placement and routing.The optimization minimizes network congestion while mapping one-big-switch programs onto concrete topologies.
  • Evaluation: About 20 applications were used to implement and evaluate SNAP and its compiler.The evaluation covered the language and compiler across applications, while the paper context reports experiments over various topologies.

2. SNAP SYSTEM OVERVIEW

SNAP programs process packets together with persistent network state, supporting applications such as DNS-tunnel detection and monitoring. Its compiler analyzes state dependencies and jointly determines state placement and packet paths, while rejecting ambiguous compositions caused by races.

  • Example programs: DNS-tunnel-detect tracks resolved addresses and unused-resolution counts to report clients exceeding a threshold, then composes with assign-egress for end-to-end forwarding.assign-egress selects output ports from destination IP addresses, and the policy is independent of internal network structure.
  • Programming model: SNAP models a program as transforming an incoming packet and current network state into transformed packets and updated state.Packet and state accesses refer to packet fields and user-defined state variables.
  • Example programs: SNAP supports parallel monitoring, such as incrementing count[inport] on packet arrival, but rejects compositions when shared state creates races.Parallel composition copies the incoming packet and executes both programs simultaneously; writes by one program that are read by another create ambiguous final state.
  • Network transactions: Processing reordered packets can split related updates across state variables, causing honeypot records to combine fields from different packets.The example may leave hon-ip[1] containing p1’s source IP while hon-dstport[1] contains p2’s destination port.
  • Compilation: The compiler transforms programs into xFDDs to infer packet-to-state dependencies, then uses that information to optimize state placement and forwarding paths.For the running example, the MILP places all state variables on D4 because traffic to and from the protected subnet must flow through D4; state may also be spread across the network.

3. SNAP

SNAP is a stateful high-level language built around an abstract one-big-switch topology, with predicates and policies that process packets while tracking state access. Its semantics defines state tests, composition, conflicts, conditionals, and atomic updates.

  • Language and semantics: SNAP programs use predicates and policies over an abstract one-big-switch topology, while evaluation maps a packet and starting state to packets, output state, and an access log.The language follows an algebraic structure patterned on NetCore/NetKAT.
  • Language and semantics: Predicates only read state and either pass or drop packets, whereas policies may modify packets and state; negation, disjunction, and conjunction propagate or combine evaluation results and logs.The basic predicates id, drop, and field tests produce empty logs.
  • State operations: The state test s[e1] = e2 passes only when array s at the evaluated index equals the evaluated value, and records a read of s.Expressions may be values, packet fields, or vectors of these.
  • Composition: Parallel or sequential composition is undefined when executions create read/write or write/write conflicts, and the implementation raises a compile error for parallel conflicts.Sequential composition requires consistent runs of the second policy across packets returned by the first.
  • Concurrency and atomicity: Conditional execution may have either branch access the same state, while atomic(p) ensures all state updated by p is updated atomically during compilation.Atomicity addresses inconsistencies caused by state residing on different switches and concurrent in-flight packets.

4. COMPILATION

SNAP compiles one-big-switch programs into a composable xFDD representation that exposes state access and dependencies, then uses a MILP to jointly determine traffic routing and state placement for a concrete topology.

  • Optimization: Routing and state placement are jointly optimized because flows needing the same state should be routed through a common location where that state is placed.The physical topology may provide multiple paths and possible state locations, making the two decisions interdependent.
  • Intermediate representation: State dependency analysis orders variables so any realization preserves the constraint that a variable written after reading another cannot precede it.Parallel composition introduces no dependencies, whereas sequential composition can impose ordering constraints.
  • Intermediate representation: The compiler translates SNAP programs into xFDDs, an intermediate representation that is composable and can be partitioned across the network.xFDDs provide an explicit specification of packet processing and encode tests and action sequences, including state operations.
  • State analysis: Packet-state mapping traverses each xFDD to associate flows with the state variables they read or write, informing subsequent routing decisions.The default flow definition covers packets traveling between a given ingress and egress port pair, though other flow notions are possible.
  • Optimization: The compiler formulates a MILP using the topology, state dependency graph, and packet-state mapping to output routing and state placement.The optimization extends the multi-commodity flow linear program and constrains each state variable to one physical location.

5. IMPLEMENTATION

SNAP is primarily implemented in Python, using Gurobi for state placement and routing, and emits per-switch NetASM instructions. The compiler translates xFDDs into branch and state-table instructions, while any programmable device supporting the required primitives can serve as a target.

  • Compiler implementation: The compiler is mostly implemented in Python, except for state placement and routing, which use Gurobi to solve the MILP.Its output for each switch is a set of switch-level instructions in NetASM, supported by a software switch.
  • Packet processing: Each switch processes packets with a customized per-switch xFDD and forwards them using SNAP-header fields in a match-action table.
  • xFDD translation: The compiler traverses each xFDD, generating branch instructions for test nodes that jump according to each test result.For state tests, it retrieves the value matching the packet’s index before branching.
  • xFDD translation: The compiler generates separate index and value tables for each state variable when translating xFDDs into NetASM instructions.
  • Target platforms: Any programmable device supporting match-action tables, branch instructions, and stateful operations can serve as a SNAP target.Prioritized match-action rules can implement branches, while multiple tables can represent xFDD paths.

6. EVALUATION

The evaluation shows that SNAP can express several stateful network functions while supporting compilation across campus and ISP topologies. Compiler costs are concentrated in one-time MILP creation and topology-dependent optimization, while incremental updates and routing reoptimization are faster.

  • Language expressiveness: SNAP implements several stateful network functions typically relegated to middleboxes, including examples drawn from Chimera, FAST, and Bohatei.Most examples use protocol fields at fixed packet offsets; some require session reassembly, which is orthogonal to language expressiveness.
  • Compiler performance: MILP model creation occurs only once during cold start, after which variable and constraint changes take a few milliseconds.Different events require only subsets of the compiler phases.
  • Experimental setup: The evaluation uses three campus networks and four RocketFuel ISP topologies, with directed links and ISP edge switches selected by degree.The experiments define OBS external ports using 70% of the lowest-degree ISP switches.
  • Compiler scalability: The largest evaluated policy combines all 20 examples and contains 35 state variables, while parallel composition preserves separate dependency graphs.Each component affects traffic destined for a separate egress port, and parallel composition introduces no read/write dependencies between state variables.
  • Compiler scalability: A 10-second compilation jump from 18 to 19 components occurs when the more complex TCP state machine is added, primarily due to xFDD generation.The composed programs are transformed into separate xFDDs and then combined into the whole-policy xFDD.
  • Compiler performance: ∼2.5 minutes is required for ST MILP on the biggest synthesized topology and ∼2.3 minutes on the biggest RocketFuel topology, whereas TE MILP recomputes paths in around a minute.ST MILP runs during cold starts or policy changes; TE MILP handles topology or traffic-matrix changes with fixed state placement.

7. DISCUSSION

SNAP discusses implementation choices and limitations for stateful data-plane operations, its relationship to middleboxes, and extensions for broader applications. It supports centralized programming while leaving state placement, consistency, and richer processing capabilities as important design considerations.

  • Data-plane implementation: SNAP implements small dictionaries with pre-allocated arrays and large sparse dictionaries with reactively populated tables.The reactive approach begins with a default entry and adds or updates entries as packets change the state variable.
  • Data-plane implementation: No known hardware switch implements an arbitrary number of SNAP stateful operations at line rate with strong consistency.SNAP therefore uses NetASM’s low-level primitives as its compiler backend for efficient and consistent data-plane implementations.
  • Middleboxes: SNAP expresses many stateful programs typically relegated to middleboxes while presenting a single explicit network policy.This gives programmers more control and customization over simpler stateful functionalities.
  • Middleboxes: Shared state variables force bidirectional connection traffic through the same node, exposing challenges similar to managing stateful middleboxes.SNAP does not claim to match all stateful middleboxes or replace them.
  • Extensions: Future work could shard state variables, support payload regular-expression tests on DPI-capable switches, and explore the resulting dependency and resource constraints.Sharding can partition a variable such as s[inport] into disjoint per-port variables, while DPI adds a content field containing packet payloads.

8. RELATED WORK

SNAP extends prior SDN language approaches with a richer stateful programming model. Compared with stateful NetKAT and compositional languages such as NetCore, SNAP supports multiple packet-indexed arrays and stateful primitives.

  • Stateful languages: Stateful NetKAT, developed concurrently with SNAP, guarantees consistent updates when transitioning between configurations in response to events.
  • Stateful languages: SNAP is richer and exponentially more compact than stateful NetKAT because it supports multiple indexable arrays updated using packet-header contents.Stateful NetKAT has one array, indexed and updated only by constant integers.
  • Compositional languages: NetCore and related compositional languages provide primitives for testing and modifying packet fields plus operators for combining programs, while SNAP adds stateful-programming primitives.

9. CONCLUSION · APPENDIX · A. FORMAL SEMANTICS OF SNAP

The paper introduces SNAP as a stateful SDN programming model and reports a prototype language and compiler evaluated on numerous sample programs. It also identifies extensions for broader stateful applications and presents formal semantics for SNAP.

  • 9. CONCLUSION: SNAP provides a one-big-switch abstraction for stateful SDN programming.The model includes persistent global arrays and network transactions.
  • 9. CONCLUSION: The paper develops algorithms to analyze and compile SNAP programs.These algorithms also address distributing program state across the network.
  • 9. CONCLUSION: The SNAP language and compiler were prototyped and evaluated on numerous sample programs.The evaluation is presented as support for the paper’s proposed ideas.
  • 9. CONCLUSION: SNAP explores extensions intended to support a wider range of stateful applications.The extensions build on the language, compilation algorithms, and prototype.
  • 9. CONCLUSION: Each proposed extension introduces additional research problems for SNAP’s language, compilation algorithms, and prototype.The conclusion characterizes these as new problems rather than completed capabilities.
  • A. FORMAL SEMANTICS OF SNAP: The appendix presents the formal semantics of SNAP.The appendix includes a figure titled “SNAP Semantics.”

B. STATE DEPENDENCY ALGORITHM

Figure 14 presents the st-dep function, which determines ordering constraints involving state variables.

  • State dependency algorithm: Figure 14 presents the st-dep function for state dependency analysis.The figure identifies the function used to determine ordering constraints against state variables.
  • State dependency algorithm: The st-dep function determines ordering constraints.These constraints govern the ordering considered in relation to state variables.
  • State dependency algorithm: The ordering constraints are defined against state variables.Figure 14 specifically describes the function’s role with respect to state variables.

C. EXTENDED STATE SHARDING

SNAP extends state sharding by partitioning arrays into disjoint per-port or per-IP components, allowing the compiler to place and route these components independently without synchronization.

  • Extended State Sharding: The compiler partitions s[inport] into s1 through sk, with si storing state for port i.Because the partitions store disjoint parts of s, they can be placed independently without synchronization.
  • Extended State Sharding: The same approach distributes t[srcip] into t1 through tk, each covering a disjoint subset of IP addresses.The OBS must replace each port u with its corresponding partition-aware representation.
  • Extended State Sharding: The MILP jointly decides placement and routing while allowing the state partitions to reside at different locations.This optimization applies to both per-port and per-IP sharding.

D. DECIDING EGRESS PORTS

SNAP handles cases where the egress port depends on unavailable state by forwarding packets toward the state needed to resolve the decision. When multiple egress choices share that state, traffic is distributed across their designated paths in proportion to capacity.

  • Handling state-dependent egress ports: The MILP optimizes paths for each ingress–egress pair even when the policy cannot determine the egress port at ingress.A packet entering at u may have multiple possible outports v1, · · ·, vk, whose paths are optimized separately.
  • Handling state-dependent egress ports: If processing gets stuck on state s that appears only in one egress’s state sequence, the packet is safely forwarded along that egress’s designated path.Reaching the switch holding s allows packet processing to continue and resolves the egress choice.
  • Handling state-dependent egress ports: When state s is needed by multiple possible egresses at the same sequence index, each corresponding path can carry its assigned traffic toward the switch holding s.These paths are capable of carrying at least d_uv volume for their respective ingress–egress traffic.
  • Handling state-dependent egress ports: Traffic requiring shared state s is sent over the corresponding paths in proportion to their capacities, whose total capacity matches the traffic volume requiring s.The same technique is used whenever packet processing stops because a needed state variable is not locally available.

E. FDD SEQUENTIAL COMPOSITION … Algorithm 4

The paper defines sequential FDD composition around a context that records inferred test outcomes, then uses helper algorithms to propagate packet-field mappings, filter actions, and compare expressions. The base composition procedure recursively selects branches or constructs new tests based on these inferred relationships.

  • E. FDD SEQUENTIAL COMPOSITION: Sequential composition recursively combines an action sequence with an FDD while accumulating test outcomes in a context T.Each context pair records a test and whether it evaluates yes or no.
  • E. FDD SEQUENTIAL COMPOSITION: Together, these helpers let sequential composition simplify tests using known assignments, inferred outcomes, and expression equality checks.The composition algorithm invokes field-map, filter, and eequal while traversing the FDD.
  • E. FDD SEQUENTIAL COMPOSITION: The seq procedure updates context with field assignments, infers branch outcomes, and recursively composes the relevant FDD branch.When neither outcome is inferred, it preserves the test by constructing a conditional result.
  • E. FDD SEQUENTIAL COMPOSITION: For tests comparing fields or expressions, seq uses inferred equality results to choose branches or create nested conditionals.The pseudocode handles field equality and state-indexed expression comparisons separately.
  • Algorithm 2: The field-map function records assignments from packet fields to values until a drop action terminates the scan.Non-assignment actions are skipped unless they are drop.
  • Algorithm 3: The filter function removes irrelevant actions while propagating known packet-field values into state expressions.It continues past identity actions, stops at drop, and substitutes mapped values in indexed expressions.
  • Algorithm 4: The eequal function first rejects expressions with unequal lengths, then compares corresponding values under context T.It returns false on an inferred inequality, both with an unresolved equality test, or true when all positions match.

F. SNAP POLICY EXAMPLES

SNAP policy examples demonstrate how persistent state supports security monitoring, access control, traffic measurement, sampling, selective dropping, load balancing, and attack mitigation. The examples use counters, pairwise state, protocol state, thresholds, and policy composition.

  • DNS security: Policies 1 and 2 detect suspicious DNS behavior by counting distinct domains per IP address or distinct IP addresses per domain name against a threshold.Policy 1 tracks domain-IP pairs and marks an IP malicious; Policy 2 tracks IP-domain pairs and marks a domain malicious.
  • Stateful monitoring: Policies 3–6 implement stateful firewalling and protocol monitoring using connection, DNS TTL, FTP channel, MTA, and mail-count state.The examples allow only CS-initiated connections, track TTL changes, authorize FTP data channels after control signals, and identify new MTAs sending many mails within 24 hours.
  • Threat detection: Policies 7–9 detect heavy hitters, sidejacking, and super-spreaders by maintaining per-flow or per-session state and updating counters on relevant packets.Sidejacking validation atomically records session identity mappings, while super-spreader detection increments on SYNs and decrements on FINs.
  • Measurement and sampling: Policies 10–14 classify flows by sizes of 1, 100, or 1000 and apply differentiated sampling rates, sampling every 5th, 50th, or 500th packet.Flow-size detection assigns SMALL, MEDIUM, or LARGE types, which select the corresponding sampler.
  • Traffic control: Policies 15 and 16 use dependency and TCP connection state to selectively drop MPEG B frames and apply per-connection load balancing.Policy 15 initializes dependency state for I frames and drops dependent B frames when the count reaches zero; Policy 16 invokes load balancing for established connections.
Loading 1512.00822v2…