Technische Universität München Lehrstuhl für Kommunikationsnetze Prof. Dr.-Ing. J. Eberspächer...

Technische Universität München

Lehrstuhl für KommunikationsnetzeProf. Dr.-Ing. J. Eberspächer

Interdisziplinäres Projekt

Abschlussvortrag

Bandwidth Consumption ofMulti-Path Resilience Concepts

Wolfgang Mühlbauer / Matthias [email protected] / [email protected]

Betreuer: Claus Gruber

Technische Universität München Lehrstuhl für KommunikationsnetzeProf. Dr.-Ing. J. Eberspächer

Wolfgang Mühlbauer / Matthias WimmerInterdisziplinäres Projekt

Abschlussvortrag 2

Inhalt

• Motivation• Grundlagen

– Konzepte für Ausfallsicherheit– Mehrwege-Erweiterungen– Freigabe der Verbindungsstümpfe

• Implementierung– Übersicht– Modellierung der Graphen– Aufbau der Nebenbedingungen– Baukastenprinzip– Probleme

• Ergebnisse– Auswirkungen der Pfadbegrenzung– Vergleich der Ausfallsicherheitskonzepte– Einfluss der Mehrwege-Erweiterungen– Nebeneinanderstellung der Zielfunktionen– Zusammenfassung



Abschlussvortrag 3

Motivation für Ausfallsicherheit

Flughafen

Hauptbahnhof

Zwei Wege vom Hauptbahnhof zum Flughafen:Jeweils 40 Minuten Fahrzeit



Abschlussvortrag 4

Konzepte für Ausfallsicherheit: Ansätze

• Bei Ausfallsicherheit in Datennetzen unterscheidet man zwischen drei Ansätzen:– „Protection“: Die Fehlerszenarien sind vorausberechnet

und die Ausweichpfade sind im Netz vorkonfiguriert.– „Restoration“: Die Fehlerszenarien sind

vorausberechnet, die Ausweichpfade werden aber erst im Bedarfsfall im Netz eingestellt.

– „Rerouting“: Erst im Fehlerfall wird für die betroffenen Pfade ein neuer Weg gesucht. Es ist nicht garantiert, dass ein solcher gefunden wird.



Abschlussvortrag 5

Konzepte für Ausfallsicherheit: 1+1 Path Protection

01101

0110111101

11101



Abschlussvortrag 6

Konzepte für Ausfallsicherheit: 1:1 Path Protection

0110111101

Nimm denanderen Pfad!

10001



Abschlussvortrag 7

Konzepte für Ausfallsicherheit: 1:N Path Protection

01101 00001 11111Nimm den

anderen Pfad!

11000



Abschlussvortrag 8

Konzepte für Ausfallsicherheit: Haskin

0110111001



Abschlussvortrag 9

Konzepte für Ausfallsicherheit: Link Protection

01101

00000



Abschlussvortrag 10

Konzepte für Ausfallsicherheit: Local-to-Egress

01101

11100



Abschlussvortrag 11

Konzepte für Ausfallsicherheit: Regional Protection

01101

Region 1 Region 2

10001

Nimm denanderen Pfad!

01111



Abschlussvortrag 12

Konzepte für Ausfallsicherheit: Ring-Protection

1111101110



Abschlussvortrag 13

Konzepte für Ausfallsicherheit: p-Cycles



Abschlussvortrag 14

Mehrwege-Erweiterungen (Multi-Working-Path)

100 100

100

10010

0

200?

100

100

100



Abschlussvortrag 15

Mehrwege-Erweiterungen (Multi-Protection-Path)

50 50

100

50

50

100

50

50



Abschlussvortrag 16

Freigabe der Verbindungsstümpfe

100

100

100

100

100



Abschlussvortrag 17

Implementierung - Übersicht

Relationenmodell GRAPH Library

Repräsentation von Eingabe und Ausgabe

Resilience Verfahren

Zentrale Ablaufsteuerung

Linearer Optimierer CPLEX/Concert

Bedingungen (Constraints)



Abschlussvortrag 18

Implementierung – Repräsentation von Graphen

• Eingabe: 2 GML Dateien– Physical Network– Demand Graph

• Ausgabe: 4 GML Dateien– Physical Network– Demand Graph– Working Graph– Protection Graph

• Verknüpfung der Graphen durch Setzen von Relationen (siehe Beispiel)



Abschlussvortrag 19

Implementierung – Repräsentation von Graphen

Demand GraphPhysical Network

Working Graph

Protection Graph



Abschlussvortrag 20

Implementierung – CPLEX

• Optimierung der Bandbreite mit CPLEX (version 7.5)

• Zugriff auf CPLEX mittels Concert

Solver (Optimierer)

Modell

Variablen ConstraintsZielfunktion

Abbildung: Komponenten für den Solver



Abschlussvortrag 21

Implementierung - CPLEX Variablen

Variablen des Optimierers muss eine Bedeutung zugeordnet werden! (z.B. Working Pfad, Protection Pfad)

Protection Einheiten

Kreise

Working Pfade

Identifikation von Variablen (Auszug)

Träger von Kapazitäten: Pfade

PathPairPathPairForErrorEdgeRerouteProtectionKeyRingProtectionKey



Abschlussvortrag 22

Implementierung – CPLEX Variablen

Semantisch zusammengehörige Variablen werden in gemein- samer Klasse verwaltet (z.B. alle möglichen Working Pfade).

• Allgemeine Formulierung von Constraints möglich

• Speichert ausgewählte relevante Variablen

• erlaubt einfaches Iterieren durch die relevanten Variablen

Vorteil: Klasse CplexVariable

Attribute:allVariables (map)

Methoden:operator[]addVariables(...)Iterator



Abschlussvortrag 23

Implementierung – CPLEX Constraints

Constraint 1

Realisierung der Constraints

Constraint {abstract}

addYourself()

Constraint n Constraint m… …

• Ziel: Constraints sollen universell einsetzbar sein.• Constraints "fügen sich selbst dem Modell hinzu".



Abschlussvortrag 24

Implementierung – Aufbau eines CPLEX Modells

Constraint 1

Ablauf der Erzeugung eines CPLEX Modells

Network Calculator(verwaltet die Resilience Klassen)

Constraint n Constraint m… …

Resilience Klasse(Liste aller Constraints)Aktueller Schritt:

Network Calculator erzeugen:Alle CPLEX Para- meter werden initialisiert.

Dem Network Calculator die neu angelegte ResilienceKlasse hinzufügen.

Resilience Klasse erzeugen: Alle relevanten CPLEX Variablen und Constraints erzeugen.

Berechnung im Network Calculator starten: Hinzufügen der Constraints aller Resilience Klassen und der Zielfunktion



Abschlussvortrag 25

Implementierung – Resilience Klassen

• Problem: Unterstützung verschiedener Resilience-Verfahren und Multipath-Erweiterungen erfordert Vielzahl an Resilience Klassen

• Lösung: Wiederverwendung und Vererbung

Multipath Klassen (Dedicated)

Vererbungshierarchie der Resilience Klassen (Grundidee)

CplexResilienceStrategy

Multipath Klassen (Shared)

Konkrete Klassen

zentrale Klasse: Berechnet z.B. relevante Working Pfade

enthalten zusätzlich Variablen für ge- teilte (Protection) Kantenkapazitäten Spezielle Constraints für das gewählte Resilience Verfahren

Constraints und Variablen für die gewählte Multipath Variante



Abschlussvortrag 26

Implementierung - Zielfunktionen

• Zielfunktion ist Bestandteil des Network Calculators• Implementierung der abstrakten Methode

addTargetFunction() in Unterklassen von CplexNetworkCalculator

• Zukünftige Erweiterbarkeit

Mögliche Minimierungsziele:

• Minimale Gesamtkapazität

• Minimale Working Kapazität

• Minimales maximales Kantenauslastungsverhältnis



Abschlussvortrag 27

Implementierung - Modularität

Mehrere Resilience Verfahren

Modularität/Vielfältigkeit bezüglich:

Resilience Verfahren

Zielfunktion

Multipath Variante

1+1, 1:N, Haskin, Local-To-Egress, Link, Regional, Rerouting with and without Stub-Release, Ring, pCycle

Mehrere Working Pfade je Demand Mehrere Protection Pfade je Working Pfad Beliebige und gleiche Kapazitätsverteilung

Verschiedene Optimierungsmöglichkeiten

Verwendung unterschiedlicher Resilience Verfahren für jeden einzelnen Demand Graphen (falls mehrere Demand Graphen zu einem Physical Network existieren)



Abschlussvortrag 28

Implementierung – Probleme mit dem Speicherbedarf

COST 239 Netzwerk

Folge: ca. 472MiB benötigt, um alle Pfadpaare im Speicher zu halten (geschätzter Wert)

# Knoten 11

# Kanten 52

# Pfade pro Demand 923 bis 1760

# Disjunkte Pfadpaare pro Demand ca. 250000 bis 500000

Abhilfe durch Reduzierung der verwendeten Pfade:• Einführung einer Schranke für die maximale Pfadlänge• Nur Verwendung der kürzesten Pfade je Pfadpaar



Abschlussvortrag 30

Auswirkungen der Pfadbegrenzung an COST 239

Pfade/Knotenpaar Benutzte Kapazität Zeitverbrauch

10 1.649,12 Gib/s < 1 Minute

20 1.621,15 Gib/s 13 Minuten

30 1.613,40 Gib/s 47 Minuten

40 1.612,85 Gib/s 1 Stunde 24 Minuten

50 1.612,65 Gib/s 3 Stunden 2 Minuten

60 1.612,65 Gib/s 4 Stunden 1 Minute

70 1.612,65 Gib/s 7 Stunden 1 Minute

80 1.612,65 Gib/s

90 1.612,65 Gib/s

100 1.612,65 Gib/s

105 1.612,65 Gib/sBerechnungen am COST-Netzwerk, 1:N Protection, Multipath-Routing erlaubt.



Abschlussvortrag 31

Vergleich der Ausfallsicherheitskonzepte an COST 239

Konzept Working- Pfade

Protection-resources

Working Kapazität

Gesamt-kapazität

1+1 Protection Es existiert hierfür keine Lösung

1:N Protection 136 613 1.279,39 1.612,65

Haskin Es existiert hierfür keine Lösung

Link Protection 133 597 1.272,97 1.743,67

Local-To-Egress

138 651 1.270,27 1.719,64

Regional Protection

133 764 1.279,39 1.612,65

Rerouting mit Stub-Release

136 808 1.279,39 1.612,65

Rerouting ohne Stub-Release

139 850 1.279,39 1.612,65



Abschlussvortrag 32

Wandlung Link-Protection nach 1:N Protection



Abschlussvortrag 33

Vergleich der Ausfallsicherheitskonzepte an COST 239

Konzept Working- pfade


Working Kapazität

Gesamt-kapazität

1+1 Protection 110 116 1.535,00 3.142,50

1:N Protection 136 455 1.277,46 1.582,93

Haskin 128 492 1.267,50 1.773,44

Link Protection 129 646 1.272,50 1.692,25

Local-To-Egress

123 565 1.272,50 1.679,78

Regional Protection

134 643 1.277,69 1.582,92


137 668 1.277,69 1.582,92


140 687 1.277,69 1.582,92



Abschlussvortrag 34

Das WMW-Netz

• Selbst erstelltes Netz• 9 Knoten• 2 x 12 Kanten• 7 bis 12 Pfade pro

Knotenpaar• 72 Demands



Abschlussvortrag 35

Vergleich der Ausfallsicherheitskonzepte an WMW

Konzept Working- pfade


Working Kapazität

Gesamt-kapazität

1+1 Protection 72 72 783,62 1.466,96

1:N Protection 90 129 564,74 867,73

Haskin 79 89 564,74 1.009,96

Link Protection Es existiert hierfür keine Lösung

Local-To-Egress

Es existiert hierfür keine Lösung

Regional Protection

95 307 564,74 867,76


94 272 564,74 867,76


94 284 564,74 867,76



Abschlussvortrag 36

Kapazitätsrelationen zwischen den Konzepten

1+1 = 1:1 ≥

Haskin ≥

Link Protection ≥

1:1 = Reroute ohne Stub-Release≥ Regional Prot.

≥ Rerout mit Stub-Release

Link Protection ≥ Local-to-Egress Protection

Ring Protection ≥ P-Cycle Protection



Abschlussvortrag 37

Ergebnisse – Mehrwege-Erweiterungen

Erlaubte Zahl von Working Pfaden

Working- pfade


Working Kapazität

Gesamt-kapazität

beliebig viele 137 492 1276,85 1586,29

3 134 492 1276,85 1586,29

2 134 483 1276,85 1586,29

1 110 327 1272,50 1602,92

COST 239 Netzwerk mit je 200 Gib/s Kantenkapaztiät



Abschlussvortrag 38

Ergebnisse – gleiche und beliebige Kapazitätsaufteilung

Erlaubte Zahl von Working Pfaden

Gesamtkapazität (Beliebige Aufteilung)

Gesamtkapazität (Gleiche Aufteilung)

Beliebig 1586,29 1588,44

3 1586,29 1588,47

2 1586,29 1588,52

1 1604,92 -

COST 239 Netzwerk mit je 200 Gib/s Kantenkapaztiät



Abschlussvortrag 39

Ergebnisse – Unterschiedliche Zielfunktionen

ZielfunktionGesamt-kapazität

Working-kapazität

Maximale Kanten-auslastung

Mittlere Kanten-auslastung

min. Gesamt K. 1612,65 1279,39 99,52% 69,41%

min. Working K. 1623,86 1267,50 94,34% 67,55%

min. maximale Auslastung

1682,83 1315,62 70,00% 69,03%

COST 239 Netzwerk (Standard)



Abschlussvortrag 40

• Auswahl der kürzesten Pfade zwischen einem Knotenpaar scheinbar sinnvolle Heuristik.

• Unterschiedlicher Bandbreitenverbrauch der Resilience Verfahren. Bandbreitenverbrauch allerdings nicht einziges relevantes Kriterium

• Je mehr Freiheit bezüglich der Mehrwege-Erweiterungen desto geringer normalerweise der Bandbreitenverbrauch

Zusammenfassung



Abschlussvortrag 41

Vielen Dank für die

Aufmerksamkeit!

Date post:	05-Apr-2015
Category:	Documents
Upload:	jannike-landis
View:	106 times
Download:	3 times

Technische Universität München Lehrstuhl für Kommunikationsnetze Prof. Dr.-Ing. J. Eberspächer...

Documents