An optimal single-path routing algorithm in the Datacenter Network DPillar

Alejandro Erikson, Abbas E. Kiasari, Javier Navaridas Palma, Iain A. Stewart

Research output: Contribution to journalArticlepeer-review

109 Downloads (Pure)


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
Original languageEnglish
Pages (from-to)689 - 703
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
Early online date13 Jul 2016
Publication statusPublished - 1 Mar 2017


Dive into the research topics of 'An optimal single-path routing algorithm in the Datacenter Network DPillar'. Together they form a unique fingerprint.

Cite this