Search Results

Documents authored by Salem, Iosif

Document
DOI: 10.4230/LIPIcs.ESA.2024.52
Toward Self-Adjusting k-Ary Search Tree Networks

Authors: Evgeniy Feder, Anton Paramonov, Pavel Mavrin, Iosif Salem, Vitaly Aksenov, and Stefan Schmid

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Datacenter networks are becoming increasingly flexible with the incorporation of new optical communication technologies, such as optical circuit switches, enabling self-adjusting topologies that can adapt to the traffic pattern in a demand-aware manner. In this paper, we take the first steps toward demand-aware and self-adjusting k-ary tree networks. These are more powerful generalizations of existing binary search tree networks (like SplayNet [Stefan Schmid et al., 2016]), which have been at the core of self-adjusting network (SAN) designs. k-ary search tree networks are a natural generalization offering nodes of higher degrees, reduced route lengths, and local routing in spite of reconfigurations (due to maintaining the search property). Our main results are two online heuristics for self-adjusting k-ary tree networks. Empirical results show that our heuristics work better than SplayNet in most of the real network traces and for average to low locality synthetic traces, and are only a little inferior to SplayNet in all remaining traces. We build our online algorithms by first solving the offline case. First, we compute an offline (optimal) static demand-aware network for arbitrary traffic patterns in 𝒪(n³ ⋅ k) time via dynamic programming, where n is the number of network nodes (e.g., datacenter racks), and also improve the bound for the special case of uniformly distributed traffic. Then, we present a centroid-based approach to demand-aware network designs that we use both in the offline static and online settings. In the offline uniform-workload case, we construct this centroid network in linear time 𝒪(n).
Cite as

Evgeniy Feder, Anton Paramonov, Pavel Mavrin, Iosif Salem, Vitaly Aksenov, and Stefan Schmid. Toward Self-Adjusting k-Ary Search Tree Networks. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feder_et_al:LIPIcs.ESA.2024.52,
  author =	{Feder, Evgeniy and Paramonov, Anton and Mavrin, Pavel and Salem, Iosif and Aksenov, Vitaly and Schmid, Stefan},
  title =	{{Toward Self-Adjusting k-Ary Search Tree Networks}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.52},
  URN =		{urn:nbn:de:0030-drops-211235},
  doi =		{10.4230/LIPIcs.ESA.2024.52},
  annote =	{Keywords: self-adjusting networks, networks, splay-tree, k-ary tree}
}
Document
DOI: 10.4230/DagRep.12.11.96
Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471)

Authors: Artur Hecker, Stefan Schmid, Henning Schulzrinne, Lily Hügerich, Sándor Laki, and Iosif Salem

Published in: Dagstuhl Reports, Volume 12, Issue 11 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 22471 "Towards More Flexible and Automated Communication Networks". Communication network are becoming more and more automated, allowing to overcome human configuration errors (a frequent reason for outages) and enabling a more fine-grained control, potentially improving also efficiency. For example, the percentage of employees of Telecom companies "really touching the network" is decreasing. The goal of this seminar was to bring together experts in the field to identify and discuss the key challenges in making communication networks more autonomous. To this end, the seminar was structured around a small number of enlightning keynote talks, leaving significant time for breakout sessions and discussions, as well as socializing.
Cite as

Artur Hecker, Stefan Schmid, Henning Schulzrinne, Lily Hügerich, Sándor Laki, and Iosif Salem. Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471). In Dagstuhl Reports, Volume 12, Issue 11, pp. 96-108, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{hecker_et_al:DagRep.12.11.96,
  author =	{Hecker, Artur and Schmid, Stefan and Schulzrinne, Henning and H\"{u}gerich, Lily and Laki, S\'{a}ndor and Salem, Iosif},
  title =	{{Towards More Flexible and Automated Communication Networks (Dagstuhl Seminar 22471)}},
  pages =	{96--108},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{12},
  number =	{11},
  editor =	{Hecker, Artur and Schmid, Stefan and Schulzrinne, Henning and H\"{u}gerich, Lily and Laki, S\'{a}ndor and Salem, Iosif},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.11.96},
  URN =		{urn:nbn:de:0030-drops-178379},
  doi =		{10.4230/DagRep.12.11.96},
  annote =	{Keywords: networking, communication technologies, automation, programmability, flexibility}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.35
Brief Announcement: On Self-Adjusting Skip List Networks

Authors: Chen Avin, Iosif Salem, and Stefan Schmid

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
This paper explores the design of dynamic network topologies which adjust to the workload they serve, in an online manner. Such self-adjusting networks (SANs) are enabled by emerging optical technologies, and can be found, e.g., in datacenters. SANs can be used to reduce routing costs by moving frequently communicating nodes topologically closer. This paper presents SANs which provide, for the first time, provable working set guarantees: the routing cost between node pairs is proportional to how recently these nodes communicated last time. Our SANs rely on skip lists (which serve as the topology) and provide additional interesting properties such as local routing.
Cite as

Chen Avin, Iosif Salem, and Stefan Schmid. Brief Announcement: On Self-Adjusting Skip List Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 35:1-35:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{avin_et_al:LIPIcs.DISC.2019.35,
  author =	{Avin, Chen and Salem, Iosif and Schmid, Stefan},
  title =	{{Brief Announcement: On Self-Adjusting Skip List Networks}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{35:1--35:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.35},
  URN =		{urn:nbn:de:0030-drops-113423},
  doi =		{10.4230/LIPIcs.DISC.2019.35},
  annote =	{Keywords: self-adjusting networks, skip lists, working set, online algorithms}
}
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 About DROPS Imprint Privacy Contact