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

Paweł M. Białoń ()
Additional contact information
Paweł M. Białoń: National Institute of Telecommunications

Telecommunication Systems: Modelling, Analysis, Design and Management, 2017, vol. 64, issue 3, No 8, 525-542

Abstract: Abstract 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$$ k = 1 , this allows us to prove a property similar to the $$\mathcal O(\sqrt{\log m})$$ O ( 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.

Keywords: k-Splittable flow; Randomized rounding; Multicommodity flow (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11235-016-0190-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:telsys:v:64:y:2017:i:3:d:10.1007_s11235-016-0190-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/11235

DOI: 10.1007/s11235-016-0190-2

Access Statistics for this article

Telecommunication Systems: Modelling, Analysis, Design and Management is currently edited by Muhammad Khan

More articles in Telecommunication Systems: Modelling, Analysis, Design and Management from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().