An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar
An Optimal Single-Path Routing Algorithm in the Datacenter Network DPillar
复制标题
DOI：
10.1109/tpds.2016.2591011
复制
发表时间：
2015-09
影响因子：
5.3
通讯作者：
Alejandro Erickson;A. E. Kiasari;J. Navaridas;I. A. Stewart
中科院分区：
文献类型：
--
作者：
Alejandro Erickson;A. E. Kiasari;J. Navaridas;I. A. Stewart
DPillar 最近被提议作为以服务器为中心的数据中心网络，并且与著名的包装蝴蝶网络组合相关（但不同）。在证明DPillar的底层图是凯莱图之前，我们先解释一下DPillar和包裹蝴蝶网络之间的关系；因此，数据中心网络 DPillar 是节点对称的。我们利用这种对称性为 DPillar 建立单路径路由算法，计算最短路径，时间复杂度为 $O(k)$ ，其中 $k$ 参数化 DPillar 的维度（我们将其交换机中的端口数量称为 $n$ ）。我们的分析还使我们能够准确计算 DPillar 的直径。此外，我们的算法实现起来很简单，本质上是数值测试的条件子句，并且比早期用于 DPillar 的路由算法有了显着改进。此外，我们提供经验数据来证明这种改进。特别是，我们凭经验表明，我们的路由算法改善了找到的路径的平均长度、总瓶颈吞吐量和通信延迟。我们工作的第二个但重要的效果是，它强调数据中心网络适合更严格的组合审查，可以显着提高其计算效率和性能。
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.