Document Open Access Logo

Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks

Authors Neta Rozen-Schiff , Klaus-Tycho Foerster , Stefan Schmid , David Hay



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.25.pdf
  • Filesize: 1.29 MB
  • 23 pages

Document Identifiers

Author Details

Neta Rozen-Schiff
  • School of computer science and engineering, The Hebrew University of Jerusalem, Israel
Klaus-Tycho Foerster
  • Computer Science Department, TU Dortmund, Germany
Stefan Schmid
  • TU Berlin, Germany
  • Faculty of Computer Science, Universität Wien, Austria
David Hay
  • School of computer science and engineering, The Hebrew University of Jerusalem, Israel

Cite AsGet BibTex

Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay. Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.OPODIS.2022.25

Abstract

The performance of distributed and data-centric applications often critically depends on the interconnecting network. Emerging reconfigurable datacenter networks (RDCNs) are a particularly innovative approach to improve datacenter throughput. Relying on a dynamic optical topology which can be adjusted towards the workload in a demand-aware manner, RDCNs allow to exploit temporal and spatial locality in the communication pattern, and to provide topological shortcuts for frequently communicating racks. The key challenge, however, concerns how to realize demand-awareness in RDCNs in a scalable fashion. This paper presents and evaluates Chopin, a hybrid scheduler for self-adjusting networks that provides demand-awareness at low overhead, by combining centralized and distributed approaches. Chopin allocates optical circuits to elephant flows, through its slower centralized scheduler, utilizing global information. Chopin’s distributed scheduler is orders of magnitude faster and can swiftly react to changes in the traffic and adjust the optical circuits accordingly, by using only local information and running at each rack separately.

Subject Classification

ACM Subject Classification
  • Networks → Programmable networks
  • Networks → Data center networks
Keywords
  • reconfigurable optical networks
  • centralized scheduler
  • distributed scheduler

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mohammad Alizadeh. Empirical traffic generator. Cisco DC Repositories, 2015. Google Scholar
  2. Mohammad Alizadeh, Albert Greenberg, David A. Maltz, Jitendra Padhye, Parveen Patel, Balaji Prabhakar, Sudipta Sengupta, and Murari Sridharan. Data center tcp (dctcp). In ACM SIGCOMM, 2010. Google Scholar
  3. Mohammad Alizadeh, Abdul Kabbani, Tom Edsall, Balaji Prabhakar, Amin Vahdat, and Masato Yasuda. Less is more: Trading a little bandwidth for ultra-low latency in the data center. In NSDI. USENIX Association, 2012. Google Scholar
  4. Richard P. Anstee. A polynomial algorithm for b-matchings: An alternative approach. Inf. Process. Lett., 24(3):153-157, 1987. Google Scholar
  5. John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, and Philipp Schneider. Shortest paths in a hybrid network model. In SODA, pages 1280-1299. SIAM, 2020. Google Scholar
  6. Chen Avin, Manya Ghobadi, Chen Griner, and Stefan Schmid. On the complexity of traffic traces and implications. In Proc. ACM SIGMETRICS, 2020. Google Scholar
  7. Navid Hamed Azimi, Zafar Ayyub Qazi, Himanshu Gupta, Vyas Sekar, Samir R. Das, Jon P. Longtin, Himanshu Shah, and Ashish Tanwer. Firefly: a reconfigurable wireless data center fabric using free-space optics. In SIGCOMM. ACM, 2014. Google Scholar
  8. Hitesh Ballani, Paolo Costa, Raphael Behrendt, Daniel Cletheroe, István Haller, Krzysztof Jozwik, Fotini Karinou, Sophie Lange, Kai Shi, Benn Thomsen, and Hugh Williams. Sirius: A flat datacenter network with nanosecond optical switching. In SIGCOMM, pages 782-797. ACM, 2020. Google Scholar
  9. Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. J. ACM, 68(5):39:1-39:30, 2021. Google Scholar
  10. T. Benson, A. Akella, and D.A. Maltz. Network traffic characteristics of data centers in the wild. In ACM IMC, pages 267-280, 2010. Google Scholar
  11. André Berger, James Gross, Tobias Harks, and Simon Tenbusch. Constrained resource assignments: Fast algorithms and applications in wireless networks. Management Science, 62, November 2015. Google Scholar
  12. Maciej Besta and Torsten Hoefler. Slim fly: A cost effective low-diameter network topology. In IEEE SC, pages 348-359, 2014. Google Scholar
  13. Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger. Deterministic dynamic matching in O(1) update time. Algorithmica, 82(4):1057-1080, 2020. Google Scholar
  14. Li Chen, Kai Chen, Zhonghua Zhu, Minlan Yu, George Porter, Chunming Qiao, and Shan Zhong. Enabling wide-spread communications on optical fabric with megaswitch. In USENIX NDSI, 2017. Google Scholar
  15. Charles Clos. A study of non-blocking switching network. Bell System Technology Journal, 32(2):406-424, 1953. Google Scholar
  16. Shibsankar Das. A modified decomposition algorithm for maximum weight bipartite matching and its experimental evaluation. Sci. Ann. Comput. Sci., 30(1):39-67, 2020. Google Scholar
  17. Sushovan Das, Afsaneh Rahbar, Xinyu Crystal Wu, Zhuang Wang, Weitao Wang, Ang Chen, and T. S. Eugene Ng. Shufflecast: An optical, data-rate agnostic, and low-power multicast architecture for next-generation compute clusters. IEEE/ACM Trans. Netw., 30(5):1970-1985, 2022. Google Scholar
  18. Pamela Delgado, Florin Dinu, Anne-Marie Kermarrec, and Willy Zwaenepoel. Hawk: Hybrid datacenter scheduling. In USENIX ATC, 2015. Google Scholar
  19. Nikhil Devanur, Janardhan Kulkarni, Gireeja Ranade, Manya Ghobadi, Ratul Mahajan, and Amar Phanishayee. Stable matching algorithm for an agile reconfigurable data center interconnect. Technical Report 2016-1140, MSR, June 2016. Google Scholar
  20. Fahad Dogar, Thomas Karagiannis, Hitesh Ballani, and Antony Rowstron. Decentralized task-aware scheduling for data center networks. ACM SIGCOMM CCR, 44, August 2014. Google Scholar
  21. N. Farrington, A. Forencich, G. Porter, P. C. Sun, J. E. Ford, Y. Fainman, G. C. Papen, and A. Vahdat. A multiport microsecond optical circuit switch for data center networking. IEEE Phot. Techn. L., 25(16):1589-92, August 2013. Google Scholar
  22. Nathan Farrington, Alex Forencich, Pang-Chen Sun, Shaya Fainman, Joe Ford, Amin Vahdat, George Porter, and George C. Papen. A 10 us hybrid optical-circuit/electrical-packet network for datacenters. In OFC/NFOEC. OSA, 2013. Google Scholar
  23. Nathan Farrington, George Porter, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Hunting mice with microsecond circuit switches. In ACM HotNets, 2012. Google Scholar
  24. Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: a hybrid electrical/optical switch architecture for modular data centers. In SIGCOMM. ACM, 2010. Google Scholar
  25. Thomas Fenz, Klaus-Tycho Foerster, Stefan Schmid, and Anaïs Villedieu. Efficient non-segregated routing for reconfigurable demand-aware networks. Comput. Commun., 164:138-147, 2020. Google Scholar
  26. Klaus-Tycho Foerster, Maciej Pacut, and Stefan Schmid. On the complexity of non-segregated routing in reconfigurable data center architectures. Comput. Commun. Rev., 49(2):2-8, 2019. Google Scholar
  27. Klaus-Tycho Foerster and Stefan Schmid. Survey of reconfigurable data center networks: Enablers, algorithms, complexity. SIGACT News, 50(2):62-79, 2019. Google Scholar
  28. Harold N. Gabow. Data structures for weighted matching and extensions to b-matching and f-factors. ACM Trans. Algorithms, 14(3):39:1-39:80, 2018. Google Scholar
  29. Zvi Galil. Efficient algorithms for finding maximum matching in graphs. ACM Comput. Surv., 18(1):23-38, March 1986. Google Scholar
  30. Manya Ghobadi, Ratul Mahajan, Amar Phanishayee, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel Kilper. Design of mirror assembly for an agile reconfigurable data center interconnect. Technical Report 2016-1139, MSR, June 2016. Google Scholar
  31. Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel Kilper. Projector: Agile reconfigurable data center interconnect. In ACM SIGCOMM, pages 216-229, 2016. Google Scholar
  32. A. Greenberg, J. R. Hamilton, N. Jain, S.Kandula, C.Kim, P. Lahiri, D. A. Maltz, P. Patel, and S. Sengupta. VL2: A scalable and flexible data center network. ACM SIGCOMM, 39(4):51-62, 2009. Google Scholar
  33. A. Grieco, G. Porter, and Y. Fainman. Integrated space-division multiplexer for application to data center networks. IEEE J. Sel. Top. Quant. El., 22(6), 2016. Google Scholar
  34. Chen Griner, Stefan Schmid, and Chen Avin. Cachenet: Leveraging the principle of locality in reconfigurable network design. Computer Networks, 204:108648, 2022. Google Scholar
  35. Chen Griner, Johannes Zerwas, Andreas Blenk, Manya Ghobadi, Stefan Schmid, and Chen Avin. Cerberus: The power of choices in datacenter topology design - A throughput perspective. Proc. ACM Meas. Anal. Comput. Syst., 5(3):38:1-38:33, 2021. Google Scholar
  36. Matthew Nance Hall, Klaus-Tycho Foerster, Stefan Schmid, and Ramakrishnan Durairajan. A survey of reconfigurable optical networks. Opt. Switch. Netw., 41:100621, 2021. Google Scholar
  37. Daniel Halperin, Srikanth Kandula, Jitendra Padhye, Paramvir Bahl, and David Wetherall. Augmenting data center networks with multi-gigabit wireless links. In SIGCOMM, pages 38-49. ACM, 2011. Google Scholar
  38. Y. Han, J.H. Yoo, and J.W.K. Hong. Poisson shot-noise process based flow-level traffic matrix generation for data center networks. In IFIP/IEEE IM, May 2015. Google Scholar
  39. Kathrin Hanauer, Monika Henzinger, Stefan Schmid, and Jonathan Trummer. Fast and heavy disjoint weighted matchings for demand-aware datacenter topologies. In INFOCOM, pages 1649-1658. IEEE, 2022. Google Scholar
  40. Keqiang He, Junaid Khalid, Aaron Gember-Jacobson, Sourav Das, Chaithan Prakash, Aditya Akella, Li Erran Li, and Marina Thottan. Measuring control plane latency in sdn-enabled switches. In ACM SIGCOMM, SOSR '15, pages 25:1-25:6, 2015. Google Scholar
  41. Netflix help center. Internet connection speed recommendations, 2018. URL: https://help.netflix.com/en/node/306.
  42. Mikel Jimenez and Henry Kwik. Building Express Backbone: Facebook’s new long-haul network, May 2017. URL: https://engineering.fb.com/data-center-engineering/building-express-backbone-facebook-s-new-long-haul-network/.
  43. Mikel Jimenez and Henry Kwik. Ternary Content Addressable Memory (TCAM) Search IP for SDNet - SmartCORE IP Product Guide. Technical report, Xilinx, November 2017. URL: https://www.xilinx.com/support/documentation/ip_documentation/tcam/pg190-tcam.pdf.
  44. S. Kandula, J. Padhye, and P. Bahl. Flyways to de-congest data center networks. In ACM HotNets, 2009. Google Scholar
  45. S. Kandula, S. Sengupta, A. Greenberg, P. Patel, and R. Chaiken. The nature of data center traffic: Measurements & analysis. In ACM IMC, pages 202-208, 2009. Google Scholar
  46. Simon Kassing, Asaf Valadarsky, Gal Shahaf, Michael Schapira, and Ankit Singla. Beyond fat-trees without antennae, mirrors, and disco-balls. In SIGCOMM, pages 281-294. ACM, 2017. Google Scholar
  47. Arif M. Khan, Alex Pothen, Md. Mostofa Ali Patwary, Nadathur Rajagopalan Satish, Narayanan Sundaram, Fredrik Manne, Mahantesh Halappanavar, and Pradeep Dubey. Efficient approximation algorithms for weighted b-matching. SIAM J. Sci. Comput., 38(5), 2016. Google Scholar
  48. Viatcheslav Korenwein. The practical power of data reduction for maximum-cardinality matching. Masterthesis, TU Berlin, January 2018. Master thesis. URL: http://fpt.akt.tu-berlin.de/publications/theses/ma-viatcheslav-korenwein.pdf.
  49. M. Kuzniar, P. Peresini, and D. Kostic. What you need to know about sdn control and data planes. Technical report, EPFL, 2014. Google Scholar
  50. Adam N. Letchford, Gerhard Reinelt, and Dirk Oliver Theis. Odd minimum cut sets and b-matchings revisited. SIAM J. Discret. Math., 22(4):1480-1487, 2008. Google Scholar
  51. Z. Li, W. Bai, K. Chen, D. Han, Y. Zhang, D. Li, and H. Yu. Rate-aware flow scheduling for commodity data center networks. In IEEE INFOCOM, pages 1-9, 2017. URL: https://doi.org/10.1109/INFOCOM.2017.8057082.
  52. Xiao Ling, Yi Yuan, Dan Wang, Jiangchuan Liu, and Jiahai Yang. Joint scheduling of mapreduce jobs with servers. J. Parallel Distrib. Comput., 90(C):52-66, April 2016. Google Scholar
  53. He Liu, Feng Lu, Alex Forencich, Rishi Kapoor, Malveeka Tewari, Geoffrey M. Voelker, George Papen, Alex C. Snoeren, and George Porter. Circuit switching under the radar with reactor. In USENIX NSDI, pages 1-15, April 2014. Google Scholar
  54. He Liu, Feng Lu, Alex Forencich, Rishi Kapoor, Malveeka Tewari, Geoffrey M. Voelker, George Papen, Alex C. Snoeren, and George Porter. Circuit switching under the radar with reactor. In USENIX NSDI, pages 1-15, 2014. Google Scholar
  55. Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. J. ACM, 62(5):38:1-38:17, 2015. Google Scholar
  56. Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén. Distributed approximate matching. SIAM J. Comput., 39(2):445-460, 2009. Google Scholar
  57. Long Luo, Klaus-Tycho Foerster, Stefan Schmid, and Hongfang Yu. Optimizing multicast flows in high-bandwidth reconfigurable datacenter networks. J. Netw. Comput. Appl., 203:103399, 2022. Google Scholar
  58. William M. Mellette, Rajdeep Das, Yibo Guo, Rob McGuinness, Alex C. Snoeren, and George Porter. Expanding across time to deliver bandwidth efficiency and low latency . In NSDI. USENIX Association, 2020. Google Scholar
  59. William M. Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C. Snoeren, and George Porter. Rotornet: A scalable, low-complexity, optical datacenter network. In SIGCOMM. ACM, 2017. Google Scholar
  60. Alizadeh Mohammad, Yang Shuang, Sharif Milad, Katti Sachin, McKeown Nick, Prabhakar Balaji, and Shenker Scott. pfabric: Minimal near-optimal datacenter transport. ACM SIGCOMM, 43(4):435-446, 2013. Google Scholar
  61. Matthias Müller-Hannemann and Alexander Schwartz. Implementing weighted b-matching algorithms: Insights from a computational study. ACM Journal of Experimental Algorithmics, 5:8, 2000. Google Scholar
  62. George Porter, Richard Strong, Nathan Farrington, Alex Forencich, Pang Chen-Sun, Tajana Rosing, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Integrating microsecond circuit switching into the data center. ACM SIGCOMM, 43(4):447-458, 2013. Google Scholar
  63. George Porter, Richard D. Strong, Nathan Farrington, Alex Forencich, Pang-Chen Sun, Tajana Rosing, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Integrating microsecond circuit switching into the data center. In SIGCOMM, pages 447-458. ACM, 2013. Google Scholar
  64. Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Muhammad Mukarram Bin Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve D. Gribble, Rishi Kapoor, Stephen Kratzer, Nanfang Li, Hong Liu, Karthik Nagaraj, Jason Ornstein, Samir Sawhney, Ryohei Urata, Lorenzo Vicisano, Kevin Yasumura, Shidong Zhang, Junlan Zhou, and Amin Vahdat. Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking. In SIGCOMM, pages 66-85. ACM, 2022. Google Scholar
  65. Y. Qiao, Z. Hu, and J. Luo. Efficient traffic matrix estimation for data center networks. In IFIP Networking, pages 1-9, May 2013. Google Scholar
  66. Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex C. Snoeren. Inside the social network’s (datacenter) network. In SIGCOMM. ACM, 2015. Google Scholar
  67. Neta Rozen-Schiff, David Hay, Stefan Schmid, and Klaus-Tycho Foerster. Chopin implementation code. https://bitbucket.org/NetaRS/sched_analytics/src/master/, October 2020.
  68. Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. Splaynet: Towards locally self-adjusting networks. IEEE/ACM Trans. Netw., 24(3):1421-1433, 2016. Google Scholar
  69. Ankit Singla, Chi-Yao Hong, Lucian Popa, and Philip Brighten Godfrey. Jellyfish: Networking data centers, randomly. In USENIX NSDI, volume 12, 2012. Google Scholar
  70. Ankit Singla, Atul Singh, and Yan Chen. OSA: An optical switching architecture for data center networks with unprecedented flexibility. In USENIX NSDI, 2012. Google Scholar
  71. T. A. Strasser and J. L. Wagener. Wavelength-selective switches for roadm applications. IEEE J. Sel. Top. Quant. El., 16(5), 2010. Google Scholar
  72. Xiaoye Steven Sun and T. S. Eugene Ng. When creek meets river: Exploiting high-bandwidth circuit switch in scheduling multicast data. In ICNP, pages 1-6. IEEE Computer Society, 2017. Google Scholar
  73. Jukka Suomela. Survey of local algorithms. ACM Comput. Surv., 45(2):24:1-24:40, 2013. Google Scholar
  74. Akhilesh S. Thyagaturu, Anu Mercian, Michael P. McGarry, Martin Reisslein, and Wolfgang Kellerer. Software defined optical networks (sdons): A comprehensive survey. IEEE Commun. Surv. Tutorials, 18(4):2738-2786, 2016. Google Scholar
  75. Gerard J Tortora and Bryan H Derrickson. Principles of anatomy and physiology. John Wiley & Sons, 2018. Google Scholar
  76. Asaf Valadarsky, Gal Shahaf, Michael Dinitz, and Michael Schapira. Xpander: Towards optimal-performance datacenters. In ACM CoNEXT, 2016. Google Scholar
  77. R. Veisllari, S. Bjornstad, and N. Stol. Scheduling techniques in an integrated hybrid node with electronic buffers. In ONDM, April 2012. Google Scholar
  78. Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, and Pramod Viswanath. Costly circuits, submodular schedules and approximate carathéodory theorems. In SIGMETRICS. ACM, 2016. Google Scholar
  79. Guohui Wang, David G. Andersen, Michael Kaminsky, Konstantina Papagiannaki, T. S. Eugene Ng, Michael Kozuch, and Michael P. Ryan. c-through: part-time optics in data centers. In SIGCOMM, pages 327-338. ACM, 2010. Google Scholar
  80. Yiting Xia, Xiaoye Steven Sun, Simbarashe Dzinamarira, Dingming Wu, Xin Sunny Huang, and T. S. Eugene Ng. A tale of two topologies: Exploring convertible data center network architectures with flat-tree. In SIGCOMM, pages 295-308. ACM, 2017. Google Scholar
  81. Bing Xiong, Kun Yang, Jinyuan Zhao, Wei Li, and Keqin Li. Performance evaluation of openflow-based software-defined networks based on queueing model. Comput. Netw., 102(C):172-185, 2016. Google Scholar
  82. Haining Yang, Brian Robertson, Peter Wilkinson, and Daping Chu. Low-cost cdc roadm architecture based on stacked wavelength selective switches. J. Opt. Commun. Netw., 9(5):375-384, May 2017. Google Scholar
  83. Johannes Zerwas, Chen Avin, Stefan Schmid, and Andreas Blenk. Exrec: Experimental framework for reconfigurable networks based on off-the-shelf hardware. In ANCS, pages 66-72. ACM, 2021. Google Scholar
  84. Johannes Zerwas, Wolfgang Kellerer, and Andreas Blenk. What you need to know about optical circuit reconfigurations in datacenter networks. In ITC, pages 1-9. IEEE, 2021. Google Scholar
  85. Danyang Zhuo, Qiao Zhang, Vincent Liu, Arvind Krishnamurthy, and Thomas Anderson. Rack-level congestion control. In ACM HotNets, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail