Inhalt des Dokuments
Network Optimization by Randomization (Integrierte Veranstaltung, SoSe 2011)
Alle modernen Computer und drahtlosen Netze enthalten eine Zufallskomponente. Konkrete Anwendungen von Zufälligkeit gibt es zuhauf in verschiedenen Feldern wie Kommunikationsprotokollen, Netz-Sicherheit oder verteiltem Rechnen. Studierende, die dieses Modul nehmen, werden imstande sein
- eine Reihe allgemeiner Prinzipien zu verstehen, die dem Wesen der zufälligene Verteilungen bei der Entwicklung von Netzprotokollen zugrunde liegen, sowie
- die Vorteile der zufälligen Verteilungen, z.B. hinsichtlich Einfachheit, Effizienz oder schneller Durchlaufzeiten für die Netz-Optimierung.
Insbesondere werden die Studierenden in der Lage sein, bei der Entwicklung neuer Protokolle sinnvoll Zufallskomponenten in diese zu integrieren.
Die Vorlesung mischt grundlegende Elemente der Wahrscheinlichkeitsrechnung, die sich direkt auf praktische Probleme der Protokollentwicklung anwenden lassen, mit der Analyse. Die wichtigsten Themen der Veranstaltung werden sein (vorläufige Liste):
- Multiple Access Protocols
- Scheduling (e.g., backpressure, opportunistic, approximate)
- Flow & Congestion Control, Routing
- Resource Allocation (e.g., Energie, Bandbreite, CPU)
- Peer-to-Peer & Social Networks
- Online-Algorithmen
- Network Security
- Network Coding
- Network Reliability
Überblick
| Dozent/innen: | Anja Feldmann, Florin Ciucu ergänzend: Stefan Schmid |
| weiterer Ansprechpartner: | Oliver Hohlfeld |
| Veranstaltungstyp: | Integrierte Veranstaltung (Vorlesung mit Übung) |
| Gebiet: | Diplom-Informatik: Betriebs- und Kommunikationssysteme (BKS) Informatik (Master): Kommunikationsbasierte Systeme Technische Informatik (Master): Technische Anwendungen |
| Modul: | MINF-KT-NOR.S11 |
| SWS: | 4 |
| LP: | 6 |
| Zeit: | donnerstags, 12–16 Uhr wöchentlich |
| erster Termin: | 21. April 2011 |
| Raum: | FR 1067 |
| Hörerkreis: | Bachelor-Studierende nach dem Grundlagenstudium (ab dem fünften Semester), Master-Studierende und Diplom-Studierende |
| Voraussetzungen: |
|
| Prüfung: | schriftlich. Weitere Informationen werden noch bekannt gegeben. |
| Weitere Informationen: | s. ISIS |
Anmeldung
Falls du an der Vorlesung teilnehmen willst, trag dich bitte auf der zugehörigen ISIS-Seite ein, um wichtige Informationen und Ankündigungen zu erhalten.
Für Master-Studierende ist außerdem eine Modulanmeldung erforderlich. Weitere Informationen dazu werden in der Vorlesung und via ISIS bekannt gegeben.
Hausaufgaben
Es wird eine Übung im Rahmen der Veranstaltung angeboten. Zum Bestehen der Übungen sind mind. 50% der maximal erreichbaren Punkte notwendig.
Vorlesungsfolien
- Network Optimization by Randomization: Lecture 01 PDF, 194 KB
- Network Optimization by Randomization: Lecture 02 & 03 PDF, 3 MB
- Network Optimization by Randomization: Lecture 04 PDF, 2 MB
- Network Optimization by Randomization: Lecture 05 PDF, 2 MB
- Network Optimization by Randomization: Lecture 06 PDF, 3 MB
- Network Optimization by Randomization: Lecture 07 PDF, 708 KB
- Network Optimization by Randomization: Lecture 08 PDF, 560 KB
- Network Optimization by Randomization: Lecture 09 PDF, 773 KB
Hausaufgaben
- NOR: Homework 1 (due: 28 April '11) PDF, 25 KB
- NOR: Homework 2 (due: 12 May '11) PDF, 24 KB
- NOR: Homework 3 (due: 19 May '11) PDF, 23 KB
- NOR: Homework 4 (due: 26 May '11) PDF, 23 KB
- NOR: Homework 5 (due: 28 June '11) PDF, 22 KB
- NOR: Homework 6 (due: 30 Juni '11) PDF, 54 KB
Einige Lösungen
- NOR HW 6: Presentation of the solution PDF, 379 KB
- NOR HW 6: Solution PDF, 84 KB
Literatur
- M.J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool, 2010 (english)
- Michael Mitzenmacher and Eli Upfal. Probability and Computing. Cambridge University Press, 2005 (english)
- David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, USA, 2000. (english)
- Juraj Hromkovic, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger. Dissemination of Information in Communication Networks. Springer. 2005 (english)
- Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction to Algorithms. The MIT Press, 1998 (english)
- J. Kleinberg. Navigation in a Small World. Nature, Volume 406(2000), 845 (pdf)
