Search Results

Documents authored by Gurtov, Andrei

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}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact