Performance of Balanced Fairness in Resource Pools: A Recursive Approach

Abstract

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be processed by any server of the cluster due to various constraints like data locality. In this paper, we represent these constraints by some assignment graph between jobs and servers. We present a recursive approach to computing performance metrics like mean response times when the server capacities are shared according to balanced fairness. While the computational cost of these formulas can be exponential in the number of servers in the worst case, we illustrate their practical interest by introducing broad classes of pool structures that can be exactly analyzed in polynomial time. This extends considerably the class of models for which explicit performance metrics are accessible.

References

1. D. P. Anderson. 2004. BOINC: A System for Public-Resource Computing and Storage Proc. of the 5th IEEE/ACM Int. Workshop on Grid Comput. (GRID '04). IEEE Comput. Soc., Washington, DC, USA, 4--10.
2. S. A. Berezner and A. E. Krzesinski. 1996. Order independent loss queues. Queueing Syst. Vol. 23, 1--4 (March 1996), 331--335.
3. T. Bonald and C. Comte. 2017. Balanced fair resource sharing in computer clusters. Perf. Evaluation Vol. 116 (Nov. 2017), 70--83.
4. T. Bonald, C. Comte, and F. Mathieu. 2017 a. Performance of Balanced Fairness in Resource Pools: A Recursive Approach. Proc. ACM Meas. Anal. Comput. Syst. Vol. 1, 2 (Dec. 2017), 41:1--41:25.
5. T. Bonald, C. Comte, V. Shah, and G. de Veciana. 2017 b. Poly-symmetry in processor-sharing systems. Queueing Syst. Vol. 86, 3--4 (Aug. 2017), 327--359.
6. T. Bonald, L. Massoulié, A. Proutière, and J. Virtamo. 2006. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Syst. Vol. 53, 1--2 (June 2006), 65--84.
7. T. Bonald and A. Proutière. 2003. Insensitive Bandwidth Sharing in Data Networks. Queueing Syst. Vol. 44, 1 (May 2003), 69--100.
8. T. Bonald and J. Virtamo. 2004. Calculating the flow level performance of balanced fairness in tree networks. Perf. Evaluation Vol. 58, 1 (Oct. 2004), 1--14.
9. K. Gardner, M. Harchol-Balter, E. Hyyti"a, and R. Righter. 2017a. Scheduling for efficiency and fairness in systems with redundancy. Perf. Evaluation Vol. 116 (Nov. 2017), 1--25.
10. K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, M. Velednitsky, and S. Zbarsky. 2017b. Redundancy- d : The Power of d Choices for Redundancy. Operations Research Vol. 65, 4 (April 2017), 1078--1094.
11. K. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, E. Hyytia, and A. Scheller-Wolf. 2016. Queueing with redundant requests: exact analysis. Queueing Syst. Vol. 83, 3--4 (Aug. 2016), 227--259.
12. P. G. Harrison. 1985. On Normalizing Constants in Queueing Networks. Operations Research Vol. 33, 2 (1985), 464--468.
13. A. E. Krzesinski. 2011. Order Independent Queues. In Queueing Networks, bibfieldeditorR. J. Boucherie and N. M. van Dijk (Eds.). Number 154 in Int. Series in Operations Research & Management Science. Springer US, 85--120.
14. K. Lee, Y. Lee, H. Choi, Y. D. Chung, and B. Moon. 2012. Parallel Data Processing with MapReduce: A Survey. SIGMOD Rec. Vol. 40, 4 (Jan. 2012), 11--20.
15. L. Massoulié. 2007. Structural Properties of Proportional Fairness: Stability and Insensitivity. The Annals of Appl. Probability Vol. 17, 3 (2007), 809--839.
16. V. Shah and G. de Veciana. 2015. High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics. Trans. on Netw. Vol. 23, 5 (2015), 1674--1687.
17. V. Shah and G. de Veciana. 2016. Asymptotic Independence of Servers' Activity in Queueing Systems with Limited Resource Pooling. Queueing Syst. Vol. 83, 1--2 (June 2016), 13--28.
18. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. 2001. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. SIGCOMM Comput. Commun. Rev. Vol. 31, 4 (2001), 149--160.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

      • Cloud computing

• Mathematics of computing

  • Probability and statistics

    • Stochastic processes

      • Markov processes