O Passado Também Importa: Um Mecanismo de Alocação Justa de Múltiplos Tipos de Recursos ao Longo do Tempo
Resumo
Sistemas compartilhados de computação são compostos por vários tipos de recursos, como CPU e memória, e utilizados por usuários com requisitos distintos. Enquanto alguns usuários executam tarefas pequenas, em que a alocação rápida é fundamental, outros executam tarefas longas que requerem mais recursos. Dentre as diferentes propostas para alocar recursos nesse cenário, a justiça de recurso dominante (DRF) se destaca por possuir propriedades fundamentais, como verdade e eficiência de Pareto. Contudo, essas propostas focam apenas em justiça instantânea, ignorando a heterogeneidade de usuários. Este trabalho propõe o DRF com estado (SDRF), que mantém as propriedades fundamentais do DRF, além de garantir um novo conceito de justiça que considera a alocação de recursos passada. O SDRF é verificado por análises teóricas e simulações usando traços de um mês do cluster do Google. Os resultados mostram que o SDRF reduz a espera média dos usuários e melhora a justiça, ao aumentar o número de tarefas completas para usuários com demanda menor, tendo impacto pequeno nos de demanda maior.
Referências
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.
