Brief Announcement: Toward Self-Adjusting Networks for the Matching Model

Evgeniy Feder, Ichha Rathod, Punit Shyamsukha, Robert Sama, Vitaly Aksenov, Iosif Salem, Stefan Schmid

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed


Self-adjusting networks (SANs) utilize novel optical switching technologies to support dynamic physical network topology reconfiguration. SANs rely on online algorithms to exploit this topological flexibility to reduce the cost of serving network traffic, leveraging locality in the demand. Models in prior work assign uniform cost for traversing and adjusting a single link (e.g. both cost 1). In this paper, we initiate the study of online algorithms for SANs in a more realistic cost model, the Matching Model (MM), in which the network topology is given by the union of a constant number of bipartite matchings (realized by optical switches), and in which changing an entire matching incurs a fixed cost a. The cost of routing is given by the number of hops packets need to traverse. We present online SAN algorithms in the MM with cost O(sqrt(a)) times the cost of reference algorithms in the uniform cost model.
TitelSPAA '21: Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
ErscheinungsortNew York, NY
Herausgeber (Verlag)ACM
ISBN (elektronisch)978-1-4503-8070-6
PublikationsstatusVeröffentlicht - 1 Juli 2021


ReiheSymposium on Parallelism in Algorithms and Architectures : Proceedings of the ... ACM symposium on Parallelism in algorithms and architectures

ÖFOS 2012

  • 102025 Verteilte Systeme