Split/Merge: System Support for Elastic Execution in Virtual Middleboxes

by Michael J. Freedman

Split/Merge introduces general techniques for virtualizing middlebox devices, such as firewalls, NATs, or IDSes. Unlike Virtual Machines, which virtualize the resources of a single physical machine, Split/Merge is designed to provide programmers with a single "big middlebox" abstraction, even though the middlebox service may actually be spread across multiple servers. Split/Merge also seeks to support elastic scaling, so that this "big middlebox" may be scaled out or spun in across multiple servers based on resource demands, without requiring significant effort by the programmer.

The ability to provide such an abstraction ultimately comes down to managing the program's state. For general-purpose computing, this seems like a hard problem: applications commonly used shared data structures in memory, so replicating applications across multiple servers may involve implementing distributed consistency protocols for shared state. Replicated state machines (RSMs) and distributed shared memory (DSM) tackle this exact problem, yet both lead to significant performance overhead or implementation complexity. To avoid these problems, the authors observe a unique aspect of middleboxes: Much of their state is either local and ephemeral (such as packet-processing state), or associated with specific network flows; little state typically must be shared between flows. Thus, if all the packets of a flow are directed to the same middlebox replica, the replica can perform most of its processing without updating others. Only global state, such as policy or counters, must be synchronized across replicas.

This paper describes the design and implementation of a middlebox architecture, called FreeFlow, that systematically deals with this state management. A system orchestrator can spin up or power down instances of a middlebox service, which serves to split or merge thesystem's partitionable state (e.g., its network flow table). The orchestrator integrates with Software-Defined Network (SDN) switches and updates forwarding tables to dynamically map active flows to the FreeFlow replicas that are responsible for them. In a similar manner, the system supports the automated migration of partitioned state across replicas for load (re-)balancing.

Still, some middleboxes use global state that must be kept consistent. The paper argues that most shared middlebox state, such as counters, only requires eventual (rather than strong) consistency. Leveraging the approach popularized by the Bayou storage system, FreeFlow has application-specific combiner functions that merge state updates between replicas. (For strong consistency, the paper suggests that the FreeFlow library can use a distributed lock service like Google's Chubby.)

The program committee appreciated that the work was clearly described and well motivated, and it addresses the problem with a sensible and realistic design. The paper includes detailed evidence that the design reflects real, pragmatic implementation experience. PC members were especially interested in how well FreeFlow works for more complex, stateful middlebox applications, rather than simple stateless NATs. Towards this end, the paper's port and evaluation of the open-source Bro intrusion detection system to FreeFlow was of particular relevance. Bro maintains counters per rule that should trigger an alert upon hitting a (global) threshold of matches; if an attack originates from multiple sources, these events may be detected by distinct replicas. Still, the eventually-consistent management of these shared counters seems suitable for this setting, as it merely leads to some delay in the triggering of an alert, not a violation of correctness. While the paper's evaluation only synchronized counters upon VM merging, the paper also discusses allowing application code to actively invoke state combination between replicas. Of course, the synchronization overhead increases with the number of replicas that share state, but this is true for any type of replicated state protocol.

Split/Merge is a promising architecture to build elastic and scale-out middlebox applications more easily. Unlike network or machine virtualization, however, Split/Merge does require application source-code modifications to integrate its FreeFlow library that manages partitioned and shared state. While this presents some additional barrier to adoption, the PC was hopeful for its continued development and use.