Self-Adjusting Networks:
A Short Video Course

The goal of this course is to provide a short introduction into self-adjusting networks. After a technical and empirical motivation, we present models, give insights into the underlying algorithmic problems, propose metrics to measure structure in communication traffic, and then discuss applications in reconfigurable datacenter networks. The course targets students and researchers interested in this emerging area. Currently, the course consists of 7 videos, but it may be extended.


Introduction

Lecture 1

  • What a self-adjusting network is
  • The empirical motivation
  • The technological enablers
  • The relationship to coding and data-structures theory
  • Some challenges faced by self-adjusting networks

Download Slides: Lecture 1 – Introduction

References:

  • Chen Avin and Stefan Schmid. Toward demand-aware networking: A theory for self-adjusting networks. ACM SIGCOMM Computer Communication Review 48.5 (2019): 31-40.


Model and Taxonomy

Lecture 2

  • That there are different types of datacenter topologies
  • A first model for the design of static demand-aware networks
  • A first model for the design of dynamic demand-aware networks
  • The potential benefits of demand-aware networks
  • A taxonomy of the problem space

Download Slides: Lecture 2 – Model and Taxonomy

References:

  • Chen Avin and Stefan Schmid. Toward demand-aware networking: A theory for self-adjusting networks. ACM SIGCOMM Computer Communication Review 48.5 (2019): 31-40.
  • Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network designs of bounded degree. Distributed Computing 33.3 (2020): 311-325.
  • Chen Griner, et al. Cerberus: The power of choices in datacenter topology design-a throughput perspective. Proceedings of the ACM on Measurement and Analysis of Computing Systems 5.3 (2021): 1-33.


Demand-Aware Networks

Lecture 3

  • A first algorithm for demand-aware networks
  • Relationship to existing algorithmic problems
  • How route lengths are connected to entropy

Download Slides: Lecture 3 – Demand-Aware Networks

References:

  • Chen Avin and Stefan Schmid. Toward demand-aware networking: A theory for self-adjusting networks. ACM SIGCOMM Computer Communication Review 48.5 (2019): 31-40.
  • Avin, Chen, Kaushik Mondal, and Stefan Schmid. Demand-aware network designs of bounded degree. Distributed Computing 33.3-4 (2020): 311-325.
  • C. Avin, K. Mondal and S. Schmid. Demand-Aware Network Design With Minimal Congestion and Route Lengths. In IEEE/ACM Transactions on Networking, vol. 30, no. 4, pp. 1838-1848, Aug. 2022.


Trace Complexity

Lecture 4

  • That datacenter traffic features structure
  • The difference between temporal and spatial structure
  • An approach to systematically quantify such structures
  • What a complexity map is

Download Slides: Lecture 4 – Trace Complexity

References:

  • W. M. Mellette, R. Das, Y. Guo, R. McGuinness, A. C. Snoeren, and G. Porter. Expanding across time to deliver bandwidth efficiency and low latency. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 1–18, 2020.
  • Roy, H. Zeng, J. Bagga, G. Porter, and A. C. Snoeren. Inside the social network’s (datacenter) network. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, pages 123–137, 2015.
  • M. Ghobadi, R. Mahajan, A. Phanishayee, N. Devanur, J. Kulkarni, G. Ranade, P.-A. Blanche, H. Raste- garfar, M. Glick, and D. Kilper. Projector: Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference, pages 216–229, 2016.
  • C. Avin, M. Ghobadi, C. Griner, and S. Schmid. On the complexity of traffic traces and implications. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1–29, 2020.


Self-Adjusting Networks

Lecture 5

  • A first approach to design self-adjusting networks
  • How a splay tree works
  • Ego-trees and Pushdown Trees
  • What a SplayNet is

Download Slides: Lecture 5 – Self-Adjusting Networks

References:

  • Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary search trees. Journal of the ACM (JACM) 32.3 (1985): 652-686.
  • Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. SplayNet: Towards Locally Self-Adjusting Networks. IEEE/ACM Transactions on Networking (TON), Volume 24, Issue 3, 2016.
  • Chen Avin and Stefan Schmid. ReNets: Statically-Optimal Demand-Aware Networks. SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), Alexandria, Virginia, USA, January 2021.


Dynamic Datacenter Topologies

Lecture 6

  • What traffic and topology types exist
  • What is a bandwidth tax and what a delay tax
  • Why a mismatch between traffic and topology is harmful
  • How throughput can be defined in dynamic networks
  • How to optimally match traffic to topology components
´´

Download Slides: Lecture 6 – Dynamic Datacenter Topologies

References:

  • W. M. Mellette, R. Das, Y. Guo, R. McGuinness, A. C. Snoeren, and G. Porter. Expanding across time to deliver bandwidth efficiency and low latency. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 1–18, 2020.
  • M. Ghobadi, R. Mahajan, A. Phanishayee, N. Devanur, J. Kulkarni, G. Ranade, P.-A. Blanche, H. Raste- garfar, M. Glick, and D. Kilper. Projector: Agile reconfigurable data center interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference, pages 216–229, 2016.
  • C. Avin, M. Ghobadi, C. Griner, and S. Schmid. On the complexity of traffic traces and implications. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1–29, 2020.
  • C. Griner, J. Zerwas, A. Blenk, M. Ghobadi, S. Schmid, and C. Avin, Cerberus: The power of choices in datacenter topology design-a throughput perspective. In Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 5, no. 3, pp. 1–33, 2021.
  • P. Namyar, S. Supittayapornpong, M. Zhang, M. Yu, and R. Govindan, A throughput-centric view of the performance of datacenter topologies. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, pp. 349–369, 2021.
  • W. M. Mellette, R. McGuinness, A. Roy, A. Forencich, G. Papen, A. C. Snoeren, and G. Porter. Ro- tornet: A scalable, low-complexity, optical datacenter network. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, pp. 267–280, 2017.
  • S. A. Jyothi, A. Singla, P. B. Godfrey, and A. Kolla. Measuring and understanding throughput of network topologies. In SC’16: Proceedings of the International Conference for High Performance Com- puting, Networking, Storage and Analysis, pp. 761–772, IEEE, 2016.
  • A. Valadarsky, G. Shahaf, M. Dinitz, and M. Schapira. Xpander: Towards optimal-performance data-centers. In Proceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies, pp. 205–219, 2016.
  • H. Ballani, P. Costa, R. Behrendt, D. Cletheroe, I. Haller, K. Jozwik, F. Karinou, S. Lange, K. Shi, B. Thomsen, et al. Sirius: A flat datacenter network with nanosecond optical switching. In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication, pp. 782–797, 2020.