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

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

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: Dec 9, 2016
• 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