Abstract Directed Acyclic Graph (DAG) workflows are widely used for large-scale data analytics in cluster-based distributed computing systems. The performance model for a DAG on data-parallel frameworks (e.g., MapReduce) is a research challenge because the allocation of preemptable system resources among parallel jobs may dynamically vary during execution. This resource allocation variation during execution makes it difficult to accurately estimate the execution time. In this paper, we tackle this challenge by proposing a new cost model, called Bottleneck Oriented Estimation (BOE), to estimate the allocation of preemptable resources by identifying the bottleneck to accurately predict task execution time. For a DAG workflow, we propose a state-based approach to iteratively use the resource allocation property among stages to estimate the overall execution plan. Furthermore, to handle the skewness of various jobs, we refine the model with the order statistics theory to improve estimation accuracy. Extensive experiments were performed to validate these cost models with HiBench and TPC-H workloads. The BOE model outperforms the state-of-the-art models by a factor of five for task execution time estimation. For the refined skew-aware model, the average prediction error is under $$3\%$$ 3 % when estimating the execution time of 51 hybrid analytics (HiBench) and query (TPC-H) DAG workflows.

Inter-job Write once read many (WORM) scenario is ubiquitous in MapReduce applications that are widely deployed on enterprise production systems. However, traditional MapReduce auto-tuning techniques can not address the inter-job WORM scenario. To address the shortcomings in existing works, this work presents a novel online cross-layer solution, FORESEER. It can automatically predict workloads' data access information and tune data placement parameters to optimize the over-all performance for an inter-job WORM scenario. In our experiments, we observe that FORESEER can achieve significant performance speedup (up to 37%) compared with previous work.

MapReduce and Spark are two very popular open source cluster computing frameworks for large scale data analytics. These frameworks hide the complexity of task parallelism and fault-tolerance, by exposing a simple programming API to users. In this paper, we evaluate the major architectural components in MapReduce and Spark frameworks including: shuffle, execution model, and caching, by using a set of important analytic workloads. To conduct a detailed analysis, we developed two profiling tools: (1) We correlate the task execution plan with the resource utilization for both MapReduce and Spark, and visually present this correlation; (2) We provide a break-down of the task execution time for in-depth analysis. Through detailed experiments, we quantify the performance differences between MapReduce and Spark. Furthermore, we attribute these performance differences to different components which are architected differently in the two frameworks. We further expose the source of these performance differences by using a set of micro-benchmark experiments. Overall, our experiments show that Spark is about 2.5x, 5x, and 5x faster than MapReduce, for Word Count, k-means, and PageRank, respectively. The main causes of these speedups are the efficiency of the hash-based aggregation component for combine, as well as reduced CPU and disk overheads due to RDD caching in Spark. An exception to this is the Sort workload, for which MapReduce is 2x faster than Spark. We show that MapReduce's execution model is more efficient for shuffling data than Spark, thus making Sort run faster on MapReduce.

Document stores that provide the efficiency of a schema-less interface are widely used by developers in mobile and cloud applications. However, the simplicity developers achieved controversially leads to complexity for data management due to lack of a schema. In this paper, we present a schema management framework for document stores. This framework discovers and persists schemas of JSON records in a repository, and also supports queries and schema summarization. The major technical challenge comes from varied structures of records caused by the schema-less data model and schema evolution. In the discovery phase, we apply a canonical form based method and propose an algorithm based on equivalent sub-trees to group equivalent schemas efficiently. Together with the algorithm, we propose a new data structure, eSiBu-Tree, to store schemas and support queries. In order to present a single summarized representation for heterogenous schemas in records, we introduce the concept of "skeleton", and propose to use it as a relaxed form of the schema, which captures a small set of core attributes. Finally, extensive experiments based on real data sets demonstrate the efficiency of our proposed schema discovery algorithms, and practical use cases in real-world data exploration and integration scenarios are presented to illustrate the effectiveness of using skeletons in these applications.

MapReduce based data-intensive computing solutions are increasingly deployed as production systems. Unlike Internet companies who invent and adopt the technology from the very beginning, traditional enterprises demand easy-to-use software due to the limited capabilities of administrators. Automatic job optimization software for MapReduce is a promising technique to satisfy such requirements. In this paper, we introduce a toolkit from IBM, called MRTuner , to enable holistic optimization for MapReduce jobs. In particular, we propose a novel Producer-Transporter-Consumer (PTC) model, which characterizes the tradeoffs in the parallel execution among tasks. We also carefully investigate the complicated relations among about twenty parameters, which have significant impact on the job performance. We design an efficient search algorithm to find the optimal execution plan. Finally, we conduct a thorough experimental evaluation on two different types of clusters using the HiBench suite which covers various Hadoop workloads from GB to TB size levels. The results show that the search latency of MRTuner is a few orders of magnitude faster than that of the state-of-the-art cost-based optimizer, and the effectiveness of the optimized execution plan is also significantly improved.

Peer-to-Peer SIP (P2PSIP) is proposed to provide fully distributed multimedia communication systems. This paper focuses on analysis of call setup delay "(CSD) of P2PSIP system to evaluate whether it could provide equivalent signaling performance to that of traditional SIP or telephone networks. Call setup delay is composed of lookup latency in DHT overlay and INVITE transaction latency, and mainly decided by Round Trip Time (RTT) experienced on hops and message exchange procedures of lookup and INVITE transactions. Simulation with active measurement RTT data showed that call setup delay ranges widely from under 100 ms to more than ten seconds, and lookup latency takes up more than 60% of call setup delay. It is concluded that P2PSIP system within limited geographic range could achieve acceptable signaling latency, and efficient latency optimization should be considered to ensure the signaling performance when P2PSIP system is used spread across the public Internet.

Various characteristics of applications determine different requirements of mobility management schemes. Realtime applications especially lay strict limitation on handoff latency and latency stretch. This limitation is exacerbated when system robust, scalability and load balancing are required simultaneously. In this paper, we present a peer-to-peer based mobility support scheme that keeps advantages of P2P on robustness and scalability as well as optimizes handoff latency and latency stretch. Moreover, a proxy handoff mechanism is proposed to ensure the optimal performance in movement. Analysis and experiments based on OpenDHT reveal proxy handoff works effectively and handoff latency about 50 ms with latency stretch value 1.14 can be achieved.

P2P SIP is proposed to leverage Peer-to-Peer computing to control multimedia sessions in a decentralized manner. The deployment and maintenance cost of P2PSIP is reduced compared to conventional SIP. In this paper, we propose a hierarchical P2PSIP system to address the connectivity and overhead problems which haven't been solved in the P2PSIP literature. The hierarchical P2PSIP system is implemented under Linux, which demonstrates the feasibility of the proposed scheme. Finally, exhaustive simulations are performed to evaluate the performance of various P2PSIP schemes. Results indicate that the hierarchical approach not only solves the connectivity problem caused by heterogeneous overlays, but also performs more efficiently than the flat scheme when the percentage of nodes in the upper level overlay is less than 10%.

The cluster-based wireless sensor network (WSN) can enhance the whole network lifetime. In each cluster, the cluster head (CH) plays an important role in aggregating and forwarding data sensed by other common nodes. A major challenge in the WSN is the appropriate cluster head selection approach. In this paper, we propose a centralized cluster head selection approach using analytical hierarchy process (AHP). Three factors contributing to the network lifetime are considered and they are energy, mobility and the distance to the involved cluster centroid respectively. Simulation results demonstrate that the proposed approach is effective in prolonging the network lifetime