We present Policy Graph Abstraction (PGA) that graphically expresses network policies and service chain requirements, just as simple as drawing whiteboard diagrams. Different users independently draw policy graphs that can constrain each other. PGA graph clearly captures user intents and invariants and thus facilitates automatic composition of overlapping policies into a coherent policy.

Software Defined Networking (SDN) and cloud automation enable a large number of diverse parties (network operators, application admins, tenants/end-users) and control programs (SDN Apps, network services) to generate network policies independently and dynamically. Yet existing policy abstractions and frameworks do not support natural expression and automatic composition of high-level policies from diverse sources. We tackle the open problem of automatic, correct and fast composition of multiple independently specified network policies. We first develop a high-level Policy Graph Abstraction (PGA) that allows network policies to be expressed simply and independently, and leverage the graph structure to detect and resolve policy conflicts efficiently. Besides supporting ACL policies, PGA also models and composes service chaining policies, i.e., the sequence of middleboxes to be traversed, by merging multiple service chain requirements into conflict-free composed chains. Our system validation using a large enterprise network policy dataset demonstrates practical composition times even for very large inputs, with only sub-millisecond runtime latencies.

Resource conflicts are inevitable on any shared infrastructure. In Software-Defined Networks (SDNs), different controller modules with diverse objectives may be installed on the SDN controller. Each module independently generates resource requests that may conflict with the objectives of a different module. For example, a controller module for maintaining high availability may want resource allocations that require too much core network bandwidth and thus conflict with another module that aims to minimize core bandwidth usage. In such a situation, it is imperative to identify and install resource allocations that achieve network wide global objectives that may not be known to individual modules, e.g., high availability with acceptable bandwidth usage. This problem has received only limited attention, with most prior work focused on detecting, avoiding, and resolving rule-level conflicts in the context of OpenFlow.

Providing bandwidth guarantees to specific applications is becoming increasingly important as applications compete for shared cloud network resources. We present CloudMirror, a solution that provides bandwidth guarantees to cloud applications based on a new network abstraction and workload placement algorithm. An effective network abstraction should enable applications to easily and accurately specify their requirements, while simultaneously enabling the infrastructure to provision resources efficiently for deployed applications. Prior research has approached the bandwidth guarantee specification by using abstractions that resemble physical network topologies. We present a contrasting approach of deriving a network abstraction based on application communication structure, called Tenant Application Graph or TAG. CloudMirror also incorporates a new workload placement algorithm that efficiently meets bandwidth requirements specified by TAGs while factoring in high availability considerations. Extensive simulations using real application traces and datacenter topologies show that CloudMirror can handle 40% more bandwidth demand than the state of the art (e.g., the Oktopus system), while improving high availability from 20% to 70%.

Software-Defined Networking (SDN) promises to enable vigorous innovation, through separation of the control plane from the data plane, and to enable novel forms of network management, through a controller that uses a global view to make globally-valid decisions. The design of SDN controllers creates novel challenges; much previous work has focused on making them scalable, reliable, and efficient.

While cloud computing providers offer guaranteed allocations for resources such as CPU and memory, they do not offer any guarantees for network resources. The lack of network guarantees prevents tenants from predicting lower bounds on the performance of their applications. The research community has recognized this limitation but, unfortunately, prior solutions have significant limitations: either they are inefficient, because they are not work-conserving, or they are impractical, because they require expensive switch support or congestion-free network cores.

Recent research on memory disaggregation introduces a new architectural building block — the memory blade — as a cost-effective approach for memory capacity expansion and sharing for an ensemble of blade servers. Memory blades augment blade servers' local memory capacity with a second-level (remote) memory that can be dynamically apportioned among blades in response to changing capacity demand, albeit at a higher access latency. In this paper, we build on the prior research to explore the software and systems implications of disaggregated memory. We develop a software-based prototype by extending the Xen hypervisor to emulate a disaggregated memory design wherein remote pages are swapped into local memory on-demand upon access. Our prototyping effort reveals that low-latency remote memory calls for a different regime of replacement policies than conventional disk paging, favoring minimal hypervisor overhead even at the cost of using less sophisticated replacement policies. Second, we demonstrate the synergy between disaggregated memory and content-based page sharing. By allowing content to be shared both within and across blades (in local and remote memory, respectively), we find that their combination provides greater workload consolidation opportunity and performance-per-dollar than either technique alone. Finally, we explore a realistic deployment scenario in which disaggregated memory is used to reduce the scaling cost of a memcached system. We show that disaggregated memory can provide a 50% improvement in performance-per-dollar relative to conventional scale-out.

Software Defined Networking, or SDN, based networks are being deployed not only in testbed networks, but also in production networks. Although fault-tolerance is one of the most desirable properties in production networks, there are not much study in providing fault-tolerance to SDN-based networks. The goal of this work is to develop a fault tolerant SDN architecture that can rapidly recover from faults and scale to large network sizes. This paper presents CORONET, a SDN fault-tolerant system that recovers from multiple link failures in the data plane. We describe a prototype implementation based on NOX that demonstrates fault recovery for emulated topologies using Mininet. We also discuss possible extensions to handle control plane and controller faults.

This paper presents Ally, a server platform architecture that supports compute-intensive management services on multi-core processors. Ally introduces simple hardware mechanisms to sequester cores to run a separate software environment dedicated to management tasks, including packet processing software appliances (e.g. for Deep Packet Inspection, DPI) with efficient mechanisms to safely and transparently intercept network packets. Ally enables distributed deployment of compute-intensive management services throughout a data center. Importantly, it uniquely allows these services to be deployed independent of the arbitrary OSs and/or hyper visor that users may choose to run on the remaining cores, with hardware isolation preventing the host environment from tampering with the management environment. Experiments using full system emulation and a Linux-based prototype validate Ally functionality and demonstrate low overhead packet interception, e.g., using Ally to host the well-known Snort packet inspection software incurs less over-head than deploying Snort as a Xen virtual machine appliance, resulting in up to 2× improvement in throughput for some workloads.

The Ensemble Routing architecture (presented at ANCS 2010) implements multipath routing for data center networks. Rather than managing individual flows, ensemble routing manages flows in groups or ensembles to provide scalable responsive management using simple hardware. Ensemble Routing combines: routing VLANs that define a set of diverse paths through complex networks, and load balancing algorithms to split traffic among those VLANS and optimize traffic flow. This extended abstract describes improved algorithms for the formation of routing VLANs and traffic load-balancing for Ensemble routing. The VLAN formation algorithms are improved by incorporating traffic flow estimates into the VLAN formation heuristics. The previous load balancing algorithm using a greedy heuristic is replaced by linear programming that determines optimal traffic splitting among VLANs. Simulations show that these mechanisms significantly enhance performance.

This paper describes Hash-Based Routing (HBR), an architecture that enhances Ethernet to support dynamic management for multipath networks in scalable datacenters. This work enhances HBR to support flow ensemble management for large-scale networks of arbitrary topology. Ensemble routing eliminates measurement and control for individual flows and instead manages using summary data thus providing a unique capability for reactive datacenter-wide network management. HBR provides seamless interoperability with Ethernet and supports the attachment of unmodified L2 hosts and devices including FCoE devices within converged fabrics. Simulation experiments demonstrate efficient multipath routing for a variety of scalable topologies. Optimized routing maintains efficiency in the presence of network faults and implements spatial Quality of Service to dynamically provision physical network hardware among co-hosted tenants or applications.

Most datacenter networks are based on specialized edge-core topologies, which are costly to build, difficult to maintain and consume too much power. We propose enhancements to layer-two (L2) Ethernet switches to enable multipath L2 routing in scalable datacenters. This replaces an expensive router with commodity switches. Our hash-based routing approach reuses and minimally extends hardware structures in high-volume switches, while exposing a powerful network management inter-face for multipath load balancing, QoS differentiation, and resilience to faults. Simulation results demonstrate near-optimal load balancing for uniform and non-uniform traffic patterns, and effective management of large datacenter networks independent of the number of traffic flows.

Most datacenter networks are based on specialized edge-core topologies, which are costly to build, difficult to maintain and consume too much power. We propose enhancements to layer-two (L2) Ethernet switches to enable multipath L2 routing in scalable datacenters. Our hash-based routing approach reuses and minimally extends hardware structures in high-volume switches, while exposing a powerful network management interface for multipath load balancing, QoS differentiation, and resilience to faults.

Device driver failures have been shown to be a major cause of system failures. Network services stress NIC device drivers, increasing the probability of NIC driver bugs being manifested as server failures. System virtualization is increasingly used for server consolidation and management. The isolated driver domain (IDD) architecture used by several virtual machine monitors, such as Xen, forms a natural foundation for making systems resilient to NIC driver failures. In order to realize this potential, recovery must be fast enough to maintain QoS for network services across NIC driver failures. We show that the standard Xen configuration, enhanced with simple detection and recovery mechanisms, cannot provide such QoS. However, with NIC drivers isolated in two virtual machines, in a primary/warm-spare configuration, the system can recover from an overwhelming majority of NIC driver failures in under 10 ms.

This paper presents mechanisms and optimizations to reduce the overhead of network interface virtualization when using the driver domain I/O virtualization model. The driver domain model provides benefits such as support for legacy device drivers and fault isolation. However, the processing overheads incurred in the driver domain to achieve these benefits limit overall I/O performance. This paper demonstrates the effectiveness of two approaches to reduce driver domain overheads. First, Xen is modified to support multi-queue network interfaces to eliminate the software overheads of packet demultiplexing and copying. Second, a grant reuse mechanism is developed to reduce memory protection overheads. These mechanisms shift the bottleneck from the driver domain to the guest domains, improving scalability and enabling significantly higher data rates. This paper also presents and evaluates a series of optimizations that substantially reduce the I/O virtualization overheads in the guest domain. In combination, these mechanisms and optimizations increase the maximum throughput achieved by guest domains from 2.9Gb/s to full 10 Gigabit Ethernet link rates.

Recently, the number of cores on general-purpose processors has been increasing rapidly. Using conventional programming models, it is challenging to effectively exploit these cores for maximal performance. An interesting alternative candidate for programming multiple cores is the stream programming model, which provides a framework for writing programs in a sequential-style while greatly simplifying the task of automatic parallelization. It has been shown that not only traditional media/image applications but also more general-purpose data-intensive applications can be expressed in the stream programming style.

Applications requiring high-speed TCP/IP processing can easily saturate a modern server. We and others have previously suggested alleviating this problem in multiprocessor environments by dedicating a subset of the processors to perform network packet processing. The remaining processors perform only application computation, thus eliminating contention between these functions for processor resources. Applications interact with packet processing engines (PPEs) using an asynchronous I/O (AIO) programming interface which bypasses the operating system. A key attraction of this overall approach is that it exploits the architectural trend toward greater thread-level parallelism in future systems based on multi-core processors. In this paper, we conduct a detailed experimental performance analysis comparing this approach to a best-practice configured Linux baseline system.

We present a new distributed checkpoint-restart mechanism, Cruz, that works without requiring application, library, or base kernel modifications. This mechanism provides comprehensive support for checkpointing and restoring application state, both at user level and within the OS. Our implementation builds on Zap, a process migration mechanism, implemented as a Linux kernel module, which operates by interposing a thin layer between applications and the OS. In particular, we enable support for networked applications by adding migratable IP and MAC addresses, and checkpoint-restart of socket buffer state, socket options, and TCP state. We leverage this capability to devise a novel method for coordinated checkpoint-restart that is simpler than prior approaches. For instance, it eliminates the need to flush communication channels by exploiting the packet re-transmission behavior of TCP and existing OS support for packet filtering. Our experiments show that the overhead of coordinating checkpoint-restart is negligible, demonstrating the scalability of this approach.

Virtual Machine (VM) environments (e.g., VMware and Xen) are experiencing a resurgence of interest for diverse uses including server consolidation and shared hosting. An application's performance in a virtual machine environment can differ markedly from its performance in a non-virtualized environment because of interactions with the underlying virtual machine monitor and other virtual machines. However, few tools are currently available to help debug performance problems in virtual machine environments.In this paper, we present Xenoprof, a system-wide statistical profiling toolkit implemented for the Xen virtual machine environment. The toolkit enables coordinated profiling of multiple VMs in a system to obtain the distribution of hardware events such as clock cycles and cache and TLB misses. The toolkit will facilitate a better understanding of performance characteristics of Xen's mechanisms allowing the community to optimize the Xen implementation.We use our toolkit to analyze performance overheads incurred by networking applications running in Xen VMs. We focus on networking applications since virtualizing network I/O devices is relatively expensive. Our experimental results quantify Xen's performance overheads for network I/O device virtualization in uni- and multi-processor systems. With certain Xen configurations, networking workloads in the Xen environment can suffer significant performance degradation. Our results identify the main sources of this overhead which should be the focus of Xen optimization efforts. We also show how our profiling toolkit was used to uncover and resolve performance bugs that we encountered in our experiments which caused unexpected application behavior.

Large-scale systems experience frequent failures which can result in unacceptably high service downtime or application execution time. To meet performance and availability requirements, the user must perform a complex design task including the selection and configuration of hardware and software components and mechanisms for handling failures. We believe users should be relieved of this burden by automating the design process in order to generate cost-effective solutions from high-level application requirements. In this paper, we present Aved, a proof of concept design automation engine which is a first step toward this goal. We describe how infrastructure choices, application models, and user requirements are represented with Aved to automate design space search and reason about design alternatives. We additionally present examples to illustrate how Aved can generate a complete picture of the cost-availability and cost-performance tradeoffs for the infrastructure design.

Infiniband system area networks (SANs) which use link-level flow control experience congestion spreading, where one bottleneck link causes traffic to block throughout the network. In this paper, we propose an end-to-end congestion control scheme that avoids congestion spreading, delivers high throughput, and prevents flow starvation. It couples a simple switch-based ECN packet marking mechanism appropriate for typical SAN switches with small input buffers, together with a source response mechanism that uses rate control combined with a window limit. The classic fairness convergence requirement for source response functions assumes network feedback is synchronous. We relax the classic requirement by exploiting the asynchronous behavior of packet marking. Our experimental results demonstrate that compared to conventional approaches, our proposed marking mechanism improves fairness. Moreover, rate increase functions possible under the relaxed requirement reclaim available bandwidth aggressively and improve throughput in both static and dynamic traffic scenarios.

Internet services experience frequent changes in demand, resource characteristics and service requirements. A service can meet its requirements with minimal cost only if the allocation of its distributed resources can be adaptively controlled. The design of adaptive control schemes requires a solid understanding of the dynamic characteristics of the distributed service, demand and resources. This study examines the dynamic properties of distributed demand and differs from prior demand characterization work by focusing on dynamic variations across clients, time and region which are crucial in adaptively allocating distributed resources. Our analysis of the demand for the 1998 World Cup web site finds that the dynamic behavior of a small subset of clients is representative of the entire demand, the churn in the active set of clients from day to day is relatively small and that regional demand shows significant, and predictable, variations in the hourly scales. These results will provide guidance for the design of adaptive policies.

InfiniBand System Area Networks using link-level flow control can experience congestion spreading, where one bottleneck link causes traffic to block throughout the network. End-to-end congestion control using Explicit Congestion Notification (ECN) packet marking has the potential to solve this problem. In this paper, we develop and evaluate ECN mechanisms for switches with input-buffered configuration (typical for InfiniBand), as opposed to traditional techniques that target output-buffered switches. Our mechanisms vary in two dimensions: the condition that triggers a marking event, and the set of packets marked at such an event. The experimental results show that our approaches avoid congestion spreading while preserving high network throughput. In addition, selective marking of packets at an input buffers on each marking event provides better fairness than a naive mechanism that marks only packets in a full input buffer. Finally, schemes that use state at both input and output ports to trigger marking events can improve fairness over purely input-triggered marking schemes.