Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Load scheduling for distributed edge computing: A communication-computation tradeoff

  • Published:
Peer-to-Peer Networking and Applications Aims and scope Submit manuscript

Abstract

Due to the intensive computation requirements of emerging applications and the limited computational capability of edge computing servers, the computation task must be executed on multiple edge servers in a distributive and cooperative manner. However, the large amount of information exchanged among the edge servers is a major obstacle for improving the computing performance. By utilizing the excess computational resource, coded MapReduce provides an effective approach to reduce the communication load. In this paper, we develop a stochastic load scheduling framework to complete the computation tasks with coded MapReduce considering the intrinsic tradeoff between the communication and computation loads. Our goal is to minimize the communication load under time-varying excess computational resources. We first reduce this problem to a task scheduling problem by exploiting the property of the computing repetition in the coded MapReduce framework. Since the task scheduling problem is still a stochastic optimization problem, it is generally difficult to solve. In the offline setting, we obtain the optimal computation load scheduling algorithm by adopting the augmented Lagrangian method. In the online setting, we derive a worst-case performance bound of the online equal task scheduling (ETS) algorithm by using competitive analysis. Furthermore, we make full use of past state information of computing resources for pre-planing and propose an improved algorithm based on the ETS algorithm in a learning manner. Finally, our proposed algorithm is evaluated by simulation to demonstrate that the proposed algorithms are superior over the conventional algorithms, and the performance gap between the online and offline algorithms is fairly small.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. To guarantee that all M tasks can be completed within time N, it is assumed that at least M/NC dedicated servers are assigned for the computation tasks. In addition to these dedicated servers, the computation tasks can also be executed at other idle servers, whose number is time-varying.

  2. The repetitive computing on the same edge server does not achieve any performance gain in the communication load.

References

  1. Meng X, Wang W, Zhang Z (2017) Delay-constrained hybrid computation offloading with cloud and fog computing. IEEE Access 5:21355–21367

    Article  Google Scholar 

  2. Talia D, Trunfio P (2010) How distributed data mining tasks can thrive as knowledge services. Commun ACM 53(7):132– 137

    Article  Google Scholar 

  3. Li S, Maddah-Ali MA, Avestimehr AS (2017) Coding for distributed fog computing. IEEE Commun Mag 55(4):34–40

    Article  Google Scholar 

  4. Dean J, Ghemawat S (2010) Mapreduce: a flexible data processing tool. Commun ACM 53(1):72–77

    Article  Google Scholar 

  5. Sakr S, Liu A, Batista DM, Alomari M (2011) A survey of large scale data management approaches in cloud environments. IEEE Commun Surv Tutor 13(3):311–336

    Article  Google Scholar 

  6. Chowdhury M, Zaharia M, Ma J, Jordan MI, Stoica I (2011) Managing data transfers in computer clusters with orchestra. ACM SIGCOMM Comput Commun Rev 41(4):98–109

    Article  Google Scholar 

  7. Zhang Z, Cherkasova L, Loo BT (2013) Performance modeling of mapreduce jobs in heterogeneous cloud environments. In: IEEE sixth international conference on cloud computing, pp 839–846

  8. Zaharia M, Borthakur D, Sarma JS, Elmeleegy K, Shenker S, Stoica I (2010) Delay scheduling:a simple technique for achieving locality and fairness in cluster scheduling. In: ACM EuroSys, pp 265–278

  9. Ananthanarayanan G, Agarwal S, Kandula S, Greenberg A, Stoica I, Harlan D, Harris E (2011) Scarlett: coping with skewed content popularity in mapreduce clusters. In: ACM EuroSys, pp 287–300

  10. Xie Q, Pundir M, Lu Y, Abad CL, Campbell RH (2017) Pandas: robust locality-aware scheduling with stochastic delay optimality. IEEE/ACM Trans Netw 25(2):662–675

    Article  Google Scholar 

  11. Klas G (2017) Edge computing and the role of cellular networks. Computer 50(10):40–49

    Article  Google Scholar 

  12. Li S, Maddah-Ali MA, Avestimehr AS (2015) Coded MapReduce. In: Allerton conference on communication, control, and computing, pp 964–971

  13. Li S, Maddah-Ali MA, Avestimehr AS (2016) Fundamental tradeoff between computation and communication in distributed computing. In: IEEE ISIT, pp 1814–1818

  14. Li S, Yu Q, Maddah-Ali MA, Avestimehr AS (2016) Coded distributed computing: Fundamental limits and practical challenges. In: Asilomar conference on signals, systems and computers, pp 509–513

  15. Wu L, Wang W, Zhang Z (2012) A POMDP-based optimal spectrum sensing and access scheme for cognitive radio networks with hardware limitation. In: IEEE WCNC, pp 1281–1286

  16. Lyu X, Ni W, Tian H, Liu RP, Wang X, Giannakis GB, Paulraj A (2017) Optimal schedule of mobile edge computing for internet of things using partial information. IEEE J Sel Areas Commun 35(11):2606–2615

    Article  Google Scholar 

  17. Wang F, Xu J, Wang X, Cui S (2017) Joint offloading and computing optimization in wireless powered mobile-edge computing systems. In: IEEE ICC, pp 1–6

  18. Wang R, Butnariu D, Rexford J (2011) Openflow-based server load balancing gone wild. In: Usenix Hot-ICE, vol 11, pp 12–12

  19. Zhao T, Zhou S, Guo X, Niu Z (2017) Tasks scheduling and resource allocation in heterogeneous cloud for delay-bounded mobile edge computing. In: IEEE ICC, pp 1–7

  20. Dinh TQ, Tang J, La QD, Quek TQ (2017) Offloading in mobile edge computing: Task allocation and computational frequency scaling. IEEE Trans Commun 65(8):3571–3584

    Google Scholar 

  21. Lin X, Zhang H, Ji H, Leung VCM (2017) Joint computation and communication resource allocation in mobile-edge cloud computing networks. In: IEEE international conference on network infrastructure and digital content

  22. Wu F, Niu J, Gao Y (2011) Bandwidth aware application partitioning for computation offloading on mobile devices. In: International conference on green communications and networking

  23. Palanisamy B, Singh A, Liu L, Jain B (2011) Purlieus: locality-aware resource allocation for mapreduce in a cloud. In: International conference for high performance computing, networking, storage and analysis, pp 1–11

  24. Wang W, Zhu K, Ying L, Tan J (2013) Map task scheduling in mapreduce with data locality: throughput and heavy-traffic optimality. In: INFOCOM, pp 1609–1617

  25. Li J, Wu J, Yang X, Zhong S (2015) Optimizing mapreduce based on locality of k-v pairs and overlap between shuffle and local reduce. In: International conference on parallel processing, pp 939–948

  26. Chen W, Paik I, Li Z (2016) Tology-aware optimal data placement algorithm for network traffic optimization. IEEE Trans Comput 65(8):2603–2617

    Article  MathSciNet  MATH  Google Scholar 

  27. Ying Y, Birke R, Wang C, Chen LY, Gautam N (2015) Optimizing energy, locality and priority in a mapreduce cluster. In: IEEE international conference on autonomic computing, pp 21–30

  28. Chen F, Kodialam M, Lakshman TV (2012) Joint scheduling of processing and shuffle phases in mapreduce systems. In: IEEE INFOCOM, pp 1143–1151

  29. Tan J, Meng X, Zhang L (2013) Coupling task progress for mapreduce resource-aware scheduling. In: IEEE INFOCOM, pp 1618–1626

  30. Karp RM (1992) On-line algorithms versus off-line algorithms: How much is it worth to know the future? IFIP Congress 12:416–429

    Google Scholar 

  31. Zafer MA, Modiano EA (2009) A calculus approach to energy-efficient data transmission with quality-of-service constraints. IEEE/ACM Trans Netw 17:898–911

    Article  Google Scholar 

  32. Wang Y, Wang W, Lau VKN, Chen L, Zhang Z (2018) Heterogeneous spectrum aggregation: coexistence from a queue stability perspective. IEEE Trans Wirel Commun 17(4):2471–2485

    Article  Google Scholar 

  33. Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press, Cambridge

    Book  MATH  Google Scholar 

  34. Borodin A, Ran EY (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  35. Borodin A, Ran EY, Gogan V (2000) On the competitive theory and practice of portfolio selection. In: Latin American symposium on theoretical informatics, pp 173–196

  36. Hadoop: Fair Scheduler. http://hadoop.apache.org/docs/r2.7.3/hadoop-yarn/hadoop-yarnsite/FairScheduler.html

  37. Hadoop: Capacity Scheduler. http://hadoop.apache.org/docs/r2.7.0/hadoop-yarn/hadoopyarn-site/CapacityScheduler.html

  38. Li S, Maddah-Ali MA, Yu Q (2018) A fundamental tradeoff between computation and communication in distributed computing. IEEE Trans Inf Theory 64(1):109–128

    Article  MathSciNet  MATH  Google Scholar 

  39. Kiamari M, Wang C, Avestimehr AS (2017) On heterogeneous coded distributed computing. In: IEEE GLOBECOM, pp 1–7

  40. Reisizadeh A, Prakash S, Pedarsani R, Avestimehr S (2017) Coded computation over heterogeneous clusters. In: IEEE ISIT, pp 2408–2412

  41. Gupta S, Lalitha V (2017) Locality-aware hybrid coded MapReduce for server-rack architecture. In: IEEE ITW, pp 459–463

Download references

Author information

Authors and Affiliations

  1. College of Information Science and Electronic Engineering, Zhejiang University, Hangzhou, 310027, China

    Minghui Zhao, Wei Wang, Yitu Wang & Zhaoyang Zhang

Authors
  1. Minghui Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yitu Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhaoyang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei Wang.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the Topical Collection: Special Issue on Big Data and Smart Computing in Network Systems

Guest Editors: Jiming Chen, Kaoru Ota, Lu Wang, and Jianping He

This work is supported in part by National Natural Science Foundation of China (Nos. 61571396, 61725104), Zhejiang Provincial Natural Science Foundation of China (No. LR17F010001), Young Elite Scientist Sponsorship Program by CAST (No. 2016 QNRC001), and Talent Project of ZJAST (No. 2017YCGC011)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhao, M., Wang, W., Wang, Y. et al. Load scheduling for distributed edge computing: A communication-computation tradeoff. Peer-to-Peer Netw. Appl. 12, 1418–1432 (2019). https://doi.org/10.1007/s12083-018-0695-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12083-018-0695-4

Keywords

Search

Navigation