Skip to main content

Research Repository

Advanced Search

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

Erickson, A.; Kiasari, A.E.; Navaridas, J.; Stewart, I.A.

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


Authors

A. Erickson

A.E. Kiasari

J. Navaridas



Contributors

Z. Lu
Editor

D. Kim
Editor

Wei Wu wei.wu4@durham.ac.uk
Editor

W. Li
Editor

D. -Z. Du
Editor

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

Citation

Erickson, A., Kiasari, A., Navaridas, J., & Stewart, I. (2015). An efficient shortest path routing algorithm in the data centre network DPillar. In Z. Lu, D. Kim, W. Wu, W. Li, & D. -. Du (Eds.), Combinatorial optimization and applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, proceedings (209-220). https://doi.org/10.1007/978-3-319-26626-8_16

Conference Name 9th Annual International Conference on Combinatorial Optimization and Applications, COCOA
Conference Location Houston, USA
Acceptance Date Sep 1, 2015
Publication Date Dec 1, 2015
Deposit Date Jan 27, 2016
Publicly Available Date Mar 29, 2024
Volume 9486
Pages 209-220
Series Title Lecture notes in computer science
Series ISSN 0302-9743
Book Title Combinatorial optimization and applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, proceedings.
ISBN 9783319266251
DOI https://doi.org/10.1007/978-3-319-26626-8_16
Public URL https://durham-repository.worktribe.com/output/1151524
Related Public URLs http://arxiv.org/pdf/1509.01746v1.pdf

Files





You might also like



Downloadable Citations