O Passado Também Importa: Um Mecanismo de Alocação Justa de Múltiplos Tipos de Recursos ao Longo do Tempo
Abstract
Shared computing systems are composed by different resource types, such as CPU and memory, and hold users with different resource constraints. While some users execute short workloads in which fast allocation is essential, others execute long workloads that require more resources. Among the different proposals to allocate resources in this scenario, Dominant Resource Fairness (DRF) is notable for satisfying some desirable properties, such as truthfulness and Pareto efficiency. However, these proposals focus only on instantaneous fairness, ignoring users heterogeneity. This paper proposes DRF with state (SDRF). SDRF satisfies the fundamental properties of DRF, besides enforcing a new notion of fairness that look at past resource allocations. We verify SDRF with both theoretical analysis and simulations using Google cluster traces. Results show that SDRF reduces users' average waiting time and improves fairness by increasing the number of completed tasks for users with lower demand with low impact on high-demand users.
References
Chen, C., Wang, W., Zhang, S. e Li, B. (2017). Cluster fair queueing: Speeding up data-parallel jobs with delay guarantees. Em Proc. IEEE INFOCOM.
Dolev, D., Feitelson, D. G., Halpern, J. Y., Kupferman, R. e Linial, N. (2012). No justied complaints. Em Proc. Conference on Innovations in Theoretical Computer Science.
Ghodsi, A., Sekar, V., Zaharia, M. e Stoica, I. (2012). Multi-resource fair queueing for packet processing. Em Proc. ACM SIGCOMM.
Ghodsi, A., Zaharia, M., Hindman, B., Konwinski, A., Shenker, S. e Stoica, I. (2011). Dominant resource fairness: Fair allocation of multiple resource types. Em Proc. USENIX NSDI.
Grandl, R., Chowdhury, M., Akella, A. e Ananthanarayanan, G. (2016). Altruistic scheduling in multi-resource clusters. Em Proc. USENIX OSDI.
Guibas, L. J. e Sedgewick, R. (1978). A dichromatic framework for balanced trees. Em Proc. IEEE Symposium on Foundations of Computer Science.
Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., Joseph, A. D., Katz, R., Shenker, S. e Stoica, I. (2011). Mesos: A platform for ne-grained resource sharing in the data center. Em Proc. USENIX NSDI.
Jaffe, J. (1981). Bottleneck ow control. IEEE Trans. on Communic., 29(7):954–962.
Joe-Wong, C., Sen, S., Lan, T. e Chiang, M. (2013). Multiresource allocation: Fairnesefciency tradeoffs in a unifying framework. IEEE/ACM ToN, 21(6):1785–1798.
Kash, I., Procaccia, A. D. e Shah, N. (2014). No agent left behind: Dynamic fair division of multiple resources. Journal of Articial Intelligence Research, 51(1):579–603.
Oppenheim, A. V., Schafer, R. W. e Buck, J. R. (1999). Discrete-Time Signal Processing. Prentice-Hall, 2 edição.
Parkes, D. C., Procaccia, A. D. e Shah, N. (2015). Beyond dominant resource fairness. ACM Transactions on Economics and Computation, 3(1):3:1–3:22.
Radunovic, B. e Le Boudec, J.-Y. (2007). A unied framework for max-min and min-max fairness with applications. IEEE/ACM ToN, 15(5):1073–1083.
Reiss, C., Tumanov, A., Ganger, G. R., Katz, R. H. e Kozuch, M. A. (2012). Heterogeneity and dynamicity of clouds at scale: Google trace analysis. Em Proc. ACM SoCC.
Sadok, H., Campista, M. E. M. e Costa, L. H. M. K. (2017). O passado também importa: Um mecanismo de alocação justa de múltiplos tipos de recursos ao longo do tempo. Relatório Técnico GTA-17-30, GTA/PEE/UFRJ. https://www.gta.ufrj.br/ ftp/gta/TechReports/SCC17a.pdf.
Wang, W., Li, B. e Liang, B. (2014a). Dominant resource fairness in cloud computing systems with heterogeneous servers. Em Proc. IEEE INFOCOM.
Wang, W., Liang, B. e Li, B. (2014b). Low complexity multi-resource fair queueing with bounded delay. Em Proc. IEEE INFOCOM.
