A Novel Pipeline Approach for Efficient Big Data Broadcasting

作     者：Wu, Chi-Jen Ku, Chin-Fu Ho, Jan-Ming Chen, Ming-Syan 

作者机构：Natl Taiwan Univ Dept Elect Engn Taipei 10617 Taiwan Acad Sinica Inst Informat Sci Taipei 11529 Taiwan Acad Sinica Res Ctr Informat Technol Innovat Taipei 11529 Taiwan 

出 版 物：《IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING》 

年 卷 期：2016年第28卷第1期

页      面：17-28页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Council of Taiwan  R.O.C. [NSC100-2219-E-001-002  NSC99-2221-E-001-013-MY3] 

主　　题：Big data computing data delivery algorithm cloud computing distributed computing big data management 

摘      要：Big-data computing is a new critical challenge for the ICT industry. Engineers and researchers are dealing with data sets of petabyte scale in the cloud computing paradigm. Thus, the demand for building a service stack to distribute, manage, and process massive data sets has risen drastically. In this paper, we investigate the Big Data Broadcasting problem for a single source node to broadcast a big chunk of data to a set of nodes with the objective of minimizing the maximum completion time. These nodes may locate in the same datacenter or across geo-distributed datacenters. This problem is one of the fundamental problems in distributed computing and is known to be NP-hard in heterogeneous environments. We model the Big-data broadcasting problem into a Lock-Step Broadcast Tree (LSBT) problem. The main idea of the LSBT model is to define a basic unit of upload bandwidth, r, such that a node with capacity c broadcasts data to a set of left perpendicular c/r right perpendicular children at the rate r. Note that r is a parameter to be optimized as part of the LSBT problem. We further divide the broadcast data into m chunks. These data chunks can then be broadcast down the LSBT in a pipeline manner. In a homogeneous network environment in which each node has the same upload capacity c, we show that the optimal uplink rate r* of LSBT is either c/2 or c/3, whichever gives the smaller maximum completion time. For heterogeneous environments, we present an O(nlog(2)) algorithm to select an optimal uplink rate r* and to construct an optimal LSBT. Numerical results show that our approach performs well with less maximum completion time and lower computational complexity than other efficient solutions in literature.