DreamCreek is a system for grading the capacity of lithium-ion battery cells. An electric vehicle (EV) battery pack consists of thousands of lithium-ion cells; these cells must have a balanced capacity, measured by a formation and grading phase. This phase is costly, taking 14-20+ hours. DreamCreek aims to optimize this process, by collecting data from partial charge. Using the data, it determines the capacity of lithium-ion cells by employing both machine learning prediction and logic deduction, to reduce the usage of energy and increase the production. We will demonstrate how DreamCreek works with a guided tour, and show how it reduces the time of the formation and grading phase to 4 hours, with an error rate in the range of [0.06 %, 1%].

This paper studies cost-effective graph cleaning with a single machine. We adopt a rule-based method that may embed machine learning models as predicates in the rules. Graph cleaning with the rules involves rule discovery, error detection and correction. These tasks are both computation-heavy and I/O-intensive as they repeatedly invoke costly graph pattern matching, and produce a large amount of a large volume of intermediate results, among other things. In light of these, no existing single-machine system is able to carry out these tasks even on not-too-large graphs, even using GPUs. Thus we develop MiniClean, a single-machine system for cleaning large graphs. It proposes (1) a workflow that better fits a single machine by pipelining CPU, GPU and I/O operations; (2) memory footprint reduction with bundled processing and data compression; and (3) a multi-mode parallel model for SIMD, pipelined and independent parallelism, and their scheduling to maximize CPU--GPU synergy. Using real-life graphs, we empirically verify that MiniClean outperforms the SOTA single-machine systems by at least 65.34× and multi-machine systems with 32 nodes by at least 8.09×.

Mix networks, or mixnets, are one of the fundamental building blocks of anonymity systems. To defend against epistemic attacks, existing free-route mixnet designs require all clients to maintain a consistent, up-to-date view of the entire key directory. This, however, inevitably raises the performance concern under system scale-out: in a larger mixnet, a client will consume more bandwidth for updating keys in the background.This paper presents Periscoping, a key distribution protocol for mixnets at scale. Periscoping relaxes the download-all requirement for clients. Instead, it allows a client to selectively download a constant number of entries of the key directory, while guaranteeing the privacy of selections. Periscoping achieves this goal via a novel Private Information Retrieval scheme, constructed based on constrained Pseudorandom Functions. Moreover, the protocol is integrated seamlessly into the mixnet operations, readily applicable to existing mixnet systems as an extension at a minimal cost. Our experiments show that, with millions of mixes, it can reduce the traffic load of a mixnet by orders of magnitude, at a minor computational and bandwidth overhead.

We demonstrate MedHunter, a system for assisting the early stage of drug development. MedHunter builds a biomedical knowledge graph DDKG by integrating data from eleven biochemical libraries and data banks, and aligning entities from different data sources by means of heterogeneous entity resolution. It identifies drug-disease associations and protein-protein interactions in DDKG by employing graph association rules (GARs). GARs use graph patterns to extract relevant entities and embed ML models as predicates. MedHunter discovers GARs from DDKG and incrementally enriches DDKG with external data; it cleans DDKG with a special form of GARs. We demonstrate MedHunter for its (a) interfaces, (b) data enrichment/cleaning, and (c) applications in target identification, drug-drug interaction and protein-protein interaction.

This paper studies association rule discovery in a graphG1by referencing an external graphG2with overlapping information. The objective is to enrichG1with relevant properties and links fromG2. As a testbed, we consider Graph Association Rules (GARs). We propose a notion of graph joins to enrichG1by aligning entities acrossG1andG2. We also introduce a graph filtering method to support graph joins, by fetching only the data ofG2that pertains to the entities ofG1, to reduce noise and the size of the fused data. Based on these we develop a parallel algorithm to discover GARs acrossG1andG2. Moreover, we provide an incremental GAR discovery algorithm in response to updates toG1andG2. We show that both algorithms guarantee to reduce parallel runtime when given more processors. Better yet, the incremental algorithm is bounded relative to the batch one. Using real-life and synthetic data, we empirically verify that the methods improve the accuracy of association analyses by 30.4% on average, and scale well with large graphs.

This paper develops Planar (Plug and play PRAM), a single-machine system for graph analytics by reusing existing PRAM algorithms, without the need for designing new parallel algorithms. Planar supports both out-of-core and in-memory analytics. When a graph is too big to fit into the memory of a machine, Planar adapts PRAM to limited resources by extending a fixpoint model with multi-core parallelism, using disk as memory extension. For an in-memory task, it dedicates all available CPU cores to the task, and allows parallelly scalable PRAM algorithms to retain the property, i.e. , the more cores are available, the less runtime is taken. We develop a graph partitioning and work scheduling strategy to accommodate subgraph I/O, balance memory usage and reduce runtime, beyond traditional partitioners for multi-machine systems. Using real-life graphs, we empirically verify that Planar outperforms SOTA in-memory and out-of-core systems in efficiency and scalability.

We demonstrate PrismX (PRAM with SSDs as Memory eXtension), a single-machine system for graph analytics. PrismX allows users to make practical use of existing PRAM algorithms without any change. To cope with the limited DRAM capacity, it employs NVMe SSDs as memory extension. Leveraging graph preprocessing, PrismX implements a series of system optimization strategies, which automatically and transparently adapt to the runtime workload, no matter whether the computation is CPU-bound or I/O-bound. We demonstrate PrismX for its (1) ease of programming by reusing PRAM algorithms, (2) efficiency by comparing with the state-of-the-art graph systems, single-machine or multi-machine, in-memory or out-of-core; (3) parallel scalability of in-memory PRAM algorithms, reducing runtime when more CPU cores are available; and (4) applications in credit risk assessment.

This paper presents MiniGraph, an out-of-core system for querying big graphs with a single machine. As opposed to previous single-machine graph systems, MiniGraph proposes a pipelined architecture to overlap I/O and CPU operations, and improves multi-core parallelism. It also introduces a hybrid model to support both vertex-centric and graph-centric parallel computations, to simplify parallel graph programming, speed up beyond-neighborhood computations, and parallelize computations within each subgraph. The model induces a two-level parallel execution model to explore both inter-subgraph and intra-subgraph parallelism. Moreover, MiniGraph develops new optimization techniques under its architecture. Using real-life graphs of different types, we show that MiniGraph is up to 76.1x faster than prior out-of-core systems, and performs better than some multi-machine systems that use up to 12 machines.

It has become a recent trend that large volumes of data are generated, stored, and processed across geographically distributed datacenters. When popular data parallel frameworks, such as MapReduce and Spark, are employed to process such geo-distributed data, optimizing the network transfer in communication stages becomes increasingly crucial to application performance, as the inter-datacenter links have much lower bandwidth than intra-datacenter links. In this article, we focus on exploiting the flexibility of multi-path routing for inter-datacenter flows of data analytic jobs, with the hope of better utilizing inter-datacenter links and thus improve job performance. We design an optimal multi-path routing and scheduling strategy to achieve the best possible network performance for all concurrent jobs, based on our formulation of an optimization problem that can be transformed into an equivalent linear programming (LP) problem to be efficiently solved. As a highlight of this article, we have implemented our proposed algorithm in the controller of an application-layer software-defined inter-datacenter overlay testbed, designed to provide transfer optimization service for Spark jobs. With extensive evaluations of our real-world implementation on Google Cloud, we have shown convincing evidence that our optimal multi-path routing and scheduling strategies have achieved significant improvements in terms of job performance.

Data center networks need to provide low latency, especially at the tail, as demanded by many interactive applications. To improve tail latency, existing approaches require modifications to switch hardware and/or end-host operating systems, making them difficult to be deployed. We present the design, implementation, and evaluation of RepNet, an application layer transport that can be deployed today. RepNet exploits the fact that only a few paths among many are congested at any moment in the network, and applies simple flow replication to mice flows to opportunistically use the less congested path. RepNet has two designs for flow replication: (1) RepSYN, which only replicates SYN packets and uses the first connection that finishes TCP handshaking for data transmission, and (2) RepFlow which replicates the entire mice flow. We implement RepNet on node.js, one of the most commonly used platforms for networked interactive applications. node's single threaded event-loop and non-blocking I/O make flow replication highly efficient. Performance evaluation on a real network testbed and in Mininet reveals that RepNet is able to reduce the tail latency of mice flows, as well as application completion times, by more than 50 percent.

Modern stream processing frameworks, such as Spark Streaming, are designed to support a wide variety of stream processing applications, such as real-time data analytics in social networks. As the volume of data to be processed increases rapidly, there is a pressing need for processing them across multiple geo-distributed datacenters. However, these frameworks are not designed to take limited and varying inter-datacenter bandwidth into account, leading to longer query latencies. In this paper, we present the design and implementation of an extended Spark Streaming framework to automatically and optimally schedule tasks, select data flow routes and determine micro-batch sizes across geo-distributed datacenters in wide-area networks. To make these decisions, we propose a sparsity-regularized ADMM algorithm to efficiently solve a nonconvex optimization problem, based on readily measurable operating traces. Toward incremental real-world deployment, we take a non-intrusive approach to support flexible routing of micro-batches by adding a new DStream transformation we have developed to the existing Spark Streaming framework. As a result, our implementation can enforce scheduling decisions by modifying application workflows only. We have deployed our implementation on Amazon EC2 with emulated bandwidth constraints, and our experimental results on various types of queries have demonstrated the effectiveness of our proposed framework, as compared to the existing Spark Streaming scheduler and other data-locality-based heuristics.

Many applications like geo-replication need to deliver multiple copies of data from a single datacenter to multiple datacenters, which has benefits of improving fault tolerance, increasing availability and achieving high service quality. These applications usually require completing multicast transfers before certain deadlines. Some of the existing works only consider unicast transfers, which is not appropriate for the multicast transmission type. An alternative approach proposed by existing works was to find a minimum weight Steiner tree for each transfer. Instead of using only one tree for each transfer, we propose to use one or multiple trees, which increases the flexibility of routing, improves the utilization of available bandwidth, and increases the throughput for each transfer. In this paper, we focus on the multicast transmission type, propose an efficient and effective solution that maximizes throughput for all transfer requests while meeting deadlines. We also show that our solution can reduce packet reordering by selecting very few Steiner trees for each transfer. We have implemented our solution on a software-defined overlay network at the application layer, and our real-world experiments on the Google Cloud Platform have shown that our system effectively improves the network throughput performance and has a lower traffic rejection rate compared to existing related works.

Graph analytics has emerged as one of the fundamental techniques to support modern Internet applications. As real-world graph data is generated and stored globally, the scale of the graph that needs to be processed keeps growing. It is critical to efficiently process graphs across multiple geographically distributed datacenters, running wide-area graph analytics. Existing graph analytics frameworks are not designed to run across multiple datacenters well, as they implement a Bulk Synchronous Parallel model that requires excessive wide-area data transfers. In this paper, we present a new Hierarchical Synchronous Parallel model designed and implemented for synchronization across datacenters with a much improved efficiency in inter-datacenter communication. Our new model requires no modifications to graph analytics applications, yet guarantees their convergence and correctness. Our prototype implementation on Apache Spark can achieve up to 32% lower WAN bandwidth usage, 49% faster convergence, and 30% less total cost for benchmark graph algorithms, with input data stored across five geographically distributed datacenters.

Large volumes of raw data are naturally generated in multiple geographical regions. Modern data parallel frameworks may suffer from a degraded performance, due to the much lower inter-datacenter WAN bandwidth. We present Siphon, a new high-performance substrate that improves the ability of modern data parallel frameworks to optimize WAN transfers. Siphon aggregates inter-datacenter flows and routes them with the awareness of runtime network capacities. Following the principles of software-defined networking, Siphon is designed to accommodate a variety of flow scheduling algorithms that can improve the job level performance.

As increasingly large volumes of raw data are generated at geographically distributed datacenters, they need to be efficiently processed by data analytic jobs spanning multiple datacenters across wide-area networks. Designed for a single datacenter, existing data processing frameworks, such as Apache Spark, are not able to deliver satisfactory performance when these wide-area analytic jobs are executed. As wide-area networks interconnecting datacenters may not be congestion free, there is a compelling need for a new system framework that is optimized for wide-area data analytics. In this paper, we design and implement a new proactive data aggregation framework based on Apache Spark, with a focus on optimizing the network traffic incurred in shuffle stages of data analytic jobs. The objective of this framework is to strategically and proactively aggregate the output data of mapper tasks to a subset of worker datacenters, as a replacement to Spark's original passive fetch mechanism across datacenters. It improves the performance of wide-area analytic jobs by avoiding repetitive data transfers, which improves the utilization of inter-datacenter links. Our extensive experimental results using standard benchmarks across six Amazon EC2 regions have shown that our proposed framework is able to reduce job completion times by up to 73%, as compared to the existing baseline implementation in Spark.

It has become routine for large volumes of data to be generated, stored, and processed across geographically distributed datacenters. To run a single data analytic job on such geo-distributed data, recent research proposed to distribute its tasks across datacenters, considering both data locality and network bandwidth across datacenters. Yet, it remains an open problem in the more general case, where multiple analytic jobs need to fairly share the resources at these geo-distributed data-centers. In this paper, we focus on the problem of assigning tasks belonging to multiple jobs across datacenters, with the specific objective of achieving max-min fairness across jobs sharing these datacenters, in terms of their job completion times. We formulate this problem as a lexicographical minimization problem, which is challenging to solve in practice due to its inherent multi-objective and discrete nature. To address these challenges, we iteratively solve its single-objective subproblems, which can be transformed to equivalent linear programming (LP) problems to be efficiently solved, thanks to their favorable properties. As a highlight of this paper, we have designed and implemented our proposed solution as a fair job scheduler based on Apache Spark, a modern data processing framework. With extensive evaluations of our real-world implementation on Amazon EC2, we have shown convincing evidence that max-min fairness has been achieved using our new job scheduler.

Modern Internet applications are typically hosted in the public cloud, with multiple server instances running within geographically distributed datacenters. Thanks to the abundantly available bandwidth on wide-area links that interconnect these datacenters, it is conceivable that bandwidth-intensive applications may improve their performance by relaying their traffic through such an inter-datacenter network. However, there does not yet exist a cloud service that provides a turn-key solution to tap into such available bandwidth resources conveniently. In this paper, we design and implement Stemflow, a new system framework that provides Inter-Datacenter Overlay as a Service based on the software-defined networking principle. It offers an attractive foundation that helps an Internet application to transparently improve its scalability and performance by using inter-datacenter networks for its traffic. With Stemflow, all deployed server instances will construct an overlay atop an inter-datacenter network, and the routing decisions to relay application traffic are made by a centralized controller. The algorithms needed to make these decisions are customized to meet the needs of individual applications, and are cached within the data plane. We motivate and describe the design decisions, and present an extensive experimental evaluation in public cloud infrastructures, using two example applications as our case studies.

Network virtualization is a promising technology to enable multiple architectures to run on a single network. However, virtualization also introduces additional security vulnerabilities that may be exploited by attackers. It is necessary to ensure that the security requirements of virtual networks are met by the physical substrate, which however has not received much attention thus far. This paper represents an early attempt to consider the security issue in virtual network embedding, the process of mapping virtual networks onto physical nodes and links. We model the security demands of virtual networks by proposing a simple taxonomy of abstractions, which is enough to meet the variations of security requirements. Based on the abstraction, we formulate security-aware virtual network embedding as an optimization problem, proposing objective functions and mathematical constraints which involve both resource and security restrictions. Then a heuristic algorithm is developed to solve this problem. Our simulation results indicate its high efficiency and effectiveness.