For many data-parallel computing systems like Spark, a job usually consists of multiple computation stages and inter-stage communication (i.e., coflows). Many efforts have been done to schedule coflows and jobs independently. The simple combination of coflow scheduling and job scheduling, however, would prolong the average job completion time (JCT) due to the conflict. For this reason, we propose a new abstraction of scheduling unit, named coBranch, which takes the dependency between computation stages and coflows into consideration, to schedule coflows and jobs jointly. Besides, mainstream coflow schedulers are order-preserving, i.e., all coflows of a high-priority job are prioritized than those of a low-priority job. We observe that the order-preserving constraint incurs low inter-job parallelism. To overcome the problem, we employ an urgency-based mechanism to schedule coBranches, which aims to decrease the average JCT by enhancing the inter-job parallelism. We implement the urgency-based coBranch Scheduling (BS) method on Apache Spark, conduct prototype-based experiments, and evaluate the performance of our method against the shortest-job-first critical-path method and the FIFO method. Results show that our method achieves around 10 and 15 percent reduction in the average JCT, respectively. Large-scale simulations based on the Google trace show that our method performs better and reduces JCT by 23 and 35 percent, respectively.

Under-allocating or over-allocating computation resources (e.g., CPU cores) can prolong the completion time of data-parallel jobs in a distributed system. We present a predictor, ReLocag, to find the near-optimal number of CPU cores to minimize job completion time (JCT). ReLocag includes a graph convolutional network (GCN) and a fully-connected network (FCNN). The GCN learns the dependency between operations from the workflow of a job, and then the FCNN takes the workflow dependency together with other features (e.g., the input size, the number of CPU cores, the amount of memory, and the number of computation tasks) as input for JCT prediction. The prediction result can guide the user to determine the near-optimal number of CPU cores. Besides, we propose two effective strategies to overcome the time-consuming issue of training sample collection in big data applications. First, we develop an adaptive sampling method to collect essential samples judiciously. Second, we further design a cross-application transfer learning model to exploit the training samples collected from other applications. We conduct extensive experiments in a Spark cluster for 7 types of exemplary Spark applications. Results show that ReLocag improves the JCT prediction accuracy by 4-14 percent. Moreover, the CPU core consumption decreases by 58.2 percent.

Since under-allocating computation resource (e.g., CPU cores) causes suboptimal JCTs of data-parallel jobs, users are inclined to request excessive computation resource to decrease JCTs. However, over-allocating computation resource for data-parallel jobs incurs considerable system overheads (e.g., network communication and disk I/O overhead), which prolong the job completion time. In this paper, we propose ReLoca towards the optimal allocation of computation resource with the objective of minimizing the job completion time. ReLoca employs a deep neural network to guide the allocation of computation resource, by learning the impact of the operations in data-parallel jobs on the system overhead and computation time. Since training samples are time-consuming to collect, we develop an adaptive sampling method to preferably collect high-quality samples and thus overcome the issue of data scarcity. We apply ReLoca to improve Spark and conduct real experiments with five typical applications in big data analytics. Results show that ReLoca significantly reduces the average job completion time. Compared with the state-of-the-art method, ReLoca has higher prediction accuracy, needs fewer training samples and decreases the sampling overhead. With the prediction by ReLoca, the JCT decreases by 29.85%.

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.

Multicast can jointly utilize the network resources when delivering the same content to a set of destinations; hence, it can effectively reduce the consumption of network resources more than individual unicast. The source of a multicast, however, does not need to be in a specific location as long as certain constraints are satisfied. This means the multicast can have uncertain sources, which could reduce the network bandwidth consumption more than a traditional multicast. Meanwhile, a reliable multicast becomes crucial in providing reliable services for many important applications. However, a prior minimal cost forest (MCF) for such a new multicast is not designed to support reliable transmissions. In this paper, we propose a novel reliable multicast routing with uncertain sources named ReMUS. To the best of our knowledge, we are the first to study the reliable multicast under uncertain sources. The goal is to minimize the sum of the transfer cost and the recovery cost, although finding such a ReMUS is very challenging. Thus, we design a sourcebased multicast method to solve this problem by exploiting the flexibility of uncertain sources when no recovery nodes exist in the network. Furthermore, we design a general multicast method to jointly exploit the benefits of uncertain sources and recovery nodes to minimize the total cost of ReMUS. We conduct extensive evaluations based on the real topology of Internet2. The results indicate that our methods can efficiently realize the reliable and bandwidth-efficient multicast with uncertain sources, irrespective of the settings of networks and multicasts.

Multicast is designed to jointly deliver content from a single source to a set of destinations. It can efficiently save the bandwidth consumption and reduce the load on the source. The appearance of SDN provides opportunities to deploy flexible protocols, including multicast and its variants. However, in many important applications, it is not necessary that the source of a multicast transfer has to be in specific location as long as certain constraints are satisfied. Such facts bring a novel multicast with uncertain sources, abbreviated as uncertain multicast. It brings new opportunities and challenges to reduce the bandwidth consumption. In this paper, we focus on the uncertain multicast and construct a forest with the minimum cost (MCF), to enable that each destination reaches to one and only one source. Prior approaches, relying on traditional multicast, remain inapplicable to the MCF problem. Therefore, we propose two (2+ε)-approximation methods, named P-MCF and E-MCF, which can be deployed in SDN controllers. We conduct experiments on our SDN testbed together with large-scale simulations under the random SDN network. All manifest that our MCF approach always occupies less network links and incurs less network cost for an uncertain multicast than the traditional Steiner minimum tree (SMT) of any related multicast, irrespective of the used network topology and the setting of multicast transmissions.