Tology-Aware Optimal Data Placement Algorithm for Network Traffic Optimization
Authors:
- 1 October 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 65 (8) , 2603-2617
Abstract
We propose a new optimal data placement technique to improve the performance of MapReduce in cloud data centers by considering not only the data locality but also the global data access costs. We first conducted an analytical and experimental study to identify the performance issues of MapReduce in data centers and to show that MapReduce tasks that are involved in unexpected remote data access have much greater communication costs and execution time, and can significantly deteriorate the overall performance. Next, we formulated the problem of optimal data placement and proposed a generative model to minimize global data access cost in data centers and showed that the optimal data placement problem is NP-hard. To solve the optimal data placement problem, we propose a topology-aware heuristic algorithm by first constructing a replica-balanced distribution tree for the abstract tree structure, and then building a replica-similarity distribution tree for detail tree construction, to construct an optimal replica distribution tree. The experimental results demonstrated that our optimal data placement approach can improve the performance of MapReduce with lower communication and computation costs by effectively minimizing global data access costs, more specifically reducing unexpected remote data access.Keywords
This publication has 17 references indexed in Scilit:
- OPTAS: Optimal Data Placement in MapReduce2013
- Improving ReduceTask data locality for sequential MapReduce jobs2013
- Expandable and Cost-Effective Network Structures for Data Centers Using Dual-Port ServersIEEE Transactions on Computers, 2012
- Purlieus2011
- Optimal Algorithms for Cross-Rack Communication Optimization in MapReduce Framework2011
- BCN: Expansible network structures for data centers using hierarchical compound graphs2011
- A data placement strategy in scientific cloud workflowsFuture Generation Computer Systems, 2010
- BCube2009
- A minimal algorithm for the multiple-choice knapsack problemEuropean Journal of Operational Research, 1995
- The 0–1 knapsack problem with multiple choice constraintsEuropean Journal of Operational Research, 1978