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.

Datacenters need high-bandwidth interconnection fabrics. Several researchers have proposed highly-redundant topologies with multiple paths between pairs of end hosts for datacenter networks. However, traffic management is necessary to effectively utilize the bisection bandwidth provided by these topologies. This requires timely detection of elephant flows-flows that carry large amount of data-and managing those flows. Previously proposed approaches incur high monitoring overheads, consume significant switch resources, and/or have long detection times. We propose, instead, to detect elephant flows at the end hosts. We do this by observing the end hosts's socket buffers, which provide better, more efficient visibility of flow behavior. We present Mahout, a low-overhead yet effective traffic management system that follows OpenFlow-like central controller approach for network management but augments the design with our novel end host mechanism. Once an elephant flow is detected, an end host signals the network controller using in-band signaling with low overheads. Through analytical evaluation and experiments, we demonstrate the benefits of Mahout over previous solutions.

OpenFlow is a great concept, but its original design imposes excessive overheads. It can simplify network and traffic management in enterprise and data center environments, because it enables flow-level control over Ethernet switching and provides global visibility of the flows in the network. However, such fine-grained control and visibility comes with costs: the switch-implementation costs of involving the switch's control-plane too often and the distributed-system costs of involving the OpenFlow controller too frequently, both on flow setups and especially for statistics-gathering.

Providers of "Infrastructure-as-a-Service" need datacenter networks that support multi-tenancy, scale, and ease of operation, at low cost. Most existing network architectures cannot meet all of these needs simultaneously.

Recently, there has been a tremendous growth in the number of installed distributed computing platforms such as those for content distribution networks, cloud computing infrastructures, and distributed data centers. Such distributed platforms need a scalable end-to-end (e2e) network monitoring component to provide Quality of Service (QoS) guarantees to the services and improve the overall performance. An important challenge for a network monitoring infrastructure is the periodicity of the measurements as this aspect trades off the monitoring overheads with staleness of the results. In the Network Genome project, we explore the relationships between different e2e network metrics with the aim of leveraging such relationships for reducing monitoring costs while maintaining measurement accuracy. We perform our analysis using long range network measurements from PlanetLab, where we have been collecting e2e network data (route, number of hops, capacity bandwidth and available bandwidth) as part of the S3 system since January 2006. In this paper, we focus on the correlation between the Capacity and Available Bandwidth metrics between host pairs in the PlanetLab testbed. Our analysis shows that the ranking of hosts with respect to their Capacity to/from a set of nodes is a good indicator of the ranking of hosts with respect to their Available Bandwidth to/from the same set of nodes.

The OpenFlow framework enables flow-level control over Ethernet switching, as well as centralized visibility of the flows in the network. OpenFlow's coupling of these features comes with costs, however: the distributed-system costs of involving the OpenFlow controller on flow setups, and the switch-implementation costs of involving the switch's control plane too often.

The Internet was designed as a packet-switched network in the 1960's and 1970's, with the explicit intent of sacrificing quality-of-service guarantees for an individual application in order to optimize channel usage and provide optimal median service for all applications. This approach was successful, since the application mix of the Internet heretofore has been dominated by applications with low quality-of-service needs: primarily bulk data transfer and low-bandwidth text- based interactive applications. As the Internet absorbs other networks and applications with strong quality-of-service requirements (television, voice over IP) , this tradeoff changes. We are faced with the problem of introducing the quality- of-service guarantees of circuit-switching into packet-switched networks. Fundamental change to the lower layers of the Internet stack have proven infeasible; even strongly-motivated, well-designed modifications which made transition a first-class design consideration have had difficult introductions. ATM and IPv6 are two recent examples. One effective transition strategy for new networking techniques has been the use of overlays. In this paper, we introduce the concept of a service overlay network, to offer circuit-switched behavior on legacy IP networks, and establish the requirements on the underlying IP network to make this strategy effective.

We present SMART, a self-tuning, bandwidth-aware monitoring system that maximizes result precision of continuous aggregate queries over dynamic data streams. While prior approaches minimize bandwidth cost under fixed precision constraints, they may still overload a monitoring system during traffic bursts. To facilitate practical deployment of monitoring systems, SMART therefore bounds the worst-case bandwidth cost for overload resilience. The primary challenge for SMART is how to dynamically select updates at each node to maximize query precision while keeping per-node monitoring bandwidth below a specified budget. To address this challenge, SMARTpsilas hierarchical algorithm (1) allocates bandwidth budgets in an ear-optimal manner to maximize global precision and (2) self-tunes bandwidth settings to improve precision under dynamic workloads. Our prototype implementation of SMART provides key solutions to (a) prioritize pending updates for multi-attribute queries, (b) build bounded fan-in, load-aware aggregation trees to improve accuracy, and (c) combine temporal batching with arithmetic filtering to reduce load and to quantify result staleness. Our evaluation using simulations and a network monitoring application shows that SMART incurs low overheads, improves accuracy by up to an order of magnitude compared to uniform bandwidth allocation, and performs close to the optimal algorithm under modest bandwidth budgets.

Packet classification is a function increasingly used in a number of networking appliances and applications. Typically, this consists of a set of abstract classifications, and a set of rules which sort packets into the various classifications. For packet classification at line speeds, Ternary Content-Addressable Memories (TCAMs) have become a norm in most networking hardware. However, TCAMs are expensive and power-hungry. Hence, a packet classification ruleset need to be minimized before populating the TCAM. In this paper, we formulate the Ruleset Minimization Problem for TCAM as an abstract optimization problem based on two-level logic minimization, and propose an exact solution and a number of heuristics. We present experimental results with two different datasets-artificial filter sets generated using ClassBench tool suite and a real firewall Access Control List (ACL) from a large enterprise. We observe an average reduction of 41% in artificial filter sets and 72.5% reduction in the firewall ACL using the proposed heuristics.

In the absence of end-to-end quality of service (QoS), overlay routing has been used as an alternative to the default best effort Internet routing. Using end-to-end network measurement, the problematic parts of the path can be bypassed, resulting in improving the resiliency and robustness to failures. Studies have shown that overlay paths can give better latency, loss rate, and TCP throughput. Overlay routing also offers flexibility as different routes can be used based on application needs. There have been very few proposals of using bandwidth as the main metric of interest, which is of great concern in media applications. We introduce our scheme BARON (Bandwidth-Aware Routing in Overlay Networks) that utilizes capacity between the end hosts to identify viable overlay paths and measures available bandwidth to select the best route. We propose our path selection approaches, and using the measurements between 174 PlanetLab nodes and over 13,189 paths, we evaluate the usefulness of overlay routes in terms of bandwidth gain. Our results show that among 658,526 overlay paths, 25% have larger bandwidth than their native IP routes, and over 86% of (source, destination) pairs have at least one overlay route with larger bandwidth than the default IP routes. We also present the effectiveness of BARON in preserving the bandwidth requirement over time for a few selected Internet paths.

Consider a distributed network with nodes arranged in a tree, and each node having a local value. We consider the problem of aggregating values (e.g., summing values) from all nodes to the requesting nodes in the presence of writes. The goal is to minimize the total number of messages exchanged. The key challenges are to define a notion of "acceptable" aggregate values, and to design algorithms with good performance that are guaranteed to produce such values. We formalize the acceptability of aggregate values in terms of certain consistency guarantees. We propose a lease-based aggregation mechanism, and evaluate algorithms based on this mechanism in terms of consistency and performance. With regard to consistency, we adapt the definitions of strict and causal consistency to apply to the aggregation problem. We show that any lease-based aggregation algorithm provides strict consistency in sequential executions, and causal consistency in concurrent executions. With regard to performance, we propose an online lease-based aggregation algorithm, and show that, for sequential executions, the algorithm is constant competitive against any offline algorithm that provides strict consistency. Our online lease-based aggregation algorithm is presented in the form of a fully distributed protocol, and the aforementioned consistency and performance results are formally established with respect to this protocol.

A distributed monitoring framework can serve as an important building block for constructing large-scale data aggregation and continuous event monitoring applications, such as IP traffic monitoring (DDoS attacks), network anomaly detection (Internet worms), accounting and bandwidth provisioning (hot spots, flash crowds), sensor monitoring and control, and grid resource monitoring. At the core of these applications is a distributed query engine that aggregates information and performs continuous tracking of queries over collections of physically-distributed and rapidly-updating data streams. The underlying aim is to provide a global view of information in the system at a reasonable cost and within a specified precision bound. To achieve this objective, a distributed monitoring system should (a) scale to a large number of streams and query attributes, (b) incur minimal communication overhead for aggregating query results, (c) be time responsive for quickly identifying anomalies, and (d) be able to bound the inaccuracy of the computed value for the aggregate function.

We present a Scalable Distributed Information Management System (SDIMS) that aggregates information about large-scale networked systems and that can serve as a basic building block for a broad range of large-scale distributed applications by providing detailed views of nearby information and summary views of global information. To serve as a basic building block, a SDIMS should have four properties: scalability to many nodes and attributes, flexibility to accommodate a broad range of applications, administrative isolation for security and availability, and robustness to node and network failures. We design, implement and evaluate a SDIMS that (1) leverages Distributed Hash Tables (DHT) to create scalable aggregation trees, (2) provides flexibility through a simple API that lets applications control propagation of reads and writes, (3) provides administrative isolation through simple extensions to current DHT algorithms, and (4) achieves robustness to node and network reconfigurations through lazy reaggregation, on-demand reaggregation, and tunable spatial replication. Through extensive simulations and micro-benchmark experiments, we observe that our system is an order of magnitude more scalable than existing approaches, achieves isolation properties at the cost of modestly increased read latency in comparison to flat DHTs, and gracefully handles failures.

Previous researchers have suggested the use of "lighthouses" to act as guides in directed state space search. The drawback of using lighthouses is that the user has to manually, derive them, through a potentially laborious examination of the design. Additionally specifying a large number of lighthouses results in wasted effort during the search. We present approaches to automatically generate high-quality lighthouses for hard-to-cover targets.