Stefan Dziwok (xell@upb.de) Institut für Informatik FG Rechnernetze Universität Paderborn Network...

Stefan Dziwok(xell@upb.de)

Institut für InformatikFG Rechnernetze

Universität Paderborn

Network CodingNetwork Coding

2

1.1. EinführungEinführung

2.2. Maximaler DurchsatzMaximaler Durchsatz

3.3. Network CodingNetwork Coding

4.4. Fazit und weitere ForschungFazit und weitere Forschung

GliederungGliederung

EinführungEinführung

Einführung Max-Durchsatz Network Coding Fazit

4

– Umgebung des Themas festlegen

– Definitionen kennen lernen und verstehen

– Beschreibung des Problems

– Lösungsansätze besprechen

Ziele des KapitelsZiele des Kapitels

Einführung Max-Durchsatz Network Coding Fazit

5

Die UmgebungDie Umgebung

– Netz von Computern

– Verbunden über Leitungen

– Funktion: Daten senden von grünem PC zu den gelben PCs

Einführung Max-Durchsatz Network Coding Fazit

6

Abstrahierung der UmgebungAbstrahierung der Umgebung

– Netz von Knoten

– Verbunden über Kanten

– Funktion:Daten senden von Quelle S nach mehreren Senken T

Der Butterfly

Einführung Max-Durchsatz Network Coding Fazit

7

MulticastingMulticasting

– Gleichzeitiges Senden eines Bits von der Quelle S zu n Senken T

Redundanz

– Hier: Spezialfall

n = alle Senken

Bit_1Bit_1

Bit_1Bit_1 Bit_1Bit_1

Einführung Max-Durchsatz Network Coding Fazit

8

Kapazität KKapazität K

– Maximale Anzahl der versendbaren Bits je Kante je Zeiteinheit (z.B.: Bit/s)

– Hier: Spezialfall

Alle Kanten haben K = 1 Bit / Zeiteinheit

Einführung Max-Durchsatz Network Coding Fazit

9

Durchsatz DDurchsatz D

– Anzahl der gesendeten Bits je Zeiteinheit (z.B.: Bits/s)

– D bestimmt wieviele unterschiedliche Bits von S gesendet werden können, die auch alle bei jedem T ankommen

Einführung Max-Durchsatz Network Coding Fazit

Bit_1Bit_1 Bit_2Bit_2

Bit_1Bit_1

Bit_2Bit_2

Bit_1Bit_1

Bit_2Bit_2

10

Informationsfluss (Flow)Informationsfluss (Flow)

• Teilmenge aller Kanten:Teilmenge aller Kanten:– von Quelle zur Senke– azyklisch– Annahme: K=1

• Für S und T1, T2:# eingehende Kanten von T

= # ausgehende Kanten von S

• Für die anderen Knoten:# eingehende Kanten

= # ausgehende Kanten

Einführung Max-Durchsatz Network Coding Fazit

11

Informationsfluss F (Flow)Informationsfluss F (Flow)

• Die Anzahl gleichzeitig versendbarer Bits B ist abhängig von der genutzten Kantenkapazitäten F=B

• Max-Flow:Max-Flow:Maximiere die Anzahl der genutzten Kantenkapazitäten!

Einführung Max-Durchsatz Network Coding Fazit

12

SenderatenSenderaten

• Pro Kante:Pro Kante: – Kapazität K

• Pro Netz:Pro Netz: – Durchsatz D– (Informationsfluss F)

• Annahme:– Keine Verzögerungen

K1K1

K3K3 K4K4

K6K6K5K5 K7K7

K8K8 K9K9

K2K2

DD

Einführung Max-Durchsatz Network Coding Fazit

13

Problem:Problem: Senden kostet Zeit, weil

Netz durch K

beschränkt

Ziel: Ziel: Möglichst viele

Dateneinheiten (Bits)

pro Zeiteinheit empfangen

( D maximieren)

ProblembeschreibungProblembeschreibung

K1K1

K3K3 K4K4

K6K6K5K5 K7K7

K8K8 K9K9

K2K2

DD

Einführung Max-Durchsatz Network Coding Fazit

14

– Trivial:Trivial: • Mehr Kanten• Schnellere Kanten (Kapazitäten erhöhen)

– Idee von Network Coding (NC):Idee von Network Coding (NC):• Kombinierung und Trennung

von redundanten Bits in den Knoten• Codierung der zu kombinierenden Bits abhängig von

Netzstruktur

– Fragen:Fragen:• Was ist der maximale Durchsatz ohne NC?• Wie werden Bits kombiniert und getrennt und welche Rolle

spielt dabei die Redundanz?• Gibt es ein Standardvorgehen?

LösungsansätzeLösungsansätze

Einführung Max-Durchsatz Network Coding Fazit

Den maximalen Durchsatz Den maximalen Durchsatz bestimmenbestimmen

Einführung Max-Durchsatz Network Coding Fazit

16

• Notation für Notation für Kantenbeschriftung:Kantenbeschriftung:– Zahl K

K=Kapazität

– Zahlen F|K F=Kapazitätsnutzung des Flow K=Kapazität

Beispielnetzwerk des KapitelsBeispielnetzwerk des Kapitels

Einführung Max-Durchsatz Network Coding Fazit

17

a) mehrere ausgehende Kanten

In jede Kante kann ein anderes Bit geschickt werden

b) mehrere eingehende Kanten

von jeder Kante kann ein anderes

Bit hereinkommen

Eigenschaften unserer KnotenEigenschaften unserer Knoten

Einführung Max-Durchsatz Network Coding Fazit

18

Maximaler DurchsatzMaximaler Durchsatz

Max-Flow des Netzwerkes

Max. D = 1

Max-Flow

F = 1

Max-Flow

F = 1

Einführung Max-Durchsatz Network Coding Fazit

19

beide Max-Flows: F = 1 Multicasting von 1 Bit an jede Senke möglich (D=1)

Bit-DarstellungBit-Darstellung

Einführung Max-Durchsatz Network Coding Fazit

20

• Für alle alle Knoten außer S,T S,T gilt für genutzte Kanten:

ankommender Kanten-Kapazitäten

=

ausgehender Kanten-Kapazitäten

Informationserhalt (1)Informationserhalt (1)

Einführung Max-Durchsatz Network Coding Fazit

21

• Für S,TS,T gilt für genutzten Kanten:

ausgehender

Kanten-Kapazitäten von S

=

ankommender

Kante-Kapazitäten von T

Informationserhalt (2)Informationserhalt (2)

Einführung Max-Durchsatz Network Coding Fazit

22

ÜberlegungenÜberlegungen

• Vorhandenes Netz um rote Elemente erweitert

• Intuition:Intuition: zusätzliche Kanten Max-Flows steigen Durchsatz steigt

• Jedoch keine Veränderung erreichbar aufgrund des Engpasses

Intuition stimmt dennoch! Intuition stimmt dennoch! … aber nur durch neue Fähigkeiten der Knoten.… aber nur durch neue Fähigkeiten der Knoten.

Einführung Max-Durchsatz Network Coding Fazit

23

– Flow: • azyklische Verbindung über Kanten von

einer Quelle zu einer Senke

– Max-Flow: • Flow mit der maximalen Kantenzahl

• Anzahl Max-Flows = Anzahl Senken

– Max. Durchsatz:• Der kleinste Max-Flow im Netzwerk

bestimmt den max. Durchsatz

ZusammenfassungZusammenfassung

Einführung Max-Durchsatz Network Coding Fazit

Network CodingNetwork Coding

Einführung Max-Durchsatz Network Coding Fazit

25

– Konflikte und Probleme am Beispiel des Butterfly erkennen

– Network Coding als Lösung kennen lernen

– Informationsfluss und Durchsatz betrachten

– Präsentation eines Algorithmus zur Nutzung von NC

Ziele des KapitelsZiele des Kapitels

Einführung Max-Durchsatz Network Coding Fazit

26

– Wie groß ist Durchsatz ohne NC?

– Wie könnte NC funktionieren, damit der Durchsatz erhöht wird?

HausaufgabeHausaufgabe

Einführung Max-Durchsatz Network Coding Fazit

27

Betrachtung von nur einem Durchlauf:beide Flows sind Max-Flows mit F=1 D=1

Butterfly ohne NC (1)Butterfly ohne NC (1)

Einführung Max-Durchsatz Network Coding Fazit

28

2 Durchläufe: max. D=1.5 durch abwechselnde Nutzung des Engpasses

Wie können wir den Durchsatz D weiter steigern?

Butterfly ohne NC (2)Butterfly ohne NC (2)

Einführung Max-Durchsatz Network Coding Fazit

29

– Ansatz: Funktionalität von Knoten erhöhen– Bisher: Nur Weiterleiten und Duplizieren von Bits

möglich

– Neu: Bits mathematisch durch Operationen wie z.B. „xor“ kombinieren als zusätzliche Möglichkeit Codierung im Netzwerk

– Aufteilung der Knotenmenge:• Teilmenge mit Standardfunktionen• Teilmenge mit Std.funktionen und

Codierfähigkeiten

Network CodingNetwork Coding

Einführung Max-Durchsatz Network Coding Fazit

30

Durchsatz D steigt um ein Drittel !Durchsatz D steigt um ein Drittel !

Butterfly mit NCButterfly mit NC

– C,T1 und T2 haben die Fähigkeit zum Codieren– beide Flows sind Max-Flows mit F=2 D=2

Einführung Max-Durchsatz Network Coding Fazit

31

– Beispielnetzwerk kennen gelernt, dessen Kantenkapazitäten nicht maximal genutzt werden können mit normalen Mitteln

– Problem: Engpässe

– NC geschieht durch Verknüpfung von Bits mit einfachen math. Operatoren

– Dadurch: Steigerung von Informationsfluss und Durchsatz

ZwischenstandZwischenstand

Einführung Max-Durchsatz Network Coding Fazit

32

• Zweck:Zweck:– Finde geeignete Codiervorschriften für jeden Kante im

Netzwerk

• Bitdarstellung Vektordarstellung– d.h. welche Bits durch eine Kante verschickt werden wird

in einem Vektor festgehalten– Jede Dimension des Vektors steht für ein

unterschiedliches Bit – Jede Dimension des Vektors ist

modulo 2 nur 0 oder 1– mehrere Bits schicken Codierung nötig– Bsp.: (1,1,0) Bit 1 und Bit 2 worden durch ein xor

verbunden, Bit 3 nicht

Vorbesprechung zum Algorithmus (1)Vorbesprechung zum Algorithmus (1)

Einführung Max-Durchsatz Network Coding Fazit

33

• Unterschiedliche Vektoren für einzelne Bits nötig• Basisvektoren:

– Menge von Vektoren aus deren Linearkombination (LK) alle anderen darstellbar sind

– minimale Anzahl gesucht spezifizieren

• kanonische Einheitsbasis:– Im endlich dimensionalen Vektorraum der natürlichen Zahlen– Norm bzw. „Länge“ dieser ist 1

– Bit bi hat Einheitsbasis mit Wert 1 an Stelle i

– z.B.: im 3-dimensionalen Raum (0,0,1) (0,1,0) und (1,0,0)

• Endlicher d-dimensionalen Raum (d = angenommener Durchsatz)

Vorbesprechung zum Algorithmus (2)Vorbesprechung zum Algorithmus (2)

Einführung Max-Durchsatz Network Coding Fazit

34

• X: der Knoten X

• XY: die Kante von X nach Y

• V(XY):der Vektor der Kante XY

• VR(X): der Vektorraum des Knoten X

Notationen zum AlgorithmusNotationen zum Algorithmus

Einführung Max-Durchsatz Network Coding Fazit

35

V(XY) = NullvektorV(XY) = NullvektorXYXY

XX XXjjYY

VR(XVR(Xj+1j+1) := Raum aller ) := Raum aller

Vektoren deren ausgehende Vektoren deren ausgehende

Kanten in XKanten in Xj+1j+1 münden münden

V(XV(XjjY) = V;Y) = V;

Wähle einen Vektor V aus Wähle einen Vektor V aus

VR(XVR(Xjj):Fallunterscheidung ):Fallunterscheidung

(wird noch detailliert)(wird noch detailliert)

XXjj ist aktueller Knoten ist aktueller Knoten

XXjjY ist aktuelle ausgehende KanteY ist aktuelle ausgehende Kante

Einführung Max-Durchsatz Network Coding Fazit

Der Algorithmus (1)Der Algorithmus (1)

36

• Fall 1: Xj ist Quelle möglichst alle kanonischen Einheitsbasen verteilen und ggf. LK aus ihnen

• Fall 2: Xj ist Senke Senke muss alle Einheitsbasen bekommen bzw. sie herleiten können aus codierten Vektoren Testen mit Vektoren aus VR(Xj)

Der Algorithmus (2)Der Algorithmus (2)

Einführung Max-Durchsatz Network Coding Fazit

37

• Fall 3: nur eine eingehende Kante WXj nach Xj

simples weiterleiten

• Fall 4: mehrere eingehende Kanten nach Xj und eine oder mehrere ausgehende Kanten neue LK bilden

1. alle vorhandene Vektoren verknüpfen, z.B.: (1,1,1)

2. Telmengen der vorhandenen Vektoren verknüpfen, z.B.: (1,1,0)

3. Simples weiterleiten der ankommenden Vektoren

Der Algorithmus (3)Der Algorithmus (3)

Einführung Max-Durchsatz Network Coding Fazit

FazitFazit

Einführung Max-Durchsatz Network Coding Fazit

39

– Mehrere Quellen• Jede Quelle schickt Informationen, die unabhängig von den

anderen Informationen ist• Unterschiede im Multicasting

– Alle Quellen multicasten an alle Senken (Broadcasting)– Quellen multicasten nur an Teilmengen von Senken

– Zyklische Netzwerke

– Fehlerhafte Datenübertragung & Verzögerungen• z.B.: Funkübertragung

Fortführende komplexere ThemenFortführende komplexere Themen

Einführung Max-Durchsatz Network Coding Fazit

40

FazitFazit

• Problem:Problem:– Senden von Informationen kostet Zeit.

• ZielZiel::– Durchsatz erhöhen

• Lösung:– Ausnutzen der Redundanz in einem

Multicast-Netz durch Network Coding

Einführung Max-Durchsatz Network Coding Fazit

41

Interesse geweckt?Interesse geweckt?

Modul ESS: Modul ESS: (Eingebettete Systeme und Systemsoftware) (Eingebettete Systeme und Systemsoftware)

Vorlesung: Rechnernetze bei Prof. Dr. Karl Vorlesung: Rechnernetze bei Prof. Dr. Karlhttp://http://

wwwcs.upb.de/cs/ag-karl/wwwcs.upb.de/cs/ag-karl/

Gibt es Fragen ?Gibt es Fragen ?

Vielen Dank für eure Vielen Dank für eure Aufmerksamkeit.Aufmerksamkeit.

43

Der Algorithmus am Beispiel (1)Der Algorithmus am Beispiel (1)

44

Der Algorithmus am Beispiel (2)Der Algorithmus am Beispiel (2)