We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

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

Erickson, A. and Kiasari, A.E. and Navaridas, J. and Stewart, I.A. (2015) 'An efficient shortest path routing algorithm in the data centre network DPillar.', in Combinatorial optimization and applications: 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, proceedings. , pp. 209-220. Lecture notes in computer science., 9486


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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:The final publication is available at Springer via
Date accepted:01 September 2015
Date deposited:31 March 2016
Date of first online publication:December 2015
Date first made open access:09 December 2016

Save or Share this output

Look up in GoogleScholar