Modeling and Optimization of MapReduce

ABSTRACT

MapReduce framework is widely used to parallelize batch jobs since it exploits a high degree of multi-tasking to process them. However, it has been observed that when the number of mappers increases, the map phase can take much longer than expected. This paper analytically shows that stochastic behavior of mapper nodes has a negative effect on the completion time of a MapReduce job, and continuously increasing the number of mappers without accurate scheduling can degrade the overall performance. We analytically capture the effects of stragglers (delayed mappers) on the performance. Based on an observed delayed exponential distribution (DED) of the response time of mappers, we then model the map phase by means of hardware, system, and application parameters. Mean sojourn time (MST), the time needed to sync the completed map tasks at one reducer, is mathematically formulated. Following that, we optimize MST by finding the task inter-arrival time to each mapper node. The optimal mapping problem leads to an equilibrium property investigated for different types of inter-arrival and service time distributions in a heterogeneous datacenter (i.e., a datacenter with different types of nodes). Our experimental results show the performance and important parameters of the different types of schedulers targeting MapReduce applications. We also show that, in the case of mixed deterministic and stochastic schedulers, there is an optimal scheduler that can always achieve the lowest MST.

[Tech Report] [Master Thesis] [IEEE Trans]

Last version > MapReduce_Performance_Optimization

This entry was posted in Conference Paper, Journal Paper, Research, Technical Report, Thesis Diman Tootaghaj, Fork-Join Queue, Mapper, MapReduce, Mean Sojourn Time, Modeling, MST, Reducer, Stochastic Optimization, Straggler, Straggling Mapper

www.personal.psu.edu/fuf111

Publications

• Discovering Triangles in Portraits for Supporting Photographic Creation, S He, Z Zhou, F Farhat, JZ Wang, IEEE Transactions on Multimedia, Aug 2017.

• Intelligent Portrait Composition Assistance — Integrating Deep-learned Models and Photography Idea Retrieval, F Farhat, MM Kamani, S Mishra, JZ Wang, July 2017.

• Skeleton Matching with Applications in Severe Weather Detection, MM Kamani, F Farhat, S Wistar, JZ Wang, Applied Soft Computing, May 2017.

• Detecting Dominant Vanishing Points in Natural Scenes with Application to Composition-Sensitive Image Retrieval, Z Zhou, F Farhat, JZ Wang, IEEE Transactions on Multimedia, May 2017.

• Shape matching using skeleton context for automated bow echo detection, MM Kamani, F Farhat, S Wistar, JZ Wang, Big Data (Big Data), 2016 IEEE International Conference on, 901-908, Dec 2016.

• Detecting Vanishing Points in Natural Scenes with Application in Photo Composition Analysis, Z Zhou, F Farhat, JZ Wang, arXiv preprint arXiv:1608.04267, 2016.

• Optimal Placement of Cores, Caches and Memory Controllers in Network On-Chip, DZ Tootaghaj, F Farhat, arXiv preprint arXiv:1607.04298, 2016.

• Towards Stochastically Optimizing Data Computing Flows, F Farhat, DZ Tootaghaj, M Arjomand, arXiv preprint arXiv:1607.04334, 2016.

• Stochastic Modeling and Optimization of Stragglers, F Farhat, D Zad Tootaghaj, Y He, et al. IEEE Transaction on Cloud Computing, 2016.

• Fork-Join Queue Modeling and Optimal Scheduling in Parallel Programming Frameworks, F Farhat, EECS Thesis, The Pennsylvania State University, 2015.

• Evaluating the Combined Impact of Node Architecture and Cloud Workload Characteristics on Network Traffic and Performance/Cost, DZ Tootaghaj, F Farhat, M Arjomand, P Faraboschi et al. Workload characterization (IISWC), 2015 IEEE international symposium on, 203-212, 2015.

• Towards blind detection of low-rate spatial embedding in image steganalysis, F Farhat, S Ghaemmaghami, IET Image Processing 9 (1), 31-42, 2015.

• Modeling and optimization of straggling mappers, F Farhat, DZ Tootaghaj, A Sivasubramaniam, MT Kandemir, CR Das, Technical report, Technical Report CSE-14-006, Pennsylvania State University, 2014.

• Security Weaknesses in PGP Protocol, F Farhat, M Heydari, MR Aref, 2013.

• Eigenvalues-based LSB steganalysis, F Farhat, A Diyanat, S Ghaemmaghami, MR Aref, The ISC International Journal of Information Security 4 (2), 97-106, 2012.

• Image steganalysis based on SVD and noise estimation: Improve sensitivity to spatial LSB embedding families, A Diyanat, F Farhat, S Ghaemmaghami, TENCON 2011-2011 IEEE Region 10 Conference, 1266-1270, 2011.

• Multi-dimensional correlation steganalysis, F Farhat, A Diyanat, S Ghaemmaghami, MR Aref, Multimedia Signal Processing (MMSP), 2011 IEEE 13th International Workshop, 2011.

• Game-theoretic approach to mitigate packet dropping in wireless Ad-hoc networks, DZ Tootaghaj, F Farhat, MR Pakravan, MR Aref, Consumer Communications and Networking Conference (CCNC), 2011 IEEE, 163-165, 2011.

• Risk of attack coefficient effect on availability of Ad-hoc networks, DZ Tootaghaj, F Farhat, MR Pakravan, MR Aref, Consumer Communications and Networking Conference (CCNC), 2011 IEEE, 166-168, 2011.

• Private Identification, Authentication and Key Agreement Protocol with Security Mode Setup, F Farhat, S Salimi, A Salahi, IACR Cryptology ePrint Archive, 2011.

• Locally Multipath Adaptive Routing Protocol Resilient to Selfishness and Wormholes, F Farhat, MR Pakravan, M Salmasizadeh, MR Aref, International Conference on Information Security Practice and Experience, 2010.

• An Extended Authentication and Key Agreement Protocol of UMTS, F Farhat, S Salimi, A Salahi, International Conference on Information Security Practice and Experience, 2009.

 

Click HOME to go to main page!

PIAKAP

Authentication and Key Agreement Protocol in 4G

Private Identification, Authentication and Key Agreement Protocol with Security Mode Setup, Farshid Farhat, Somayeh Salimi, Ahmad Salahi.

Abstract
Identification, authentication and key agreement protocol of UMTS networks with security mode setup has some weaknesses in the case of mutual freshness of key agreement, DoS-attack resistance, and efficient bandwidth consumption. In this article we consider UMTS AKA and some other proposed schemes. Then we explain the known weaknesses of the previous frameworks suggested for the UMTS AKA protocol. After that we propose a new protocol called private identification, authentication, and key agreement protocol (PIAKAP), for UMTS mobile network. Our suggested protocol combines identification and AKA stages of UMTS AKA protocol while eliminates disadvantages of related works and brings some new features to improve the UMTS AKA mechanism. These features consist of reducing the interactive rounds of the UMTS AKA with security mode setup and user privacy establishment.

ePrint, Research, Security and tagged Ahmad Salahi, Authentication, Identification, Key Agreement, Mobile Network, PIAKAP, Privacy, Security Protocol, Somayeh Salimi, UMTS on March 25, 2011.