A. Erickson
An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar
Erickson, A.; Kiasari, A.E.; Navaridas, J.; Stewart, I.A.
Abstract
DPillar has recently been proposed as a server-centric datacenter network and is combinatorially related to (but distinct from) the well-known wrapped butterfly network. We explain the relationship between DPillar and the wrapped butterfly network before proving that the underlying graph of DPillar is a Cayley graph; hence, the datacenter network DPillar is node-symmetric. 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), where k parameterizes the dimension of DPillar (we refer to the number of ports in its switches as n). Our analysis also enables us to calculate the diameter of DPillar exactly. 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. Furthermore, we provide empirical data in order to demonstrate this improvement. In particular, we empirically show that our routing algorithm improves the average length of paths found, the aggregate bottleneck throughput, and the communication latency. A secondary, yet important, effect of our work is that it emphasises that datacenter 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. (2016). An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar. IEEE Transactions on Parallel and Distributed Systems, 28(3), 689-703. https://doi.org/10.1109/tpds.2016.2591011
Journal Article Type | Article |
---|---|
Acceptance Date | Jul 7, 2016 |
Online Publication Date | Jul 13, 2016 |
Publication Date | Jul 13, 2016 |
Deposit Date | Jul 13, 2016 |
Publicly Available Date | Jul 19, 2016 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Print ISSN | 1045-9219 |
Electronic ISSN | 1558-2183 |
Publisher | Institute of Electrical and Electronics Engineers |
Peer Reviewed | Peer Reviewed |
Volume | 28 |
Issue | 3 |
Pages | 689-703 |
DOI | https://doi.org/10.1109/tpds.2016.2591011 |
Public URL | https://durham-repository.worktribe.com/output/1378035 |
Files
Accepted Journal Article
(424 Kb)
PDF
Copyright Statement
© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
You might also like
Routing algorithms for recursively-defined data centre networks
(2015)
Presentation / Conference Contribution
Accelerating ant colony optimization-based edge detection on the GPU using CUDA
(2014)
Presentation / Conference Contribution
Improved routing in the data centre networks HCN and BCN
(2014)
Presentation / Conference Contribution
Improving Ant Colony Optimization performance on the GPU using CUDA.
(2013)
Presentation / Conference Contribution
Color image edge detection based on quantity of color information and implementation on the GPU.
(2011)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search