1 Search Results for "Bankhamer, Gregor"

Document
DOI: 10.4230/LIPIcs.DISC.2021.9
Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion

Authors: Gregor Bankhamer, Robert Elsässer, and Stefan Schmid

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
To ensure high availability, datacenter networks must rely on local fast rerouting mechanisms that allow routers to quickly react to link failures, in a fully decentralized manner. However, configuring these mechanisms to provide a high resilience against multiple failures while avoiding congestion along failover routes is algorithmically challenging, as the rerouting rules can only depend on local failure information and must be defined ahead of time. This paper presents a randomized local fast rerouting algorithm for Clos networks, the predominant datacenter topologies. Given a graph G = (V,E) describing a Clos topology, our algorithm defines local routing rules for each node v ∈ V, which only depend on the packet’s destination and are conditioned on the incident link failures. We prove that as long as number of failures at each node does not exceed a certain bound, our algorithm achieves an asymptotically minimal congestion up to polyloglog factors along failover paths. Our lower bounds are developed under some natural routing assumptions.
Cite as

Gregor Bankhamer, Robert Elsässer, and Stefan Schmid. Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bankhamer_et_al:LIPIcs.DISC.2021.9,
  author =	{Bankhamer, Gregor and Els\"{a}sser, Robert and Schmid, Stefan},
  title =	{{Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.9},
  URN =		{urn:nbn:de:0030-drops-148117},
  doi =		{10.4230/LIPIcs.DISC.2021.9},
  annote =	{Keywords: local failover routing, congestion, randomized algorithms, datacenter networks}
}
  • Refine by Author
  • 1 Bankhamer, Gregor
  • 1 Elsässer, Robert
  • 1 Schmid, Stefan

  • Refine by Classification
  • 1 Networks → Data path algorithms
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Distributed algorithms

  • Refine by Keyword
  • 1 congestion
  • 1 datacenter networks
  • 1 local failover routing
  • 1 randomized algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

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