A randomized rounding approach to a k-splittable multicommodity flow problem with lower path flow bounds affording solution quality guarantees

详细信息    查看全文

• 作者：Paweł M. Białoń
• 关键词：k ; Splittable flow ; Randomized rounding ; Multicommodity flow
• 刊名：Telecommunication Systems
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：64
• 期：3
• 页码：525-542
• 全文大小：943KB
• 刊物类别：Business and Economics
• 刊物主题：IT in Business; Computer Communication Networks; Artificial Intelligence (incl. Robotics); Probability Theory and Stochastic Processes;
• 出版者：Springer US
• ISSN：1572-9451
• 卷排序：64

文摘

In 2005, Baier et al. introduced a “k-splittable” variant of the multicommodity flow (MCF) problem in which a given commodity was allowed to flow through a number of paths limited by a small integer. This problem enables a better use of the link capacities than the classical Kleinberg’s unsplittable MCF problem while not overloading the used devices and protocols with a large number of paths. We solve a minimum-congestion k-splittable MCF problem coming from a practice of managing an software-defined, circuit switching network. We introduce a lower bound for a path flow in order to model a QoS demand for a single connection running the path. Instead of reducing the problem to the unsplittable flow problem, as suggested by Baier et al., we propose a potentially more exact method. We directly enhance the Raghavan and Thompson’s randomized rounding for ordinary MCF problems to account for k-splittability and the lower flow bounds. A mechanism is constructed that prevents rounding up low flows in the subproblem solution to big values. It is based on modifying the continuous subproblem by additionally penalizing flows of certain commodities in certain links. When \(k=1\), this allows us to prove a property similar to the \(\mathcal O(\sqrt{\log m})\) approximation factor, where m denotes the number of network links. We give probabilistic guarantees for the solution quality and examine the behavior of the method experimentally.