Parity Balancing Path Flow Decomposition and Routing
Parity Balancing Path Flow Decomposition and Routing
复制标题
奇偶平衡路径流分解和路由
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Sean Yaw
中科院分区：
文献类型：
--
作者：
B. Mumey;Samareh Shahmohammadi;Kathryn McManus;Sean Yaw
我们研究了一种在大型网络（例如数据中心间网络）中寻找有效路由路径的新方法。此类网络同时承载许多数据传输，并且需要为每次传输找到有效的路由路径。解决这个问题的一种方法是首先找到所有源-汇对的多商品流解决方案。这提供了每个连接的流量信息，但不指定要使用的特定路由路径。我们考虑将这些流解决方案分解为少量路由路径的问题。我们考虑的具体问题如下：给定一个具有源节点 s 和汇节点 t 的流，我们希望将该流精确地表示为少量路径流的总和。在这项工作中，我们描述了一种使用奇偶平衡路径流寻找良好流分解解决方案的新颖方法。我们提出了两种新算法，称为 OddCover 和 JointOdd-Cover，它们提供了理论性能保证并且在实践中有效。我们的实验结果表明，所提出的算法与最佳启发式方法具有竞争力。
We examine a new approach to finding efficient routing paths in large networks (e.g. inter-datacenter networks). Such networks carry many simultaneous data transmissions and efficient routing paths need to be found for each transmission. One way this problem can be solved is by first finding a multi-commodity flow solution for all source-sink pairs. This provides traffic flow information for each connection but does not specify specific routing paths to use. We consider the problem of decomposing these flow solutions into a small numbers of routing paths. The specific problem we consider is the following: Given a flow with source and sink nodes s and t, we wish to exactly represent the flow as the sum of a small number of path flows. In this work, we describe a novel approach to finding good flow decomposition solutions using parity balancing path flows. We present two new algorithms termed OddCover and JointOdd-Cover that provide theoretical performance guarantees and are effective in practice. Our experimental results demonstrate that the proposed algorithms are competitive with the best heuristic approach.