Search Results

Documents authored by Foerster, Klaus-Tycho

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.25
Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks

Authors: Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
The performance of distributed and data-centric applications often critically depends on the interconnecting network. Emerging reconfigurable datacenter networks (RDCNs) are a particularly innovative approach to improve datacenter throughput. Relying on a dynamic optical topology which can be adjusted towards the workload in a demand-aware manner, RDCNs allow to exploit temporal and spatial locality in the communication pattern, and to provide topological shortcuts for frequently communicating racks. The key challenge, however, concerns how to realize demand-awareness in RDCNs in a scalable fashion. This paper presents and evaluates Chopin, a hybrid scheduler for self-adjusting networks that provides demand-awareness at low overhead, by combining centralized and distributed approaches. Chopin allocates optical circuits to elephant flows, through its slower centralized scheduler, utilizing global information. Chopin’s distributed scheduler is orders of magnitude faster and can swiftly react to changes in the traffic and adjust the optical circuits accordingly, by using only local information and running at each rack separately.
Cite as

Neta Rozen-Schiff, Klaus-Tycho Foerster, Stefan Schmid, and David Hay. Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rozenschiff_et_al:LIPIcs.OPODIS.2022.25,
  author =	{Rozen-Schiff, Neta and Foerster, Klaus-Tycho and Schmid, Stefan and Hay, David},
  title =	{{Chopin: Combining Distributed and Centralized Schedulers for Self-Adjusting Datacenter Networks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{25:1--25:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.25},
  URN =		{urn:nbn:de:0030-drops-176457},
  doi =		{10.4230/LIPIcs.OPODIS.2022.25},
  annote =	{Keywords: reconfigurable optical networks, centralized scheduler, distributed scheduler}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.42
Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies

Authors: Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Emerging reconfigurable optical communication technologies enable demand-aware networks: networks whose static topology can be enhanced with demand-aware links optimized towards the traffic pattern the network serves. This paper studies the algorithmic problem of how to jointly optimize the topology and the routing in such demand-aware networks, to minimize congestion. We investigate this problem along two dimensions: (1) whether flows are splittable or unsplittable, and (2) whether routing on the hybrid topology is segregated or not, i.e., whether or not flows either have to use exclusively either the static network or the demand-aware connections. For splittable and segregated routing, we show that the problem is 2-approximable in general, but APX-hard even for uniform demands induced by a bipartite demand graph. For unsplittable and segregated routing, we show an upper bound of O(log m/ log log m) and a lower bound of Ω(log m/ log log m) for polynomial-time approximation algorithms, where m is the number of static links. Under splittable (resp., unsplittable) and non-segregated routing, even for demands of a single source (resp., destination), the problem cannot be approximated better than Ω(c_{max}/c_{min}) unless P=NP, where c_{max} (resp., c_{min}) denotes the maximum (resp., minimum) capacity. It is still NP-hard for uniform capacities, but can be solved efficiently for a single commodity and uniform capacities.
Cite as

Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dai_et_al:LIPIcs.DISC.2022.42,
  author =	{Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan},
  title =	{{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{42:1--42:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.42},
  URN =		{urn:nbn:de:0030-drops-172330},
  doi =		{10.4230/LIPIcs.DISC.2022.42},
  annote =	{Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.26
Maximally Resilient Replacement Paths for a Family of Product Graphs

Authors: Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Modern communication networks support fast path restoration mechanisms which allow to reroute traffic in case of (possibly multiple) link failures, in a completely decentralized manner and without requiring global route reconvergence. However, devising resilient path restoration algorithms is challenging as these algorithms need to be inherently local. Furthermore, the resulting failover paths often have to fulfill additional requirements related to the policy and function implemented by the network, such as the traversal of certain waypoints (e.g., a firewall). This paper presents local algorithms which ensure a maximally resilient path restoration for a large family of product graphs, including the widely used tori and generalized hypercube topologies. Our algorithms provably ensure that even under multiple link failures, traffic is rerouted to the other endpoint of every failed link whenever possible (i.e. detouring failed links), enforcing waypoints and hence accounting for the network policy. The algorithms are particularly well-suited for emerging segment routing networks based on label stacks.
Cite as

Mahmoud Parham, Klaus-Tycho Foerster, Petar Kosic, and Stefan Schmid. Maximally Resilient Replacement Paths for a Family of Product Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{parham_et_al:LIPIcs.OPODIS.2020.26,
  author =	{Parham, Mahmoud and Foerster, Klaus-Tycho and Kosic, Petar and Schmid, Stefan},
  title =	{{Maximally Resilient Replacement Paths for a Family of Product Graphs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.26},
  URN =		{urn:nbn:de:0030-drops-135111},
  doi =		{10.4230/LIPIcs.OPODIS.2020.26},
  annote =	{Keywords: Product Graphs, Resilience, Failures, Routing}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.46
Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally

Authors: Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed [Feigenbaum and others, 2012] that it is not always possible to provide perfect resilience; on the positive side, the authors also presented an efficient algorithm which achieves at least 1-resilience, tolerating a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience. This brief announcement revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; On the positive side, we can derive perfect resilience for outerplanar and some planar graphs.
Cite as

Klaus-Tycho Foerster, Juho Hirvonen, Yvonne-Anne Pignolet, Stefan Schmid, and Gilles Tredan. Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.DISC.2020.46,
  author =	{Foerster, Klaus-Tycho and Hirvonen, Juho and Pignolet, Yvonne-Anne and Schmid, Stefan and Tredan, Gilles},
  title =	{{Brief Announcement: What Can(Not) Be Perfectly Rerouted Locally}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{46:1--46:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.46},
  URN =		{urn:nbn:de:0030-drops-131244},
  doi =		{10.4230/LIPIcs.DISC.2020.46},
  annote =	{Keywords: Resilience, Local Failover}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.13
Local Fast Segment Rerouting on Hypercubes

Authors: Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Fast rerouting is an essential mechanism in any dependable communication network, allowing to quickly, i.e., locally, recover from network failures, without invoking the control plane. However, while locality ensures a fast reaction, the absence of global information also renders the design of highly resilient fast rerouting algorithms more challenging. In this paper, we study algorithms for fast rerouting in emerging Segment Routing (SR) networks, where intermediate destinations can be added to packets by nodes along the path. Our main contribution is a maximally resilient polynomial-time fast rerouting algorithm for SR networks based on a hypercube topology. Our algorithm is attractive as it preserves the original paths (and hence waypoints traversed along the way), and does not require packets to carry failure information. We complement our results with an integer linear program formulation for general graphs and exploratory simulation results.
Cite as

Klaus-Tycho Foerster, Mahmoud Parham, Stefan Schmid, and Tao Wen. Local Fast Segment Rerouting on Hypercubes. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{foerster_et_al:LIPIcs.OPODIS.2018.13,
  author =	{Foerster, Klaus-Tycho and Parham, Mahmoud and Schmid, Stefan and Wen, Tao},
  title =	{{Local Fast Segment Rerouting on Hypercubes}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.13},
  URN =		{urn:nbn:de:0030-drops-100739},
  doi =		{10.4230/LIPIcs.OPODIS.2018.13},
  annote =	{Keywords: segment routing, local fast failover, link failures}
}
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