Redes Auto-Reconfiguráveis Randomizadas para Comunicação Distribuída em Datacenters

• Otávio A. O. Souza UFMG
• Caio Caldeira UFMG
• Olga Goussevskaia UFMG

DOI: https://doi.org/10.5753/sbrc.2022.222336

Abstract

In this paper we investigate the benefits of randomization in the design of self-adjusting network topologies: networks that dynamically adapt themselves toward the demand they currently serve, in an online manner. We present a randomized self-adjusting tree network, which leverages randomization to reduce the expected network reconfiguration cost by a constant factor, compared to existing deterministic solutions. The new solution is simple, easyto-implement, fully distributed and concurrent. We prove algorithm correctness, provide worst-case amortized cost limits, and present simulation results on workloads with variable spatial and temporal complexity.

References

(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).