Stefan Dziwok ([email protected]) Institut für Informatik FG Rechnernetze Universität Paderborn Network Coding

Stefan Dziwok([email protected])

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


5

Die UmgebungDie Umgebung

– Netz von Computern

– Verbunden über Leitungen

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


6

Abstrahierung der UmgebungAbstrahierung der Umgebung

– Netz von Knoten

– Verbunden über Kanten

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

Der Butterfly


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


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


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


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


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!


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


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


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


Den maximalen Durchsatz Den maximalen Durchsatz bestimmenbestimmen


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


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


18

Maximaler DurchsatzMaximaler Durchsatz

Max-Flow des Netzwerkes

Max. D = 1

Max-Flow

F = 1

Max-Flow

F = 1


19

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

Bit-DarstellungBit-Darstellung


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)


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)


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.


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




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


26

– Wie groß ist Durchsatz ohne NC?

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

HausaufgabeHausaufgabe


27

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

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


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)


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



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


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


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)


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)


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


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


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)



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



FazitFazit


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


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


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)

Documents

Stefan Dziwok ([email protected]) Institut für Informatik FG Rechnernetze Universität Paderborn Network Coding