An efficient shortest-path routing algorithm in the data centre network DPillar

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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

Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Proceedings
EditorsDonghyun Kim, Weili Wu, Ding-Zhu Du, Zaixin Lu, Wei Li
PublisherSpringer Nature
Pages209-220
Number of pages12
Volume9486
ISBN (Print)9783319266251
DOIs
Publication statusPublished - 1 Jan 2015
Event9th International Conference on Combinatorial Optimization and Applications, COCOA 2015 - Houston, United States
Duration: 18 Dec 201520 Dec 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9486
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Combinatorial Optimization and Applications, COCOA 2015
Country/TerritoryUnited States
CityHouston
Period18/12/1520/12/15

Keywords

  • Data centre networks
  • Routing algorithms
  • Shortest paths

Fingerprint

Dive into the research topics of 'An efficient shortest-path routing algorithm in the data centre network DPillar'. Together they form a unique fingerprint.

Cite this