FlatNet: Uma Rede Auto-Reconfigurável Distribuída e Concorrente com Topologia em Árvore Binária
Resumo
Neste trabalho apresentamos FlatNet, um novo protocolo de reestruturação de topologias de árvore binária. FlatNet incrementalmente adapta a topologia da rede de forma descentralizada e concorrente em resposta à demanda da aplicação que serve, aproximando os nós que se comunicam com maior frequência atráves de reestruturações locais de rede. Diferentemente de soluções existentes, que são baseadas em propriedades de pesquisa binária ou não permitem que operações ocorram concorrentemente na rede, limitando o desempenho, FlatNet é uma solução totalmente distribuída e concorrente que não necessita manter propriedades de árvore binária de busca. Nós provamos que FlatNet é correto, provemos limites de custo no pior caso e apresentamos resultados de simulações em sequências de requisições coletadas de centros de processamento de dados reais.
Palavras-chave:
Redes reconfiguráveis, Decentralização, Concorrência, Algoritmos online
Referências
Cao, Z., Kodialam, M., and Lakshman, T. (2016). Joint static and dynamic traffic scheduling in data center networks. Biological Cybernetics, 24(3):1908–1918.
Chowdhury, N. M. K. and Boutaba, R. (2010). A survey of network virtualization. Computer Networks, 54(5):862 – 876.
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. http://disco.ethz.ch/projects/sinalgo/index.html. Accessed 10-May-2017.
Hamedazimi, N., Qazi, Z., Gupta, H., Sekar, V., Das, S. R., Longtin, J. P., Shah, H., and Tanwer, A. (2014). Firefly: A reconfigurable wireless data center fabric using free-space optics. In ACM SIGCOMM Computer Communication Review, volume 44, pages 319–330. ACM.
Hu, Z., Qiao, Y., and Luo, J. (2015). Coarse-grained traffic matrix estimation for data center networks. Computer Communications, 56:25–34.
Kandula, S., Sengupta, S., Greenberg, A., Patel, P., and Chaiken, R. (2009). The nature of data center traffic: measurements & analysis. In Proc. 9th ACM Internet Measurement Conference (IMC), pages 202–208.
Kreutz, D., Ramos, F. M., Verissimo, P. E., Rothenberg, C. E., Azodolmolky, S., and Uhlig, S. (2015). Software-defined networking: A comprehensive survey. Proceedings of the IEEE, 103(1):14–76.
Liu, H., Lu, F., Forencich, A., Kapoor, R., Tewari, M., Voelker, G. M., Papen, G., Snoeren, A. C., and Porter, G. (2014). Circuit switching under the radar with reactor. In NSDI, volume 14, pages 1–15.
Peres, B., Souza, O., Goussevskaia, O., Schmid, S., and Avin, C. (2019). Distributed self-adjusting tree networks. In Proc. IEEE INFOCOM.
Reiter, M. K., Samar, A., and Wang, C. (2008). Self-optimizing distributed trees. In Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, pages 1–12.
Roy, A., Zeng, H., Bagga, J., Porter, G., and Snoeren, A. C. (2015). Inside the social network’s (datacenter) network. In ACM SIGCOMM Computer Communication Review, pages 123–137. ACM.
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.
Singla, A., Singh, A., Ramachandran, K., Xu, L., and Zhang, Y. (2010). Proteus: a topology malleable data center network. In Proc. ACM Workshop on Hot Topics in Networks (HotNets).
Sleator, D. and Tarjan, R. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Zhou, X., Zhang, Z., Zhu, Y., Li, Y., Kumar, S., Vahdat, A., Zhao, B. Y., and Zheng, H. (2012). Mirror mirror on the ceiling: Flexible wireless links for data centers. ACM SIGCOMM Computer Communication Review, 42(4):443–454.
Chowdhury, N. M. K. and Boutaba, R. (2010). A survey of network virtualization. Computer Networks, 54(5):862 – 876.
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. http://disco.ethz.ch/projects/sinalgo/index.html. Accessed 10-May-2017.
Hamedazimi, N., Qazi, Z., Gupta, H., Sekar, V., Das, S. R., Longtin, J. P., Shah, H., and Tanwer, A. (2014). Firefly: A reconfigurable wireless data center fabric using free-space optics. In ACM SIGCOMM Computer Communication Review, volume 44, pages 319–330. ACM.
Hu, Z., Qiao, Y., and Luo, J. (2015). Coarse-grained traffic matrix estimation for data center networks. Computer Communications, 56:25–34.
Kandula, S., Sengupta, S., Greenberg, A., Patel, P., and Chaiken, R. (2009). The nature of data center traffic: measurements & analysis. In Proc. 9th ACM Internet Measurement Conference (IMC), pages 202–208.
Kreutz, D., Ramos, F. M., Verissimo, P. E., Rothenberg, C. E., Azodolmolky, S., and Uhlig, S. (2015). Software-defined networking: A comprehensive survey. Proceedings of the IEEE, 103(1):14–76.
Liu, H., Lu, F., Forencich, A., Kapoor, R., Tewari, M., Voelker, G. M., Papen, G., Snoeren, A. C., and Porter, G. (2014). Circuit switching under the radar with reactor. In NSDI, volume 14, pages 1–15.
Peres, B., Souza, O., Goussevskaia, O., Schmid, S., and Avin, C. (2019). Distributed self-adjusting tree networks. In Proc. IEEE INFOCOM.
Reiter, M. K., Samar, A., and Wang, C. (2008). Self-optimizing distributed trees. In Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, pages 1–12.
Roy, A., Zeng, H., Bagga, J., Porter, G., and Snoeren, A. C. (2015). Inside the social network’s (datacenter) network. In ACM SIGCOMM Computer Communication Review, pages 123–137. ACM.
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.
Singla, A., Singh, A., Ramachandran, K., Xu, L., and Zhang, Y. (2010). Proteus: a topology malleable data center network. In Proc. ACM Workshop on Hot Topics in Networks (HotNets).
Sleator, D. and Tarjan, R. (1985). Self-adjusting binary search trees. Journal of the ACM (JACM), 32(3):652–686.
Zhou, X., Zhang, Z., Zhu, Y., Li, Y., Kumar, S., Vahdat, A., Zhao, B. Y., and Zheng, H. (2012). Mirror mirror on the ceiling: Flexible wireless links for data centers. ACM SIGCOMM Computer Communication Review, 42(4):443–454.
Publicado
07/12/2020
Como Citar
SOUZA, Otávio Augusto de Oliviera; CALDEIRA, Caio; GOUSSEVSKAIA, Olga.
FlatNet: Uma Rede Auto-Reconfigurável Distribuída e Concorrente com Topologia em Árvore Binária. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 38. , 2020, Rio de Janeiro.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 644-657.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2020.12315.
