Technische Universität München Lehrstuhl für Kommunikationsnetze Prof. Dr.-Ing J. Eberspächer Diplomarbeit Abschlußvortrag Entwicklung und Implementierung

Technische Universität München

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

Diplomarbeit

Abschlußvortrag

Entwicklung und Implementierung vonlinearen Optimierungsmodellen für Routing-

und Kapazitätsplanung in IP-Netzenmit mehreren Verkehrsklassen

Daniel Rö[email protected]

19.06.2002

Betreuer: Dipl.-Ing. (Univ.) Anton Riedl

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

Daniel RögeleinDiplomarbeit

Abschlußvortrag 2

Gliederung

• Planungsziele• Modellierung• Implementierung• Untersuchungen zur Anwendbarkeit des Modells• Zusammenfassung der Ergebnisse der Diplomarbeit• Demonstration Netzplanungs-Software „OMNI“



Abschlußvortrag 3

Planungsziele (1)

• Kapazitäts-Planung:

Anpassung der Link-Kapazitäten bei vorgegebenem Routing

– Ableiten einer Topologie mit minimalen Kosten

– Kapazitäts-Anpassung zur Verminderung der Verzögerung in Netzwerk-Knoten bzw. Einhaltung von Dienstgüte-Anforderungen von Flüssen

• Routing-Optimierung:

Anpassung des Routings von Flüssen bei fixierten Kapazitäten– Minimierte Verzögerung– Lastausgleich durch Minimierung der maximalen

Auslastung im Netzkern

+ Vorteil der Abgrenzung von Kapazitäts- gegenüber Routing-Variabilität: Resultierende Probleme geringerer Komplexität

- Nachteil: Starke Einschränkung des Lösungsraumes



Abschlußvortrag 4

Planungsziele (2)

+ Vorteil: Großer Lösungsraum, unter Umständen bessereErgebnisse als iterative Kapazitäts/Routing-Optimierung

- Nachteil: Hohe Komplexität der resultierenden Probleme

• Erweiterungs-Planung (Kapazitäten und Routing variabel):– Ableiten eines Ergebnisses, welches unter den

Gesichtspunkten der Routing-Optimierung sowie Kapazitätsplanung in abzuwägendem Maße optimal ist.

Entwicklung eines linearen Optimierungsmodells zurErweiterungsplanung, welches durch optionale Parametrierungin Untermodelle zur Kapazitäts-Planung bzw.Routing-Optimierung überführt werden kann.



Abschlußvortrag 5

Gliederung

• Planungsziele• Modellierung

– Abbildung der Topologie– Link-Dimensionierung– Kapazitäts-Partitionierung– Beschreibung von Flüssen nach Fluß-/Pfad-Ansatz– Berechnung der Verzögerung in Netzwerk-Knoten

• Implementierung• Untersuchungen zur Anwendbarkeit des Modells• Zusammenfassung der Ergebnisse der Diplomarbeit• Demonstration Netzplanungs-Software „OMNI“



Abschlußvortrag 6

Abbildung der Topologie

• Knoten-Menge , Kanten-Menge • Verzögerung eines Links• Zugehörigkeit zum Netzkern

DA

C F

EB

(A,B)

(B,A)(D,G) G

(G,D)

H I

=1

=0

Netzkern

Zugangsnetz



Abschlußvortrag 7

Link-Dimensionierung (1)

• Diskretisierung der Kapazitätsstruktur durch Link-Dimensionen



Abschlußvortrag 8

Link-Dimensionierung (2)

• Spezifikation des Bereichs zulässiger Dimensionen pro Link

– feste Dimension

=3Rate

obere Grenze

untere GrenzeRate

Rate

variable Dimension 1..3

e

=1

1

2

3

Rateobere Grenze = untere Grenze

feste Dimension

e

=3

3

– variable Dimension

• Variabler Link-Dimensions-Vektor



Abschlußvortrag 9

Kapazitäts-Partitionierung

• Partitionierung der Übertragungsrate pro Link– einfachster Fall: eine Partition, alle Klassen teilen sich gesamte Rate

– Reservierung von Kapazität für bestimmte Klassen (Bsp. 2 Partitionen)

c2c1 c3={ }

c2c1

c3

=x

=1-x

={

={

}

}

1,e

2,e

e

1,e

2,e

c2c1={ c3 }1,e

e

=100%1,e

Menge derVerkehrsklassen



Abschlußvortrag 10

Darstellung von Verkehrsflüssen (1)

• Verkehr nach Fluss-Ansatz– Fluss f beschrieben durch Quelle o, Senke d, Klasse c: f=(o,d,c)

– Datenrate des Flusses: ; maximaler Delay

– Beispiel: f =(A,G,c3)

C F

E

ff

– Berechnung, Darstellung der Route anhand binärer Flussmatrixunter Einhaltung von Quell-, innerem, Senken-Gleichgewicht.

B

A GD

=1f,(A,B)

=0f,(A,D)

=0f,(A,C)



Abschlußvortrag 11

Darstellung von Verkehrsflüssen (2)

• Verkehr nach Pfad-Ansatz– Beispiel: Fluss p=(A,G,c3)

– Rate , maximaler Delay

pp

– Aufteilung der Rate auf Pfadalternativen …

– Angabe von (statischen) Pfadalternativen

C

– … unter Randbedingung der Flusskonservierung

A

=(1/4)1,p

=(1/2)2,p

B E

GD

=(1/4)3,p

F

Flußkonser-vierung:

=1



Abschlußvortrag 12

Berechnung der Verzögerung in Netzwerkknoten

Routing

Wartesysteme

Ein Wartesystem pro abgehendem Link

• Kenntnis der internen Struktur von Vermittlungsknoten erforderlich



Abschlußvortrag 13

• R Kapazität eines abgehenden Links

• r Datenrate auf abgehendem Link

• ρ = r / R Auslastung des abgehenden Links

• MTU Maximale Paketgröße („worst case“)

• = Mittlere Wartezeit der Pakete

Größen des M/D/1-Paket-Wartesystems

~

~

~

~~

1



Abschlußvortrag 14

Lineare Approximation der Wartezeit-Funktion

0,4 0,8 1

2

4

6

8

0,60,2 ρmax

Exakter Wert

>T0( )

>T1( )

>T2( )

>T3( )

Randbedingungen

Approximierter Wert



Abschlußvortrag 15

Unterstützung von Verkehrs-Priorisierung

• Unterstützung von Verkehrs-Priorisierung:Für die Berechnung der Wartezeit ist nur derqueuing-relevante Verkehr von Bedeutung:

c1-relevant

c2-relevant

c3-relevant

c1-relevant

c2-relevantc3-

relevant

Partition 1

Partition 1

Partition 2

c1,c2,c3-relevant

c1,c2-relevantc3-relevant

OhnePriorisierung

MitPriorisierung

c2c1 c3Ordnungsrelation: < <

=0 =1



Abschlußvortrag 16

Bestandteile der Gesamtverzögerung von Flüssen

• Die Gesamtverzögerung eines Flusses setzt sichaus Anteilen in Netzwerk-Knoten sowie auf Links zusammen:

A

D

CBc1(A,B),c1

(B,C),c1

• Beim Pfad-Ansatz werden nur verwendete Pfadalternativen berücksichtigt

(auf Links)

(in Knoten)



Abschlußvortrag 17

Gliederung

• Planungsziele• Modellierung• Implementierung

– AMPL– Netzplanungs-Software „OMNI“

• Untersuchungen zur Anwendbarkeit des Modells• Zusammenfassung der Ergebnisse der Diplomarbeit• Demonstration Netzplanungs-Software „OMNI“



Abschlußvortrag 18

AMPL-Implementierung

Datensatz Pre-

Sol

ver

Solv

er

Ableitungdes LGS

Ableitung vonRandbedingungen,

Zielfunktion

AMPL Benutzer

Optionen

*.mod-Datei

*.dat-Datei

• Konkretes Optimierungsproblem (Topologie, Fluß-Datensatz,TE-Disziplin und Optimierungsziel) wird in *.dat- Datei hinterlegt.

ModellInterpretationder Zustands-

variablen

AMPL liefert gutes „Feedback“ bei der Modell-Entwicklung



Abschlußvortrag 19

Software-Implementierung „OMNI“

GUI

Interpretationder Zustands-

variablen

GUI

Optionen

Datensatz

Visualisierung

Modell Ableitungdes LGS

Ableitung vonRandbedingungen,

Zielfunktion

Concert Technology

Pre-

Sol

ver

Solv

er

OMNI

OMNI

Top

olog

ie*.

top

Flü

sse

*.fl

owK

ap.

Kos

t.*.

cost

Demonstration



Abschlußvortrag 20

Gliederung

1. Planungsziele

2. Modellierung

3. Implementierung

4. Untersuchungen zur Anwendbarkeit des Modells• Lastausgleich bei Routing-Optimierung• Linkkosten-Minimierung bei Erweiterungsplanung• Lastausgleich bei Erweiterungsplanung

5. Zusammenfassung der Ergebnisse der Diplomarbeit

6. Demonstration Netzplanungs-Software „OMNI“



Abschlußvortrag 21

Lastausgleich bei Routing-Optimierung (1)

Bereits bei maximal 4 gleichzeitig verwandtenkantendisjunkten Pfadalternativen wird optimalesErgebnis gemäß LP Fluß-Ansatz erreicht.

Topologie „bird“,100 Knoten, 1026 Links,

500 Flüsse

Shortest Path Routing, längen-proportionale Kantengewichte



Abschlußvortrag 22

Lastausgleich bei Routing-Optimierung (2)

Die Ableitung des optimalen Ergebnissesbei 4 Pfadalternativen erfolgt 25 mal schnellerals beim LP-Fluß-Ansatz

Topologie „bird“,100 Knoten, 1026 Links,

500 Flüsse



Abschlußvortrag 23

Linkkosten-Minimierung bei Erweiterungsplanung

Topologie „corse“,20 Knoten, 74 Links,

58 Flüsse

• Rechenzeit der Optimierung:Anzahl

Kapazitäten

Ans

atz

/ 2 Std. 4 Min.

8 Sek. 4 Sek. 5 Sek.

4 3 2

F

P

/ 294 520

414 414 800

4 3 2

F

P

• Linkkosten-Summe

Pfad-Ansatz schneller, aber 40%-50% schlechteres Ergebnis

F: Fluß-AnsatzP: Pfad-Ansatz,

kantendisjunkte Pfade

Routing nach:



Abschlußvortrag 24

Lastausgleich bei Erweiterungsplanung (1)

• Lastausgleich kann bei variablen Kapazitätennicht durch Minimierung der maximalenAuslastung erfolgen.

Alternativ: Trade-Off der Gesamtverzögerung inNetzwerk-Knoten gegenüber derGesamtkosten der Topologie

• Als Vergleichswert: Wiederholter Lastausgleich beiRouting-Optimierung gefolgt von Link-Kosten-Minimierung bei Kapazitäts-Planung(Heuristik zur Ableitung eines Referenzwertes)



Abschlußvortrag 25



4 Kapazitäten,6 Flüsse



Abschlußvortrag 26



4 Kapazitäten,6 Flüsse



Abschlußvortrag 27

Gliederung

• Planungsziele• Modellierung• Implementierung• Untersuchungen zur Anwendbarkeit des Modells• Zusammenfassung der Ergebnisse der Diplomarbeit• Demonstration Netzplanungs-Software „OMNI“



Abschlußvortrag 28

Zusammenfassung der Ergebnisse der Diplomarbeit

• Entwicklung eines linearen Optimierungsmodells für– Kapazitätsplanung– Routing-Optimierung– Erweiterungsplanung

• Implementierungen des Modells in Modellierungssprache AMPL und Netzplanungs-Werkzeug „OMNI” mit Hilfe vonLEDA- /Concert Technology- Bibliotheken

• Untersuchungen zur Anwendbarkeit des Modells



Abschlußvortrag 29

Demonstration

Demonstration der Netzplanungs-Software

OMNI

Documents

Technische Universität München Lehrstuhl für Kommunikationsnetze Prof. Dr.-Ing J. Eberspächer Diplomarbeit Abschlußvortrag Entwicklung und Implementierung