4 Search Results for "Gurtov, Andrei"

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.31
Fast Re-Routing in Networks: On the Complexity of Perfect Resilience

Authors: Matthias Bentert, Esra Ceylan, Valentin Hübner, Stefan Schmid, and Jiří Srba

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
To achieve fast recovery from link failures, most modern communication networks feature fully decentralized fast re-routing mechanisms. These re-routing mechanisms rely on pre-installed static re-routing rules at the nodes (the routers), which depend only on local failure information, namely on the failed links incident to the node. Ideally, a network is perfectly resilient: the re-routing rules ensure that packets are always successfully routed to their destinations as long as the source and the destination are still physically connected in the underlying network after the failures. Unfortunately, there are examples where achieving perfect resilience is not possible. Surprisingly, only very little is known about the algorithmic aspect of when and how perfect resilience can be achieved. We investigate the computational complexity of analyzing such local fast re-routing mechanisms. Our main result is a negative one: we show that even checking whether a given set of static re-routing rules ensures perfect resilience is coNP-complete. Additionally, we investigate other fundamental variations of the problem. In particular, we show that our coNP-completeness proof also applies to scenarios where the re-routing rules have specific patterns (known as skipping in the literature). On the positive side, for scenarios where nodes do not have information about the link from which a packet arrived (the so-called in-port), we present a linear-time algorithm to realize perfect resilience whenever possible (which we show can also be determined in linear time).
Cite as

Matthias Bentert, Esra Ceylan, Valentin Hübner, Stefan Schmid, and Jiří Srba. Fast Re-Routing in Networks: On the Complexity of Perfect Resilience. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.OPODIS.2025.31,
  author =	{Bentert, Matthias and Ceylan, Esra and H\"{u}bner, Valentin and Schmid, Stefan and Srba, Ji\v{r}{\'\i}},
  title =	{{Fast Re-Routing in Networks: On the Complexity of Perfect Resilience}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.31},
  URN =		{urn:nbn:de:0030-drops-252040},
  doi =		{10.4230/LIPIcs.OPODIS.2025.31},
  annote =	{Keywords: routing in computer networks, fast re-route, perfect resilience, complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.134
On the Resiliency of Randomized Routing Against Multiple Edge Failures

Authors: Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Shapira, and Scott Shenker

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
We study the Static-Routing-Resiliency problem, motivated by routing on the Internet: Given a graph G = (V,E), a unique destination vertex d, and an integer constant c > 0, does there exist a static and destination-based routing scheme such that the correct delivery of packets from any source s to the destination d is guaranteed so long as (1) no more than c edges fail and (2) there exists a physical path from s to d? We embark upon a study of this problem by relating the edge-connectivity of a graph, i.e., the minimum number of edges whose deletion partitions G, to its resiliency. Following the success of randomized routing algorithms in dealing with a variety of problems (e.g., Valiant load balancing in the network design problem), we embark upon a study of randomized routing algorithms for the Static-Routing-Resiliency problem. For any k-connected graph, we show a surprisingly simple randomized algorithm that has expected number of hops O(|V|k) if at most k-1 edges fail, which reduces to O(|V|) if only a fraction t of the links fail (where t < 1 is a constant). Furthermore, our algorithm is deterministic if the routing does not encounter any failed link.
Cite as

Marco Chiesa, Andrei Gurtov, Aleksander Madry, Slobodan Mitrovic, Ilya Nikolaevskiy, Michael Shapira, and Scott Shenker. On the Resiliency of Randomized Routing Against Multiple Edge Failures. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 134:1-134:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chiesa_et_al:LIPIcs.ICALP.2016.134,
  author =	{Chiesa, Marco and Gurtov, Andrei and Madry, Aleksander and Mitrovic, Slobodan and Nikolaevskiy, Ilya and Shapira, Michael and Shenker, Scott},
  title =	{{On the Resiliency of Randomized Routing Against Multiple Edge Failures}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{134:1--134:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.134},
  URN =		{urn:nbn:de:0030-drops-62692},
  doi =		{10.4230/LIPIcs.ICALP.2016.134},
  annote =	{Keywords: Randomized, Routing, Resilience, Connectivity, Arborescenses}
}
Document
DOI: 10.4230/DagSemProc.06441.1
06441 Abstracts Collection – Naming and Addressing for Next Generation Internetworks

Authors: Bengt Ahlgren, Lars Eggert, Anja Feldmann, Andrei Gurtov, and Thomas Henderson

Published in: Dagstuhl Seminar Proceedings, Volume 6441, Naming and Addressing for Next-Generation Internetworks (2007)

Abstract
From 29.10.06 to 01.11.06, the Dagstuhl Seminar 06441``Naming and Addressing for Next-Generation Internetworks'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Bengt Ahlgren, Lars Eggert, Anja Feldmann, Andrei Gurtov, and Thomas Henderson. 06441 Abstracts Collection – Naming and Addressing for Next Generation Internetworks. In Naming and Addressing for Next-Generation Internetworks. Dagstuhl Seminar Proceedings, Volume 6441, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{ahlgren_et_al:DagSemProc.06441.1,
  author =	{Ahlgren, Bengt and Eggert, Lars and Feldmann, Anja and Gurtov, Andrei and Henderson, Thomas},
  title =	{{06441 Abstracts Collection – Naming and Addressing for Next Generation Internetworks}},
  booktitle =	{Naming and Addressing for Next-Generation Internetworks},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6441},
  editor =	{Bengt Ahlgren and Lars Eggert and Anja Feldmann and Andrei Gurtov and Tom R. Henderson},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06441.1},
  URN =		{urn:nbn:de:0030-drops-11309},
  doi =		{10.4230/DagSemProc.06441.1},
  annote =	{Keywords: Naming, addressing, network architecture, next-generation networks, security, privacy}
}
Document
DOI: 10.4230/DagSemProc.06441.2
06441 Summary – Naming and Addressing for Next Generation Internetworks

Authors: Thomas Henderson, Andrei Gurtov, Lars Eggert, and Christian Dannewitz

Published in: Dagstuhl Seminar Proceedings, Volume 6441, Naming and Addressing for Next-Generation Internetworks (2007)

Abstract
The design of naming and addressing for data networks is a fundamental architectural consideration, and several current or anticipated problems in the Internet – including mobility dynamics, forwarding table growth in the core routers, and security – point out possible limitations with naming and addressing schemes in use today. A seminar on the topic of naming and addressing for next generation internetworks was held at the Schloß Dagstuhl from October 29 to November 1, 2006. Researchers from different fields discussed their views and recent results pertaining to naming and addressing problems. Over twenty talks covered topics such as routing, naming components, APIs, mobility, delay-tolerant architectures, flat routing and deployment issues. This article briefly summarizes the seminar presentations and discussions.
Cite as

Thomas Henderson, Andrei Gurtov, Lars Eggert, and Christian Dannewitz. 06441 Summary – Naming and Addressing for Next Generation Internetworks. In Naming and Addressing for Next-Generation Internetworks. Dagstuhl Seminar Proceedings, Volume 6441, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{henderson_et_al:DagSemProc.06441.2,
  author =	{Henderson, Thomas and Gurtov, Andrei and Eggert, Lars and Dannewitz, Christian},
  title =	{{06441 Summary – Naming and Addressing for Next Generation Internetworks}},
  booktitle =	{Naming and Addressing for Next-Generation Internetworks},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6441},
  editor =	{Bengt Ahlgren and Lars Eggert and Anja Feldmann and Andrei Gurtov and Tom R. Henderson},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06441.2},
  URN =		{urn:nbn:de:0030-drops-11293},
  doi =		{10.4230/DagSemProc.06441.2},
  annote =	{Keywords: Network architecture, scalability, mobility, heterogeneity, extensibility, naming, addressing}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2016
  • 2 2007

  • Refine by Author
  • 3 Gurtov, Andrei
  • 2 Eggert, Lars
  • 2 Henderson, Thomas
  • 1 Ahlgren, Bengt
  • 1 Bentert, Matthias
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 DagSemProc

  • Refine by Classification
  • 1 Networks → Network properties
  • 1 Networks → Network protocol design
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 addressing
  • 1 Arborescenses
  • 1 Connectivity
  • 1 Naming
  • 1 Network architecture
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact