nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching

verfasst von : Liang Liu, Long Gong, Sen Yang, Jun (Jim) Xu, Lance Fortnow

Erschienen in: Cloud Computing – CLOUD 2018

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A hybrid-switched data center network interconnects its racks of servers with a combination of a fast circuit switch that a schedule can reconfigure at significant cost and a much slower packet switch that a schedule can reconfigure at negligible cost. Given a traffic demand matrix between the racks, how can we best compute a good circuit switch configuration schedule that meets most of the traffic demand, leaving as little as possible for the packet switch to handle?

In this paper we propose 2-hop Eclipse, a new hybrid switch scheduling algorithm that strikes a much better tradeoff between the performance of the hybrid switch and the computational complexity of the algorithm, both in theory and in simulations, than the current state of the art solution Eclipse/Eclipse++.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Teleporting Failed Writes with Cache Augmented Data Stores

Nächstes Kapitel A Prediction Approach to Define Checkpoint Intervals in Spot Instances

DeCusatis, C.: Optical interconnect networks for data communications. J. Lightw. Technol. 32(4), 544–552 (2014)CrossRef

Patel, P., et al.: Ananta: cloud scale load balancing. In: SIGCOMM Computer Communication Review, vol. 43, pp. 207–218. ACM (2013)CrossRef

Farrington, N., et al.: Helios: a hybrid electrical/optical switch architecture for modular data centers. SIGCOMM Comput. Commun. Rev. 40(4), 339–350 (2010)CrossRef

Wang, H., et al.: Design and demonstration of an all-optical hybrid packet and circuit switched network platform for next generation data centers. In: OFC. Optical Society of America (2010)

Farrington, N., et al.: A 10 us hybrid optical-circuit/electrical-packet network for datacenters. In: OFC. Optical Society of America (2013)

Chen, K., et al.: OSA: an optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACM Trans. Netw. 22(2), 498–511 (2014)CrossRef

Wang, G., et al.: c-through: part-time optics in data centers. In: SIGCOMM Computer Communication Review, vol. 40, pp. 327–338. ACM (2010)CrossRef

Liu, H., et al.: Circuit switching under the radar with REACToR. NSDI 14, 1–15 (2014)

Porter, G., et al.: Integrating microsecond circuit switching into the data center. SIGCOMM Comput. Commun. Rev. 43(4), 447–458 (2013)CrossRef

10.

Li, X., et al.: On scheduling optical packet switches with reconfiguration delay. IEEE J. Sel. Areas Commun. 21(7), 1156–1164 (2003)CrossRef

11.

Bojja Venkatakrishnan, S., et al.: Costly circuits, submodular schedules and approximate carathéodory theorems. In: SIGMETRICS, pp. 75–88. ACM (2016)CrossRef

12.

Li, C., et al.: Using indirect routing to recover from network traffic scheduling estimation error. In: ACM/IEEE Symposium on Architectures for Networking and Communications Systems (2017)

13.

Even, S., et al.: On the complexity of time table and multi-commodity flow problems. In: FOCS, pp. 184–193. IEEE (1975)

14.

Ford Jr., L.R., et al.: A suggested computation for maximal multi-commodity network flows. Manage. Sci. 5(1), 97–101 (1958)MathSciNetCrossRef

15.

Chiang, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344–360 (1963)CrossRef

16.

Garg, N., et al.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630–652 (2007)MathSciNetCrossRef

17.

Bojja Venkatakrishnan, S.: In-Person Discussions at Sigmetrics Conference, June 2017

18.

Mekkittikul, A., et al.: A starvation-free algorithm for achieving 100% throughput in an input-queued switch. In: Proceedings of ICCCN, vol. 96, pp. 226–231. Citeseer (1996)

19.

Liu, H., et al.: Scheduling techniques for hybrid circuit/packet networks. In: ACM CoNEXT. CoNEXT 2015, pp. 41:1–41:13. ACM, New York. ACM (2015)

20.

Duan, R., et al.: A scaling algorithm for maximum weight matching in bipartite graphs. In: SODA, pp. 1413–1424. SIAM (2012)CrossRef

21.

Benson, T., et al.: Network traffic characteristics of data centers in the wild. In: IMC, pp. 267–280. ACM (2010)

22.

Ghobadi, M., et al.: ProjecTOR: agile reconfigurable data center interconnect. In: SIGCOMM, pp. 216–229 (2016)

23.

Hamedazimi, N., et al.: FireFLY: a reconfigurable wireless data center fabric using free-space optics. In: SIGCOMM, pp. 319–330 (2014)CrossRef

24.

Gale, D., et al.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9–15 (1962)MathSciNetCrossRef

25.

Inukai, T.: An efficient SS/TDMA time slot assignment algorithm. IEEE Trans. Commun. 27(10), 1449–1455 (1979)MathSciNetCrossRef

26.

Towles, B., et al.: Guaranteed scheduling for switches with configuration overhead. IEEE/ACM Trans. Netw. 11(5), 835–847 (2003)CrossRef

27.

Wu, B., et al.: Nxg05-6: minimum delay scheduling in scalable hybrid electronic/optical packet switches. In: GLOBECOM, pp. 1–5. IEEE (2006)

28.

Gopal, I.S., et al.: Minimizing the number of switchings in an SS/TDMA system. IEEE Trans. Commun. 33(6), 497–501 (1985)CrossRef

29.

Fu, S., et al.: Cost and delay tradeoff in three-stage switch architecture for data center networks. In: HPSR, pp. 56–61. IEEE (2013)

30.

Wang, C.-H., et al.: End-to-end scheduling for all-optical data centers. In: INFOCOM, pp. 406–414. IEEE (2015)

31.

Wang, C.-H.: et al.: Heavy traffic queue length behavior in switches with reconfiguration delay. arXiv preprint arXiv:1701.05598 (2017)

Titel: 2-Hop Eclipse: A Fast Algorithm for Bandwidth-Efficient Data Center Switching
verfasst von: Liang Liu
Long Gong
Sen Yang
Jun (Jim) Xu
Lance Fortnow
Verlag: Springer International Publishing
Buch: Cloud Computing – CLOUD 2018
Print ISBN: 978-3-319-94294-0

Electronic ISBN: 978-3-319-94295-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-94295-7_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner