Redes Auto-Reconfiguráveis Randomizadas para Comunicação Distribuída em Datacenters
Resumo
Neste artigo nós estudamos os benefícios de randomização no projeto de topologias de redes auto-reconfiguráveis, ou seja, redes que se adaptam dinamicamente à demanda que atendem em tempo real, de forma online. Apresentamos uma rede randomizada auto-reconfigurável com topologia em árvore, que utiliza randomização para reduzir o custo esperado de reconfiguração por um fator constante, comparado a soluções determinísticas existentes. A nova solução é simples, de fácil implementação, totalmente distribuída e concorrente. Nós provamos que o algoritmo proposto é correto, provamos limites de custo amortizado no pior caso e apresentamos resultados de simulação em sequências de requisições com localidade de referência espacial e temporal variáveis.
Referências
(2016). Projector dataset. [link].
Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., and Tarjan, R. E. (2012). Cbtree: A practical concurrent self-adjusting search tree. In Proceedings of the 26th International Conference on Distributed Computing, DISC’12, pages 1–15, Berlin, Heidelberg. Springer-Verlag.
Al-Fares, M., Loukissas, A., and Vahdat, A. (2008). A scalable, commodity data center network architecture. In ACM SIGCOMM Computer Communication Review, volume 38, pages 63–74. ACM.
Albers, S. and Karpinski, M. (2002). Randomized splay trees: Theoretical and experimental results. Inf. Process. Lett., 81(4):213–221.
Avin, C., Ghobadi, M., Griner, C., and Schmid, S. (2020). On the complexity of traffic traces and implications. In Proc. ACM SIGMETRICS.
Avin, C. and Schmid, S. (2018). Toward demand-aware networking: A theory for selfadjusting networks. In ACM SIGCOMM Computer Communication Review (CCR).
Ballani, H., Costa, P., Behrendt, R., Cletheroe, D., Haller, I., Jozwik, K., Karinou, F., Lange, S., Shi, K., Thomsen, B., et al. (2020). Sirius: A flat datacenter network with nanosecond optical switching. In Proc. ACM SIGCOMM, pages 782–797.
Chen, K., Singla, A., Singh, A., Ramachandran, K., Xu, L., Zhang, Y., Wen, X., and Chen, Y. (2014). Osa: An optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Transactions on Networking (TON), 22(2):498– 511.
Chen, L., Chen, K., Zhu, Z., Yu, M., Porter, G., Qiao, C., and Zhong, S. (2017). Enabling wide-spread communications on optical fabric with megaswitch. NSDI’17, page 577–593.
Farrington, N., Porter, G., Radhakrishnan, S., Bazzaz, H. H., Subramanya, V., Fainman, Y., Papen, G., and Vahdat, A. (2010). Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 40(4):339–350.
Ghobadi, M., Mahajan, R., Phanishayee, A., Devanur, N., Kulkarni, J., Ranade, G., Blanche, P.-A., Rastegarfar, H., Glick, M., and Kilper, D. (2016). Projector: Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM, SIGCOMM ’16, pages 216–229, New York, NY, USA. ACM.
Group, D. C. (2007). Sinalgo simulator for network algorithms. https://sinalgo.github.io. Accessed 22-April-2022.
Guo, C., Lu, G., Li, D., Wu, H., Zhang, X., Shi, Y., Tian, C., Zhang, Y., and Lu, S. (2009). Bcube: a high performance, server-centric network architecture for modular data centers. Proc. ACM SIGCOMM Computer Communication Review (CCR), 39(4):63–74.
Kassing, S., Valadarsky, A., Shahaf, G., Schapira, M., and Singla, A. (2017). Beyond fat-trees without antennae, mirrors, and disco-balls. In Proc. ACM SIGCOMM, pages 281–294.
Peres, B., Souza, O., Goussevskaia, O., Schmid, S., and Avin, C. (2019). Distributed self-adjusting tree networks. In Proc. IEEE INFOCOM.
Peres, B., Souza, O. A. d. O., Goussevskaya, O., Avin, C., and Schmid, S. (2021). Distributed self-adjusting tree networks. IEEE Transactions on Cloud Computing.
Schmid, S., Avin, C., Scheideler, C., Borokhovich, M., Haeupler, B., and Lotker, Z. (2016). Splaynet: Towards locally self-adjusting networks. IEEE/ACM Trans. Netw., 24(3):1421–1433.
Sleator, D. and Tarjan, R. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Souza, O. A. d. O., Goussevskaia, O., and Schmid, S. (2021). Cbnet: Minimizing adjustments in concurrent demand-aware tree networks. In IEEE Int. Parallel and Distributed Processing Sym. (IPDPS), pages 382–391.
Zerwas, J., Kellerer, W., and Blenk, A. (2021). What you need to know about optical circuit reconfigurations in datacenter networks. In The 33nd International Teletraffic Congress (ITC 33).
Afek, Y., Kaplan, H., Korenfeld, B., Morrison, A., and Tarjan, R. E. (2012). Cbtree: A practical concurrent self-adjusting search tree. In Proceedings of the 26th International Conference on Distributed Computing, DISC’12, pages 1–15, Berlin, Heidelberg. Springer-Verlag.
Al-Fares, M., Loukissas, A., and Vahdat, A. (2008). A scalable, commodity data center network architecture. In ACM SIGCOMM Computer Communication Review, volume 38, pages 63–74. ACM.
Albers, S. and Karpinski, M. (2002). Randomized splay trees: Theoretical and experimental results. Inf. Process. Lett., 81(4):213–221.
Avin, C., Ghobadi, M., Griner, C., and Schmid, S. (2020). On the complexity of traffic traces and implications. In Proc. ACM SIGMETRICS.
Avin, C. and Schmid, S. (2018). Toward demand-aware networking: A theory for selfadjusting networks. In ACM SIGCOMM Computer Communication Review (CCR).
Ballani, H., Costa, P., Behrendt, R., Cletheroe, D., Haller, I., Jozwik, K., Karinou, F., Lange, S., Shi, K., Thomsen, B., et al. (2020). Sirius: A flat datacenter network with nanosecond optical switching. In Proc. ACM SIGCOMM, pages 782–797.
Chen, K., Singla, A., Singh, A., Ramachandran, K., Xu, L., Zhang, Y., Wen, X., and Chen, Y. (2014). Osa: An optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Transactions on Networking (TON), 22(2):498– 511.
Chen, L., Chen, K., Zhu, Z., Yu, M., Porter, G., Qiao, C., and Zhong, S. (2017). Enabling wide-spread communications on optical fabric with megaswitch. NSDI’17, page 577–593.
Farrington, N., Porter, G., Radhakrishnan, S., Bazzaz, H. H., Subramanya, V., Fainman, Y., Papen, G., and Vahdat, A. (2010). Helios: a hybrid electrical/optical switch architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 40(4):339–350.
Ghobadi, M., Mahajan, R., Phanishayee, A., Devanur, N., Kulkarni, J., Ranade, G., Blanche, P.-A., Rastegarfar, H., Glick, M., and Kilper, D. (2016). Projector: Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM, SIGCOMM ’16, pages 216–229, New York, NY, USA. ACM.
Group, D. C. (2007). Sinalgo simulator for network algorithms. https://sinalgo.github.io. Accessed 22-April-2022.
Guo, C., Lu, G., Li, D., Wu, H., Zhang, X., Shi, Y., Tian, C., Zhang, Y., and Lu, S. (2009). Bcube: a high performance, server-centric network architecture for modular data centers. Proc. ACM SIGCOMM Computer Communication Review (CCR), 39(4):63–74.
Kassing, S., Valadarsky, A., Shahaf, G., Schapira, M., and Singla, A. (2017). Beyond fat-trees without antennae, mirrors, and disco-balls. In Proc. ACM SIGCOMM, pages 281–294.
Peres, B., Souza, O., Goussevskaia, O., Schmid, S., and Avin, C. (2019). Distributed self-adjusting tree networks. In Proc. IEEE INFOCOM.
Peres, B., Souza, O. A. d. O., Goussevskaya, O., Avin, C., and Schmid, S. (2021). Distributed self-adjusting tree networks. IEEE Transactions on Cloud Computing.
Schmid, S., Avin, C., Scheideler, C., Borokhovich, M., Haeupler, B., and Lotker, Z. (2016). Splaynet: Towards locally self-adjusting networks. IEEE/ACM Trans. Netw., 24(3):1421–1433.
Sleator, D. and Tarjan, R. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Souza, O. A. d. O., Goussevskaia, O., and Schmid, S. (2021). Cbnet: Minimizing adjustments in concurrent demand-aware tree networks. In IEEE Int. Parallel and Distributed Processing Sym. (IPDPS), pages 382–391.
Zerwas, J., Kellerer, W., and Blenk, A. (2021). What you need to know about optical circuit reconfigurations in datacenter networks. In The 33nd International Teletraffic Congress (ITC 33).
Publicado
23/05/2022
Como Citar
SOUZA, Otávio A. O.; CALDEIRA, Caio; GOUSSEVSKAIA, Olga.
Redes Auto-Reconfiguráveis Randomizadas para Comunicação Distribuída em Datacenters. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 40. , 2022, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 377-390.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2022.222336.
