Netzwerkkodierungstheorie
Sommersemester 2019
| Umfang: | 3 SWS (2/1/0) |
| Dozent: | Prof. Eduard Jorswieck |
| Lehrsprache: | deutsch |
| Abschluss: | schriftliche Prüfung über 120 Minuten |
| Einordnung: |
Bestandteil des Wahlpflichtmoduls Netzwerkkodierung in Theorie und Praxis
|
Aktuelles
Die Termine für die Prüfung wurden zur Webseite hinzugefügt. Siehe Prüfung.
Die letzte Übung findet am Mittwoch, 26.06.2019 von 13:00-14:30 Uhr im FAL 07/08 statt.
Ort und Zeit
| Vorlesung | Di | 6. DS | BAR 106 | |
| Übung | Do | 5. DS | 2. Wo | BAR 213 |
Terminverschiebungen siehe Tabelle
Vorlesung
Wie viele fundamentale Konzepte basiert die Netzwerkcodierung auf einer einfachen Idee, welche sehr anschaulich im ausgezeichneten Artikel "Network Information Flow" von R. Ahlswede, N. Cai, S.-Y. R. Li und R. W. Yeung dargestellt wurde.
In der Netzwerkcodierung wird ein Vermischen der Daten an Netzwerkknoten erlaubt und begünstigt.
Der Empfänger beobachtet diese vermischten Pakete und kann aus ihnen seine eigenen Daten extrahieren.
Im Gegensatz zu traditionellen Arten des Netzwerkmanagements, die Kollisionen der Datenströme vermeiden, impliziert dieses elegante Resultat eine Vielzahl von überraschenden Ergebnissen.
Eine der interessantesten Anwendungen dieses Ansatzes besteht darin, Datenströme zufällig zu vermischen und so die Eigenschaften von "random coding"-Argumenten bei der Analyse von Netzwerken einzusetzen.
Netzwerkcodierung ist nicht nur ein neues und elegantes Werkzeug, welches das Potential besitzt, stagnierende fundamentale Forschungsbereiche wiederzubeleben, sondern es bietet eine gemeinsame Sichtweise auf vormals getrennte Bereiche.
Ein überzeugendes Beispiel für diese Art der Vereinheitlichung ist die Charakterisierung der Kapazität von Multicast-Netzwerken, die nur durch gemeinsame Behandlung von Codierung und Routing ermöglicht wurde.
Die Vorlesung ist Bestandteil des Moduls Netzwerkkodierung in Theorie und Praxis und ist eng mit der Vorlesung Praktische Anwendungen der Netzwerkkodierung verzahnt.
Während diese Vorlesung die theoretischen Grundlagen der Netzwerkcodierung behandelt, werden in der Vorlesung Praktische Anwendungen der Netzwerkkodierung aktuelle Anwendungen besprochen und im Rahmen der Übung auch selbst implementiert.
Nachdem Grundlagen aus der Graphentheorie und der traditionelle Ansatz der Paketweiterleitung in Netzwerken behandelt wurden, wird der Hauptsatz der Netzwerkcodierung bewiesen und anhand von verschiedenen Beispielen illustriert.
Der Ansatz der Teilbaumzerlegung sowie der algebraischen Netzwerkcodierung wird ebenso behandelt wie Alternativen zur Netzwerkcodierung auf der Übertragungsschicht.
Dabei wird sowohl die klassische Netzwerkcodierung im drahtgebunden Fall betrachtet als auch die Erweiterung auf den drahtlosen Fall.
Hier werden u. a. aktuelle Forschungsthemen wie Network Coded Modulation, Lattice Codes, Compute-and-Forward, Distributed Data Storage und Secure Network Coding vorgestellt und diskutiert.
Materialien zur Vorlesung
siehe Tabelle
Übung
Die Aufgabenblätter stehen rechtzeitig auf dieser Seite bereit.
Die Aufgabenblätter nach Möglichkeit bitte ausgedruckt zur Übung mitbringen.
Materialien zur Übung
siehe Tabelle
Termine
Die folgende Tabelle enthält alle Vorlesungs- und Übungstermine des Semesters sowie die Materialien zu Vorlesung und Übung.
| Woche | Datum | DS | Vorlesung | Übung | Bemerkung / Material |
|---|---|---|---|---|---|
| 14 | 02.04.2019 | 6. | X | Folien | |
| 15 | 09.04.2019 | 6. | X | Folien | |
| 16 | 16.04.2019 | 6. | X | Folien | |
| 17 | 23.04.2019 | 6. | X | Folien | |
| 18 | 30.04.2019 | 6. | X | Folien | |
| 19 | 07.05.2019 | 6. | X | Folien | |
| 20 | 14.05.2019 | 6. | − | fällt aus | |
| 21 | 21.05.2019 | 6. | − | fällt aus | |
| 22 | 28.05.2019 | 6. | X | Folien | |
| 23 | 04.06.2019 | 6. | X | Folien | |
| 24 | 11.06.2019 | 6. | − | Pfingstferien | |
| 25 | 18.06.2019 | 6. | X | Folien | |
| 26 | 25.06.2019 | 6. | - | Folien | |
| 27 | 02.07.2019 | 6. | X | Folien | |
| 28 | 09.07.2019 | 6. | − | fällt aus |
Prüfung
22.07.2019 von 10 bis 12 Uhr im BAR 218.
Zugelassene Hilfsmittel sind schriftliche Unterlagen aller Art sowie nicht-algebra-fähige Taschenrechner.
Literatur
Da die Netzwerkcodierung erst seit kurzer Zeit in der Forschung diskutiert wird, existieren (noch) keine Standardlehrbücher. Die Lehrveranstaltung basiert auf den folgenden Buchkapiteln und Monographien:
-
Raymond W. Yeung:
Information Theory and Network Coding,
Springer, 2008. -
Christina Fragouli und Emina Soljanin:
Network Coding Fundamentals,
Now publishers, Foundations and Trends in Networking, vol. 2, no. 1, 2007.
Das ist der Basis-Artikel von 2000:
-
Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li und Raymond W. Yeung:
Network Information Flow,
IEEE Transactions on Information Theory, vol. 46, no. 4, Juli 2000.
Elektronische Version hier verfügbar (Zugang nur innerhalb des TU-Netzes).
Bücher zu Lattices und Lattice Codes:
-
J. H. Conway und N. J. A. Sloane:
Sphere Packings, Lattices and Groups,
Springer, 1999. -
Ram Zamir:
Lattice Coding for Signals and Networks,
Cambrigde University Press, 2014.
Paper zu Anwendungen der Netzwerkcodierung:
-
Bobak Nazer und Michael Gastpar:
Compute-and-Forward: Harnessing Interference Through Structured Codes,
IEEE Transactions on Information Theory, vol. 57, no. 10, Oktober 2011,
Elektronische Version hier verfügbar (Zugang nur innerhalb des TU-Netzes). -
Alexandros G. Dimakis, P. Brighten Godfrey, Yunnan Wu, Martin J. Wainwright und Kannan Ramchandran:
Network Coding for Distributed Storage Systems,
IEEE Transactions on Information Theory, vol. 56, no. 9, September 2010,
Elektronische Version hier verfügbar (Zugang nur innerhalb des TU-Netzes).
Kontakt
Kommentare zur Vorlesung oder Übung sowie Hinweise und Fragen zu den Aufgaben bitte an:
Prof. Eduard Jorswieck