Publication details for Professor Iain StewartErickson, A., Kiasari, A.E., Navaridas, J. & Stewart, I.A. (2015), An efficient shortest path routing algorithm in the data centre network DPillar, in Lu, Z., Kim, D., Wu, W., Li, W. & Du, D.-Z. eds, Lecture Notes in Computer Science 9486: 9th Annual International Conference on Combinatorial Optimization and Applications, COCOA. Houston, USA, Springer, 209-220.
- Publication type: Conference Paper
- ISSN/ISBN: 978-3-319-26625-1 (paperback), 978-3-319-26626-8 (online)
- DOI: 10.1007/978-3-319-26626-8_16
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
- View in another repository - may include full text
Author(s) from Durham
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.