[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

UFalloc: Towards Utility Max-min Fairness of Bandwidth Allocation for Applications in Datacenter Networks

  • Published:
Mobile Networks and Applications Aims and scope Submit manuscript

Abstract

Providing fair bandwidth allocation for applications is becoming increasingly compelling in cloud datacenters, as different applications compete for the shared datacenter network resources. While existing solutions mainly provide bandwidth guarantees for virtual machines (VMs) or tenants with the aim of achieving the VM-level or tenant-level fairness of bandwidth allocation, scant attention has been paid to providing bandwidth guarantees for applications to achieve the fairness of application performance (utility). In this paper, we introduce a rigorous definition of application-level utility max-min fairness, which guides us to develop a non-linear model to investigate the relationship between the utility fairness and bandwidth allocation for applications. Based on such a model, we further arbitrate the intrinsic tradeoff between the network bandwidth utilization and utility fairness of application bandwidth allocation, using a tunable fairness relaxation factor. To improve the bandwidth utilization while maintaining the strict utility fairness of bandwidth allocation, we design UFalloc, an application-level Utility max-min Fair bandwidth allocation strategy in datacenter networks. With extensive experiments using OpenFlow in Mininet virtual network environment, we demonstrate that UFalloc can achieve high utilization of network bandwidth while maintaining the utility max-min fair share of bandwidth allocation with a certain degree of fairness relaxation, yet with an acceptable computational overhead.

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
£29.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 includes VAT (United Kingdom)

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
Fig. 9

Similar content being viewed by others

Notes

  1. https://hadoop.apache.org

  2. http://www.netperf.org/netperf/

  3. https://iperf.fr

  4. http://mininet.org

  5. http://osrg.github.io/ryu/

  6. https://www.opendaylight.org

  7. http://cpqd.github.io/ofsoftswitch13/

References

  1. Roy A, Zeng H, Bagga J, Porter G, Snoeren AC (2015) Inside the social network’s (datacenter) network. In: Proceedings of SIGCOMM, pp 123–137

  2. Yi X, Liu F, Liu J, Jin H (2014) Building a network highway for big data: architecture and challenges. IEEE Network Magazine 28(4):5–13

    Article  Google Scholar 

  3. Dean J, Ghemawat S (2008) Mapreduce: simplified data processing on large clusters. Commun ACM 51(1):107–113

    Article  Google Scholar 

  4. Wang H, Chen L, Chen K, Li Z, Zhang Y, Guan H, Qi Z, Li D, Geng Y (2015) Flowprophet: generic and accurate traffic prediction for data-parallel cluster computing. In: Prof. of ICDCS, pp 349–358

  5. Xu F, Liu F, Jin H, Vasilakos AV (2014) Managing performance overhead of virtual machines in cloud computing: a survey, state of art and future directions. Proc IEEE 102(1):11–31

    Article  Google Scholar 

  6. Bertsekas DP, Gallager RG (1992) Data network, 2nd edn. Prentice-Hall, London

    MATH  Google Scholar 

  7. Kelly FP, Maulloo AK, Tan DKH (1998) Rate control for communication networks: shadow price, proportional fairness and stability. J Oper Res Soc 49(3):237–252

    Article  MATH  Google Scholar 

  8. Guo J, Liu F, Tang H, Lian Y, Jin H, Lui J (2013) Falloc: fair network bandwidth allocation in IaaS datacenters via a bargaining game approach. In: Proceedings of ICNP, pp 1–10

  9. Yu L, Cai Z (2016) Dynamic scaling of virtual clusters with bandwidth guarantee in cloud data centers. In: Proceedings of infocom

  10. Popa L, Kumar G, Chowdhury M, Krishnamurthy A, Ratnasamy S, Stoica I (2012) Faircloud: Sharing the Network in Cloud Computing. In: Proceedings of SIGCOMM, pp 187–198

  11. Lam T, Radhakrishnan S, Vahdat A, Varghese G (2010) Netshare: virtualizing data center networks across services. Technical Report CS2010-0957, Department of Computer Science and Engineering, University of California, San Diego

  12. Xie D, Ding N, Hu YC, Kompella R (2012) The only constant is change: incorporating time-varying network reservations in data centers. ACM SIGCOMM Computer Communication Review 42(4):199–210

    Article  Google Scholar 

  13. Wang XH, Han DF, Sun FY (1990) Point estimates on deformation newton’s iterations. Mathematica Numerica Sinica 1(2):145–156

    MathSciNet  MATH  Google Scholar 

  14. Ye W, Xu F, Zhang W (2015) Achieving application-level utility max-min fairness of bandwidth allocation in datacenter networks. In: Proceedings of collaboratecom

  15. Jalaparti V, Bodik P, Menache I, Rao S, Makarychev K, Caesar M (2015) Network-aware scheduling for data-parallel jobs: plan when you can. In: Proceedings of SIGCOMM, pp 407–420

  16. Shenker S (1995) Fundamental design issues for the future internet. IEEE J Sel Areas Commun 13(7):1176–1187

    Article  Google Scholar 

  17. Cao Z, Zegura E (1999) Utility max-min: an application-oriented allocation scheme. In: Proceedings of infocom, pp 793–801

  18. Al-Fares M, Loukissas A, Vahdat A (2008) A scalable, commodity data center network architecture. ACM SIGCOMM Computer Communication Review 38(4):63–74

    Article  Google Scholar 

  19. Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans Networking 8(5):556–567

    Article  Google Scholar 

  20. Kuhn HW (2014) Nonlinear programming: a historical view. Traces and Emergence of Nonlinear Programming:393– 414

  21. Slater M (2014) Lagrange multipliers revisited. Springer, Basel

    Book  Google Scholar 

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

  23. Boţ R, Kassay G, Wanka G (2005) Strong duality for generalized convex optimization problems. J Optim Theory Appl 127(1):45–70

    Article  MathSciNet  MATH  Google Scholar 

  24. Li D (1995) Zero duality gap for a class of nonconvex optimization problems. J Optim Theory Appl 85 (2):309–324

    Article  MathSciNet  MATH  Google Scholar 

  25. Rosen JB (1960) The gradient projection method for nonlinear programming. Part i. Linear constraints. J Soc Ind Appl Math 8(1):181–217

    Article  MATH  Google Scholar 

  26. Yaïche H, Mazumdar RR, Rosenberg C (2000) A game theoretic framework for bandwidth allocation and pricing in broadband networks. IEEE/ACM Trans Networking 8(5):667–678

    Article  Google Scholar 

  27. Sohrab HH (2003) Basic real analysis. Switzerland, Birkhauser

    Book  MATH  Google Scholar 

  28. Open Networking Foundation: OpenFlow Switch Specification Version 1.3.0 (Wire Protocol 0x04). https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.3.0.pdf (2012) [Online; released June 25, 2012]

  29. Kelly F (2003) Fairness and stability of end-to-end congestion control*. Eur J Control 9(2):159–176

    Article  MATH  Google Scholar 

  30. Wang W, Palaniswami M, Low S (2006) Application-Oriented Flow control fundamentals algorithms and fairness. IEEE/ACM Trans Networking 14(6):1282–1291

    Article  Google Scholar 

  31. Jin J, Wang W, Palaniswami M (2007) Utility Max-Min fair flow control for multipath communication networks. In: Proceedings of ICSPCS, pp 61–66

  32. Xu F, Liu F, Liu L, Jin H, Li B, Li B (2014) iAware: making live migration of virtual machines interference-aware in the cloud. IEEE Trans Comput 63(12):3012–3025

    Article  MathSciNet  Google Scholar 

  33. Xu F, Liu F, Jin H (2015) Heterogeneity and interference-aware virtual machine provisioning for predictable performance in the cloud. IEEE Trans Comput

  34. Ballani H, Costa P, Karagiannis T, Rowstron A (2011) Towards predictable datacenter networks. ACM SIGCOMM Computer Communication Review 41(4):242–253

    Article  Google Scholar 

  35. Hu S, Bai W, Chen K, Tian C, Zhang Y, Wu H (2016) Providing bandwidth guarantees, work conservation and low latency simultaneously in the cloud. In: Proceedings of infocom

  36. Shieh A, Kandula S, Greenberg A, Kim C, Saha B (2011) Sharing the data center network. In: Proceedings of NSDI, pp 309–322

  37. Guo J, Liu F, Huang X, Lui J, Hu M, Gao Q, Jin H (2014) On efficient bandwidth allocation for traffic variability in datacenters. In: Proceedings of infocom, pp 1572–1580

  38. Li D, Chen C, Guan J, Zhang Y, Zhu J, Yu R (2015) Dcloud: deadline-aware resource allocation for cloud computing jobs. IEEE Trans Parallel Distrib Syst

  39. Li D, Liao X, Jin H, Zhou B, Zhang Q (2013) A new disk I/O model of virtualized cloud environment. IEEE Trans Parallel Distrib Syst 24(6):1129–1138

    Article  Google Scholar 

  40. Kumar G, Chowdhury M, Ratnasamy S, Stoica I (2012) A case for performance-centric network allocation. In: Proceedings of hotcloud, pp 9–9

  41. Lee J, Turner Y, Lee M, Popa L, Banerjee S, Kang JM, Sharma P (2014) Application-driven bandwidth guarantees in datacenters. In: Proceedings of SIGCOMM, pp 467–478

  42. Chen L, Feng Y, Li B, Li B (2014) Towards performance-centric fairness in datacenter networks. In: Proceedings of infocom, pp 1599–1607

Download references

Author information

Authors and Affiliations

  1. Shanghai Key Laboratory of Multidimensional Information Processing, Department of Computer Science and Technology, East China Normal University, Shanghai, 200241, China

    Fei Xu, Wangying Ye, Yuhan Liu & Wei Zhang

Authors
  1. Fei Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wangying Ye
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuhan Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wei Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fei Xu.

Additional information

The research was supported by a grant from the National Natural Science Foundation of China (NSFC) under grant No.61502172, by a grant from the Postdoctoral Science Foundation of China under grant No.2015M580307, by a grant from Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, China, and by a grant from the Science and Technology Commission of Shanghai Municipality under grant No.14DZ2260800.

Appendix A

Appendix A

In the appendix, we will prove that d(μ) is differentiable and K-Lipschitz continuous. Accordingly to Eqs. 14 and 19, we can derive

$$\begin{array}{@{}rcl@{}} d(\mu) &=& -{\sum}_{i}\log_{{\sum}_{f}r_{i,f}} {\sum}_{f}\alpha_{i,f}^{*} \\ &&+ \sum\limits_{l \in \mathcal{K}}\mu_{l} \cdot \left( {\sum}_{i}{\sum}_{f} \alpha_{i,f}^{*} \cdot h_{i,f}^{l} - C_{l}\right), \end{array} $$

where α ∗ is a constant optimal solution value. Then, we can derive the derivative of d(μ) by substituting Eq. 18 into the equation as follows,

$$\begin{array}{@{}rcl@{}} \frac{\partial d(\mu)}{\partial \mu_{l}} & =& {\sum}_{i}{\sum}_{f}\alpha_{i,f}^{*} \cdot h_{i,f}^{l} - C_{l}\\ & =&\! {\sum}_{i}{\sum}_{f}g_{i,f}\!\left( \sum\limits_{l \in \mathcal{L}}(\mu_{l} \cdot h_{i,f}^{l}) \!\cdot\! \ln\left( \sum\limits_{p \in \mathcal{F}_{p}}r_{i,p}\!\right)\!\!\right) \!\cdot\! h_{i,f}^{l} \,-\, C_{l}. \end{array} $$

Based on the equation above, we can prove that d(μ) is differentiable. Then, we begin to prove d(μ) is K-Lipschitz continuous. In the rest of this section, \(\frac {\partial d(\mu )}{\partial \mu _{l}}\) will be denoted as \(d^{\prime }_{l}(\mu )\). Our proof is given as below,

$$\begin{array}{@{}rcl@{}} &&\left|{d^{\prime}_{l}(\mu) - d^{\prime}_{l}(\mu^{\prime})} \right| \\ &=& | {\sum}_{i}{\sum}_{f} g_{i,f}\left( \sum\limits_{l \in \mathcal{L}}(\mu_{l} \cdot h_{i,f}^{l}) \cdot \ln(\sum\limits_{p \in F_{i}} {r_{i,p}})\right) \cdot h_{i,f}^{l} - C_{l} \\ && - {\sum}_{i}{\sum}_{f} g_{i,f}\left( \sum\limits_{l \in \mathcal{L}}(\mu^{\prime}_{l} \cdot h_{i,f}^{l}) \cdot \ln(\sum\limits_{p \in \mathcal{F}_{i}}r_{i,p})\right) \cdot h_{i,f}^{l} + C_{l} | \\ &=& | {\sum}_{i} {\sum}_{f} \left( g_{i,f}\left( \sum\limits_{l \in \mathcal{L}} (\mu_{l} \cdot h_{i,f}^{l}) \ln(\sum\limits_{p \in \mathcal{F}_{i}}{r_{i,p}})\right) \right.\\ && - g_{i,f}\left( \sum\limits_{l \in \mathcal{L}} (\mu^{\prime}_{l} \cdot h_{i,f}^{l}) \ln(\sum\limits_{p \in \mathcal{F}_{i}} r_{i,p})\right) \cdot h_{i,f}^{l} |\\ &\le& {\sum}_{i} {\sum}_{f} | g_{i,f}\left( \sum\limits_{l \in \mathcal{L}} (\mu_{l} \cdot h_{i,f}^{l}) \cdot \ln (\sum\limits_{p \in \mathcal{F}_{i}} r_{i,p})\right) \\ && - g_{i,f}\left( \sum\limits_{l \in \mathcal{L}} (\mu^{\prime}_{l} \cdot h_{i,f}^{l}) \cdot \ln(\sum\limits_{p \in \mathcal{F}_{i}} r_{i,p}) | \cdot h_{i,f}^{l}.\right. \end{array} $$

Due to the function features of g i, f (x) in Eq. 18, we have

$$\begin{array}{@{}rcl@{}} \left| g_{i,f}(x) - g_{i,f}(x^{\prime}) \right| &\le& \left| r_{i,f} - (\alpha_{i,f}^{0})^{1 - \varepsilon} \right| \\ &\le& (r_{i,f} - (\alpha_{i,f}^{0})^{1 - \varepsilon})^{2} \left| x - x^{\prime} \right| \end{array} $$

and accordingly,

$$\begin{array}{@{}rcl@{}} \left| d^{\prime}_{l}(\mu) - d^{\prime}_{l}(\mu^{\prime}) \right| \le \sum\limits_{i \in \mathcal{N}}\sum\limits_{f \in \mathcal{F}_{i}} (r_{i,f} - (\alpha_{i,f}^{0})^{1 - \varepsilon})^{2} \cdot h_{i,f}^{l} \cdot \left| {\mu_{l} - \mu^{\prime}_{l}} \right| \\ \le \sum\limits_{l \in \mathcal{L}} \sum\limits_{i \in \mathcal{N}} \sum\limits_{f \in \mathcal{F}_{i}} (r_{i,f} - (\alpha_{i,f}^{0})^{1 - \varepsilon})^{2} \cdot h_{i,f}^{l} \cdot \left| {\mu_{l} - \mu^{\prime}_{l}} \right| \\ \le \sqrt n \sum\limits_{l \in \mathcal{L}} \sum\limits_{i \in \mathcal{N}} \sum\limits_{f \in \mathcal{F}_{i}} (r_{i,f} - (\alpha_{i,f}^{0})^{1 - \varepsilon})^{2} \cdot h_{i,f}^{l} \cdot \left\| {\mu - \mu^{\prime}} \right\|_{1}. \end{array} $$

As a result, d(μ) is K-Lipschitz continuous and \(K = \sqrt n \cdot \sum \limits _{l \in \mathcal {L}}\sum \limits _{i \in \mathcal {N}} \sum \limits _{f \in \mathcal {F}_{i}} \left ((r_{i,f} - (\alpha _{i,f}^{0})^{1 - \varepsilon })^{2} \cdot h_{i,f}^{l}\right )\).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xu, F., Ye, W., Liu, Y. et al. UFalloc: Towards Utility Max-min Fairness of Bandwidth Allocation for Applications in Datacenter Networks. Mobile Netw Appl 22, 161–173 (2017). https://doi.org/10.1007/s11036-016-0739-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11036-016-0739-z

Keywords

Search

Navigation