Document Open Access Logo

Rerouting Flows When Links Fail

Authors Jannik Matuschke, S. Thomas McCormick, Gianpaolo Oriolo



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.89.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Jannik Matuschke
S. Thomas McCormick
Gianpaolo Oriolo

Cite AsGet BibTex

Jannik Matuschke, S. Thomas McCormick, and Gianpaolo Oriolo. Rerouting Flows When Links Fail. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 89:1-89:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.89

Abstract

We introduce and investigate reroutable flows, a robust version of network flows in which link failures can be mitigated by rerouting the affected flow. Given a capacitated network, a path flow is reroutable if after failure of an arbitrary arc, we can reroute the interrupted flow from the tail of that arc to the sink, without modifying the flow that is not affected by the failure. Similar types of restoration, which are often termed "local", were previously investigated in the context of network design, such as min-cost capacity planning. In this paper, our interest is in computing maximum flows under this robustness assumption. An important new feature of our model, distinguishing it from existing max robust flow models, is that no flow can get lost in the network. We also study a tightening of reroutable flows, called strictly reroutable flows, making more restrictive assumptions on the capacities available for rerouting. For both variants, we devise a reroutable-flow equivalent of an s-t-cut and show that the corresponding max flow/min cut gap is bounded by 2. It turns out that a strictly reroutable flow of maximum value can be found using a compact LP formulation, whereas the problem of finding a maximum reroutable flow is NP-hard, even when all capacities are in {1, 2}. However, the tightening can be used to get a 2-approximation for reroutable flows. This ratio is tight in general networks, but we show that in the case of unit capacities, every reroutable flow can be transformed into a strictly reroutable flow of same value. While it is NP-hard to compute a maximal integral flow even for unit capacities, we devise a surprisingly simple combinatorial algorithm that finds a half-integral strictly reroutable flow of value 1, or certifies that no such solutions exits. Finally, we also give a hardness result for the case of multiple arc failures.
Keywords
  • network flows
  • network interdiction
  • robust optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. David Adjiashvili, Gianpaolo Oriolo, and Marco Senatore. The online replacement path problem. In Algorithms - ESA 2013, volume 8125 of Lecture Notes in Computer Science, pages 1-12. Springer, 2013. Google Scholar
  2. Charu C. Aggarwal and James B. Orlin. On multiroute maximum flows in networks. Networks, 39(1):43-52, 2002. Google Scholar
  3. Y. P. Aneja, R. Chandrasekaran, and K. P. K. Nair. Maximizing residual flow under an arc destruction. Networks, 38(4):194-198, 2001. Google Scholar
  4. Dimitris Bertsimas, Ebrahim Nasrabadi, and James B. Orlin. On the power of randomization in network interdiction. Operations Research Letters, 44(1):114-120, 2016. Google Scholar
  5. Dimitris Bertsimas, Ebrahim Nasrabadi, and Sebastian Stiller. Robust and adaptive network flows. Operations Research, 61:1218-1242, 2013. Google Scholar
  6. Graham Brightwell, Gianpaolo Oriolo, and F. Bruce Shepherd. Reserving resilient capacity in a network. SIAM Journal on Discrete Mathematics, 14(4):524-539, 2001. Google Scholar
  7. Chandra Chekuri, Anupam Gupta, Amit Kumar, Joseph Naor, and Danny Raz. Building edge-failure resilient networks. Algorithmica, 43(1-2):17-41, 2005. Google Scholar
  8. Stephen R. Chestnut and Rico Zenklusen. Hardness and approximation for network flow interdiction. Networks, 2017. Google Scholar
  9. Amaro de Sousa and Gil Soares. Improving load balance and minimizing service disruption on ethernet networks with IEEE 802.1 S MSTP. In Workshop on IP QoS and Traffic Control, pages 25-35, 2007. Google Scholar
  10. Yann Disser and Jannik Matuschke. The complexity of computing a robust flow, 2017. Google Scholar
  11. Lester R. Ford and Delbert R. Fulkerson. Flows in networks. Princeton Univ. Press, 1962. Google Scholar
  12. Harold N. Gabow, Shachindra N. Maheshwari, and Leon J. Osterweil. On two problems in the generation of program test paths. IEEE Transactions on Software Engineering, SE-2(3):227-231, 1976. Google Scholar
  13. Fabrizio Grandoni, Gaia Nicosia, Gianpaolo Oriolo, and Laura Sanità. Stable routing under the spanning tree protocol. Operations Research Letters, 38(5):399-404, 2010. Google Scholar
  14. Alan J. Hoffman. A generalization of max flow - min cut. Mathematical Programming, 6(1):352-359, 1974. Google Scholar
  15. Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM, 46(6):787-832, 1999. Google Scholar
  16. Robert M. Metcalfe and David R. Boggs. Ethernet: Distributed packet switching for local computer networks. Communications of the ACM, 19(7):395-404, 1976. Google Scholar
  17. Steven J. Phillips and Jeffery R. Westbrook. Approximation algorithms for restoration capacity planning. In Algorithms - ESA'99, volume 1643 of Lecture Notes in Computer Science, pages 101-115. Springer, 1999. Google Scholar
  18. F. Bruce Shepherd. Single-sink multicommodity flow with side constraints. In Research Trends in Combinatorial Optimization, pages 429-450. Springer, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail