|Name||Prof. Dr. Laurent Vanbever|
Inst. f. Techn. Informatik u. K.
ETH Zürich, ETZ G 90
|Telephone||+41 44 632 70 04|
|Department||Information Technology and Electrical Engineering|
|227-0102-00L||Discrete Event Systems||6 credits||4G||L. Thiele, L. Vanbever, R. Wattenhofer|
|Abstract||Introduction to discrete event systems. We start out by studying popular models of discrete event systems. In the second part of the course we analyze discrete event systems from an average-case and from a worst-case perspective. Topics include: Automata and Languages, Specification Models, Stochastic Discrete Event Systems, Worst-Case Event Systems, Verification, Network Calculus.|
|Objective||Over the past few decades the rapid evolution of computing, communication, and information technologies has brought about the proliferation of new dynamic systems. A significant part of activity in these systems is governed by operational rules designed by humans. The dynamics of these systems are characterized by asynchronous occurrences of discrete events, some controlled (e.g. hitting a keyboard key, sending a message), some not (e.g. spontaneous failure, packet loss). |
The mathematical arsenal centered around differential equations that has been employed in systems engineering to model and study processes governed by the laws of nature is often inadequate or inappropriate for discrete event systems. The challenge is to develop new modeling frameworks, analysis techniques, design tools, testing methods, and optimization processes for this new generation of systems.
In this lecture we give an introduction to discrete event systems. We start out the course by studying popular models of discrete event systems, such as automata and Petri nets. In the second part of the course we analyze discrete event systems. We first examine discrete event systems from an average-case perspective: we model discrete events as stochastic processes, and then apply Markov chains and queuing theory for an understanding of the typical behavior of a system. In the last part of the course we analyze discrete event systems from a worst-case perspective using the theory of online algorithms and adversarial queuing.
2. Automata and Languages
3. Smarter Automata
4. Specification Models
5. Stochastic Discrete Event Systems
6. Worst-Case Event Systems
7. Network Calculus
|Literature||[bertsekas] Data Networks |
Dimitri Bersekas, Robert Gallager
Prentice Hall, 1991, ISBN: 0132009161
[borodin] Online Computation and Competitive Analysis
Allan Borodin, Ran El-Yaniv.
Cambridge University Press, 1998
[boudec] Network Calculus
J.-Y. Le Boudec, P. Thiran
[cassandras] Introduction to Discrete Event Systems
Christos Cassandras, Stéphane Lafortune.
Kluwer Academic Publishers, 1999, ISBN 0-7923-8609-4
[fiat] Online Algorithms: The State of the Art
A. Fiat and G. Woeginger
[hochbaum] Approximation Algorithms for NP-hard Problems (Chapter 13 by S. Irani, A. Karlin)
[schickinger] Diskrete Strukturen (Band 2: Wahrscheinlichkeitstheorie und Statistik)
T. Schickinger, A. Steger
Springer, Berlin, 2001
[sipser] Introduction to the Theory of Computation
PWS Publishing Company, 1996, ISBN 053494728X
|227-0575-00L||Advanced Topics in Communication Networks (Autumn 2018)||6 credits||2V + 2U||L. Vanbever|
|Abstract||This class will introduce students to advanced, research-level topics in the area of communication networks, both theoretically and practically. Coverage will vary from semester to semester. Repetition for credit is possible, upon consent of the instructor. During the Fall Semester of 2018, the class will concentrate on network programmability and network data plane programming.|
|Objective||The goal of this lecture is to introduce students to the latest advances in the area of computer networks, both theoretically and practically. The course will be divided in two main blocks. The first block (~7 weeks) will interleave classical lectures with practical exercises and paper readings. The second block (~6 weeks) will consist of a practical project involving real network hardware and which will be performed in small groups (~3 students). During the second block, lecture slots will be replaced by feedback sessions where students will be able to ask questions and get feedback about their project. The last week of the semester will be dedicated to student presentations and demonstrations.|
During the Fall Semester 2018, the class will focus on programmable network data planes and will involve developing network applications on top of the the latest generation of programmable network hardware: Barefoot Network’s Tofino switch ASICs. By leveraging data-plane programmability, these applications can build deep traffic insights to, for instance, detect traffic anomalies (e.g. using Machine Learning), flexibly adapt forwarding behaviors (to improve performance), speed-up distributed applications (e.g. Map Reduce), or track network-wide health. More importantly, all this can now be done at line-rate, at forwarding speeds that can reach Terabits per second.
|Content||Traditionally, computer networks have been composed of "closed" network devices (routers, switches, middleboxes) whose features, forwarding behaviors and configuration interfaces are exclusively defined on a per-vendor basis. Innovating in such networks is a slow-paced process (if at all possible): it often takes years for new features to make it to mainstream network equipments. Worse yet, managing the network is hard and prone to failures as operators have to painstakingly coordinate the behavior of heterogeneous network devices so that they, collectively, compute a compatible forwarding state. Actually, it has been shown that the majority of the network downtimes are caused by humans, not equipment failures.|
Network programmability and Software-Defined Networking (SDN) have recently emerged as a way to fundamentally change the way we build, innovate, and operate computer networks, both at the software *and* at the hardware level. Specifically, programmable networks now allow: (i) to adapt how traffic flows in the entire network through standardized software interfaces; and (ii) to reprogram the hardware pipeline of the network devices, i.e. the ASICs used to forward data packets.
This year, the course will focus on reprogrammable network hardware/ASICs. It will involve hands-on experience on the world's fastest programmable switch to date (i.e. Barefoot Tofino switch ASIC).
Among others, we'll cover the following topics:
- The fundamentals and motivation behind network programmability;
- The design and optimization of network control loops;
- The use of advanced network data structures adapted for in-network execution;
- The P4 programming language and associated runtime environment;
- Hands-on examples of in-network applications solving hard problems in the area of data-centers, wide-area networks, and ISP networks.
The course will be divided in two blocks of 7 weeks. The first block will consist in traditional lectures introducing the concepts along with practical exercises to get acquainted with programmable data planes. The second block will consist of a (mandatory) project to be done in groups of few students (~3 students). The project will involve developing a fully working network application and run it on top of real programmable network hardware. Students will be free to propose their own application or pick one from a list. At the end of the course, each group will present its application in front of the class.
|Lecture notes||Lecture notes and material will be made available before each course on the course website.|
|Literature||Relevant references will be made available through the course website.|
|Prerequisites / Notice||Prerequisites: Communication Networks (227-0120-00L) or equivalents / good programming skills (in any language) are expected as both the exercices and the final project will involve coding.|