A data-parallel job is characterized as a directed acyclic graph (DAG) which usually consists of multiple computation stages and across-stage data transfers. However, classical DAG scheduling strategies like the critical path method ignore other stages off the main path and do not give specific consideration of data locality, transfer costs, etc. In practice, complicated DAGs include multiple paths which overlap with each other. The intersection of different paths in a DAG job forms an important synchronization. The synchronization significantly impacts the job completion time and however, no known scheduling methods are designed to speed up the completion time of the synchronization especially when complicated DAGs involve nested and hierarchical synchronizations. To the end, we propose a new abstraction, named branch, which is referred to a disjoint path in DAGs, and design a branch scheduling method to decrease the average job completion time of multiple data-parallel jobs. The branch scheduling method leverages the urgency of branches to speed up the synchronization of multiple parallel branches. We have implemented the BS method on Apache Spark and conducted prototype-based experiments. Compared with Spark FIFO and the shortest-job-first with the critical path methods, results show that the branch scheduling method achieves around 10-15% reduction in the average job completion time.

Flow completion times (FCTs) are critical for many cloud applications. To minimize the average FCT, recent transport designs, such as pFabric, PASE, and PIAS, approximate the Shortest Remaining Time First (SRTF) scheduling. A common, implicit assumption of these solutions is that the remaining time is only determined by the remaining flow size. However, this assumption does not hold in many real-world scenarios where applications generate data at diverse rates that are smaller than the network capacity. In this paper, we look into this issue from system perspective and find that the operating system (OS) kernel can be exploited to better estimate the remaining time of a flow. In particular, we use the rate of copying data from user space to kernel space to measure the data generation rate. We design RAX, a rate aware flow scheduling method, that calculates the remaining time of a flow more accurately, based on not only the flow size but also the data generation rate. We have implemented a RAX prototype in Linux kernel and evaluated it through testbed experiments and ns-2 simulations. Our testbed results show that RAX reduces FCT by up to 14.9%/41.8% and 7.8%/22.9% over DCTCP and PIAS for all/medium flows respectively.

This paper studies the communication pattern of data-parallel applications from the perspective of job execution, and discovers multiple inter-coflow dependencies. These inter-coflow dependencies, collectively named as semantic flow (seflow), can expose job-level semantics. It is observed that most distributed computing frameworks describe their job execution as directed acyclic graphs (DAG). So a seflow comprises not only all the coflows of a job but also the DAG-based relationship between them. Seflow, coflow and flow can be viewed as the top-down abstractions for communication of jobs.

Support Vector Machines (SVMs) are powerful classification tools. However, the model training is very time-consuming when meeting large scale data sets. Some efforts have been devoted to screening out non-support vectors (non-SVs) to accelerate the training. But their processes rely on prior knowledge of other classifiers with different parameters to screen out non-SVs. In this paper, we propose Directional Indicator Support Vector Machines (DISVMs) to efficiently identify non-SVs. DISVMs employs a directional indicator, which points to the approximately orthogonal direction of the separating hyperplane, to qualitatively define the location of different samples and thus identify non-SVs. Furthermore, DISVMs leverages a two-stage algorithm: the first stage is to compute the directional indicator. The second stage is to identify non-SVs using the indicator. To avoid misjudgement, we propose CnSV method for non-SVs based on the majority rule. DISVMs screens out non-SVs with light computation and little accuracy loss. Experiments show that our approach significantly reduces the total computation cost.

Task-aware flow schedulers collect task information across the data center to optimize task-level performance. However, the majority of the tasks, which generate short flows and are called tiny tasks, have been largely overlooked by current schedulers. The large number of tiny tasks brings significant overhead to the centralized schedulers, while the existing decentralized schedulers are too complex to fit in commodity switches. In this paper we present OPTAS, a lightweight, commodity-switch-compatible scheduling solution that efficiently monitors and schedules flows for tiny tasks with low overhead. OPTAS monitors system calls and buffer footprints to recognize the tiny tasks, and assigns them with higher priorities than larger ones. The tiny tasks are then transferred in a FIFO manner by adjusting two attributes, namely, the window size and round trip time, of TCP. We have implemented OPTAS as a Linux kernel module, and experiments on our 37-server testbed show that OPTAS is at least 2.2× faster than fair sharing, and 1.2× faster than only assigning tiny tasks with the highest priority.

The tasks of data-parallel computation jobs come up with diverse and time-varying resource requirements. The dynamic nature of task requirements brings challenges on making good scheduling decisions, due to it is hard to keep work-conserving. In this paper, we present BETS to cope with the requirement dynamics that aims at utilizing cluster resources fully. BETS employs a task model that represents for runtime task requirements, a coarse-grained task pipeline to make use of resources in a time-division multiplexing fashion, and fine-grained resource management to guarantee performance.

Internet-based virtual computing environment (iVCE) has been proposed to combine data centers and other kinds of computing resources on the Internet to provide efficient and economical services. Virtual machines (VMs) have been widely used in iVCE to isolate different users/jobs and ensure trustworthiness, but traditionally VMs require a long period of time for booting, which cannot meet the requirement of iVCE’s large-scale and highly dynamic applications. To address this problem, in this paper we design and implement VirtMan, a fast booting system for a large number of virtual machines in iVCE. VirtMan uses the Linux Small Computer System Interface (SCSI) target to remotely mount to the source image in a scalable hierarchy, and leverages the homogeneity of a set of VMs to transfer only necessary image data at runtime. We have implemented VirtMan both as a standalone system and for OpenStack. In our 100-server testbed, VirtMan boots up 1000 VMs (with a 15 GB image of Windows Server 2008) on 100 physical servers in less than 120 s, which is three orders of magnitude lower than current public clouds.

With the help of simulation tools, users can evaluate new proposals in cluster environment efficiently. However, current cloud simulators cannot meet the needs of application-driven simulation scenarios. In this paper, we propose Pallas, a task and network simulation framework that supports various cloud applications. Task-aware network scheduling and network-perceived task placement algorithms can be easily implemented in Pallas. We present the architecture and main components of Pallas and evaluate its effectiveness by comparing algorithm improvements to the actual results.

Data-parallel computing frameworks (DCF) such as MapReduce, Spark, and Dryad etc. Have tremendous applications in big data and cloud computing, and throw tons of flows into data center networks. In this paper, we design and implement FLOW PROPHET, a general framework to predict traffic flows for DCFs. To this end, we analyze and summarize the common features of popular DCFs, and gain a key insight: since application logic in DCFs is naturally expressed by directed acyclic graphs (DAG), DAG contains necessary time and data dependencies for accurate flow prediction. Based on the insight, FLOW PROPHET extracts DAGs from user applications, and uses the time and data dependencies to calculate flow information 4-tuple, (source, destination, flow size, establish time), ahead-of-time for all flows. We also provide generic programming interface to FLOW PROPHET, so that current and future DCFs can deploy FLOW PROPHET readily. We implement FLOW PROPHET on both Spark and Hadoop, and perform extensive evaluations on a testbed with 37 physical servers. Our implementation and experiments demonstrate that, with time in advance and minimal cost, FLOW PROPHET can achieve almost 100% accuracy in source, destination, and flow size predictions. With accurate prediction from FLOW PROPHET, the job completion time of a Hadoop TeraSort benchmark is reduced by 12.52% on our cluster with a simple network scheduler.

Infrastructure as a service (IaaS) allows users to rent resources from the Cloud to meet their various computing requirements. The pay-as-you-use model, however, poses a nontrivial technical challenge to the IaaS cloud service providers: how to fast provision a large number of virtual machines (VMs) to meet users' dynamic computing requests? We address this challenge with VMThunder, a new VM provisioning tool, which downloads data blockson demandduring the VM booting process and speeds up VM image streaming by strategically integrating peer-to-peer (P2P) streaming techniques with enhanced optimization schemes such as transfer on demand, cache on read, snapshot on local, and relay on cache. In particular, VMThunder stores the original images in a share storage and in the meantime it adopts a tree-based P2P streaming scheme so that common image blocks are cached and reused across the nodes in the cluster. We implement VMThunder in CentOS Linux and thoroughly test its performance. Comprehensive experimental results show that VMThunder outperforms the state-of-the-art VM provisioning methods, with respect to scalability, latency, and VM runtime I/O performance.