Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Improved Algorithms for the Evacuation Route Planning Problem Read chapter Read first chapter

2015 | OriginalPaper | Chapter

An Efficient Shortest-Path Routing Algorithm in the Data Centre Network DPillar

Authors : Alejandro Erickson, Abbas Eslami Kiasari, Javier Navaridas, Iain A. Stewart

Published in: Combinatorial Optimization and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

DPillar has recently been proposed as a server-centric data centre network and is combinatorially related to the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network before proving a symmetry property of DPillar. We use this symmetry property to establish a single-path routing algorithm for DPillar that computes a shortest path and has time complexity \(O(k\log (n))\), where k parameterizes the dimension of DPillar and n the number of ports in its switches. Moreover, our algorithm is trivial to implement, being essentially a conditional clause of numeric tests, and improves significantly upon a routing algorithm earlier employed for DPillar. A secondary and important effect of our work is that it emphasises that data centre networks are amenable to a closer combinatorial scrutiny that can significantly improve their computational efficiency and performance.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter A Fast and Effective Heuristic for Discovering Small Target Sets in Social Networks
next chapter A Sensor Deployment Strategy in Bus-Based Hybrid Ad-Hoc Networks
Literature
1.
Abts, D., Marty, M.R., Wells, P.M., Klausler, P., Liu, H.: Energy proportional datacenter networks. In: Proceedings of the 37th Annual International Symposium on Computer Architecture, pp. 338–347 (2010)
2.
Abu-Libdeh, H., Costa, P., Rowstron, A., OShea, G., Donnelly, A.: Symbiotic routing in future data centers. SIGCOMM Comput. Comm. Rev. 40(4), 51–62 (2010)CrossRef
3.
Ahn, J.H., Binkert, N., Davis, A., McLaren, M., Schreiber, R.S.: HyperX: topology, routing, and packaging of efficient large-scale networks. In: Proceedings of the Conference on High Performance Computer Networking, Storage and Analysis, Article 41 (2009)
4.
Al-Fares, M., Loukissas, A., Vahdat, A.: A scalable, commodity data center network architecture. SIGCOMM Comput. Comm. Rev. 38(4), 63–74 (2008)CrossRef
5.
Greenberg, A., Hamilton, J.R., Jain, N., Kandula, S., Kim, C., Lahiri, P., Maltz, D.A., Patel, P., Sengupta, S.: VL2: a scalable and flexible data center network. SIGCOMM Comput. Comm. Rev. 39(4), 51–62 (2009)CrossRef
6.
Guo, D., Chen, T., Li, D., Li, M., Liu, Y., Chen, G.: Expandible and cost-effective network structures for data centers using dual-port servers. IEEE Trans. Comput. 62(7), 1303–1317 (2013)MathSciNetCrossRef
7.
Guo, C., Wu, H., Tan, K., Shi, L., Zhang, Y., Lu, S.: DCell: a scalable and fault-tolerant network structure for data centers. SIGCOMM Comput. Comm. Rev. 38(4), 75–86 (2008)CrossRef
8.
Guo, C., Lu, G., Li, D., Wu, H., Zhang, X., Shi, Y., Tian, C., Zhang, Y., Lu, S.: BCube: a high performance, server-centric network architecture for modular data centers. SIGCOMM Comput. Comm. Rev. 39(4), 63–74 (2009)CrossRef
9.
Heller, B., Seetharaman, S., Mahadevan, P., Yiakoumis, Y., Sharma, P., Banerjee, S., McKeown, N.: ElasticTree: saving energy in data center networks. In: Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation, pp. 249–264 (2006)
10.
Li, C., Guo, D., Wu, H., Tan, K., Zhang, K., Lu, S.: FiConn: using backup port for server interconnection in data centers. In: Proceedings of INFOCOM, pp. 2276–2285 (2009)
11.
Li, D., Wu, J.: On data center network architectures for interconnecting dual-port servers. IEEE Trans. Comput. 64(11), 3210–3222 (2015)MathSciNetCrossRef
12.
Liao, Y., Yin, J., Yin, D., Gao, L.: DPillar: dual-port server interconnection network for large scale data centers. Comput. Netw. 56(8), 2132–2147 (2012)CrossRef
13.
Liu, Y., Muppala, J.K., Veeraraghavan, M., Lin, D., Katz, J.: Data Centre Networks: Topologies, Architectures and Fault-Tolerance Characteristics. Springer, New York (2013)CrossRef
14.
Mysore, R.N., Pamboris, A., Farrington, N., Huang, N., Miri, P., Radhakrishnan, S., Subramanya, V., Vahdat, A.: Portland: a scalable fault-tolerant layer 2 data center network fabric. SIGCOMM Comput. Comm. Rev. 39(4), 39–50 (2009)CrossRef
15.
Wang, C., Wang, C., Yuan, Y., Wei, Y.: MCube: a high performance and fault-tolerant network architecture for data centers. In: Proceedings of the International Conference on Computer Design and Applications, vol. 5, pp. V5-423-V5–427 (2010)
Metadata
Title
An Efficient Shortest-Path Routing Algorithm in the Data Centre Network DPillar
Authors
Alejandro Erickson
Abbas Eslami Kiasari
Javier Navaridas
Iain A. Stewart
Copyright Year
2015
Book
Combinatorial Optimization and Applications

Print ISBN: 978-3-319-26625-1

Electronic ISBN: 978-3-319-26626-8

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-26626-8_16

Premium Partner

    Image Credits