DROPS

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.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}
}

Search Results

Documents authored by Bankhamer, Gregor

Randomized Local Fast Rerouting for Datacenter Networks with Almost Optimal Congestion

Abstract

Cite as

Thanks for your feedback!

Could not send message