Approximate Multi Commodity Flow For Wdm Networks Design

Seminar Kommunikationsprobleme

Approximate multicommodity ow for WDM networks design Julian Alexander Krenge [email protected] 12. September 2008

Durch die immer steigende Nutzung des Internets ist ein Ausbau der Hauptnetzwerkverbindungen unumgänglich. Eine adäquate Lösung bietet die optische Übertragungstechnik mit ihrer extrem hohen Bandbreite. Eine so neue und leistungsfähige Technik ist selbstverständlich sehr kostenintensiv. In dieser Arbeit wird ein optisches Netzwerk so konstruiert, dass die Kapazität genügend groÿ und die Kosten minimal sind.

1

Inhaltsverzeichnis 1

2

3

Einführung 1.1

Problemstellung (Rwa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Multidatenuss-Netzwerke (Mcf) . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Wellenlängendivisions-Multiplexen (Wdm) . . . . . . . . . . . . . . . . . .

3

1.4

Modell für optische Netzwerke . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5

Überblick

5

5

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Approximationsalgorithmus für das

Rwa-Problem

5

2.1

Idee

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.3

Korrektheit

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.4

Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

Dynamische

Sssp-Bäume

(Dsssp)

7

3.1

Idee

3.2

Erster Schritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.2.1

Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.2.2

Korrektheit

3.3

4

3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.3.1

Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.3.2

Korrektheit

Zweiter Schritt

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.4

Komplexität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.5

Verbindung mit Approximationsalgorithmus . . . . . . . . . . . . . . . . .

10

Weitere Verbesserungen 4.1

Kürzeste Pfade

4.2

Dynamische kürzeste Pfade

10

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ergebnis

10 11

11

2

1 Einführung Zur Lösung des hier beschriebenen Problems werden einige Begrie und Hilfsmittel benötigt. Zunächst wird die Problemstellung erläutert, danach der behandelte Typ Netzwerk beschrieben und zuletzt die technische Grundlage modelliert.

1.1 Problemstellung (Rwa) Das zu lösende Problem ergibt sich in komplexen optischen Hochgeschwindigkeitsnetzwerken, wie sie in der Telekommunikationsbranche als Backbone-Netzwerk verwendet werden. Den Aufbau und die Verwendung von Backbones erklärt [Wik08a]. Optische Übertragungstechnik bietet sich aufgrund der sehr hohen Bandbreite an, birgt aber den Nachteil einiger teurer Komponenten. Daher ist es notwendig, die Topologie möglichst genau auf den wirklich auftretenden Trac auszurichten. Für diese Ausarbeitung sei das Aufkommen des Tracs hinreichend bekannt. Das Problem, einer Anfrage in einem optischen Netzwerk einen Pfad zuzuweisen, wird aufgrund der speziellen Gegebenheiten eines solchen Netzwerks als Routing and Wavelength Assignment-Problem (Rwa) genannt. Was diese speziellen Gegebenheiten sind, wird im Folgenden besprochen.

1.2 Multidatenuss-Netzwerke (Mcf) Das zu lösende Problem wird im Folgenden auf Multidatenuss-Netzwerken, englisch Multicommodity ow networks (Mcf), betrachtet. Das sind Netzwerke, dargestellt durch

G = (V, E) mit Anfragen (s, t), die über eine Datenmenge f (s, t) verfügen. Diese Anfragen gehen vom Quellknoten s aus und haben einen Zielknoten t. Kanten haben eine Kapazität c(e), die die maximale Menge der übermittelten Daten festlegt einen Graphen

[FF62]. Es ist eine Multimenge

C = {(si , ti ) : si , ti ∈ V, i = 1 . . . k} gegeben, die die auftretenden

Anfragen repräsentiert. Entsprechen die aufsummierten Datenmengen der Anfragen der Gesamtkapazität des Netzwerks, gilt also

P

(si ,ti )∈C + von einem Multidatenuss-Netzwerk [BCL 03].

f (si , ti ) =

P

e∈E

c(e), so spricht man

1.3 Wellenlängendivisions-Multiplexen (Wdm) Im Folgenden wird auf die technische Realisierung von optischen Netzwerken, das Wellenlängendivisions-Multiplexen eingegangen. Dieses wird kurz erläutert und danach ein Modell entwickelt, was ein solches Netzwerk für den Algorithmus darstellt. Wellenlängendivisions-Multiplexen (Wdm) ist eine spezielle Art des Multiplexen. Hierbei wird die Kombination von mehreren Nachrichtensignalen zu einem einzigen ermöglicht. Dies geschieht durch die Einteilung des Lichts in Wellenlängen-Intervalle. Für jede Wellenlänge wird ein Laser als Quelle verwendet, der die Daten z.B. per Amplitudenmodulation überträgt. Bevor die Daten über ein Glasfaserkabel übertragen werden, werden alle Wellenlängenbereiche gebündelt. Aufgrund der Eigenschaften des Lichts beeinussen sich die Signale nun nicht [Tan03, Wik08b]. Ein Beispiel gibt Abbildung 1.

3

f (x)

600nm

550nm

500nm

x

Abbildung 1: Sich überlagernde Lichtwellen

1.4 Modell für optische Netzwerke Für die Betrachtung von optischen Netzwerken ist ein Hilfsgraph notwendig. Eine Anfrage bekommt eine Wellenlänge zugewiesen und kann diese nicht mehr wechseln. Da sich Anfragen auf unterschiedlichen Wellenlängen nicht beeinussen, ist es sinnvoll, jeden Wellenlängenintervall als ein eigenes Netzwerk zu modellieren, wobei die Topologie gleich der Topologie des physikalischen Netzwerks ist. Jeder tatsächliche Knoten hat dann einen Repräsentanten je Wellenlänge. Quellen werden dann modelliert, indem ein zusätzlicher Knoten über unlimitierte Kanten zu allen Repräsentanten Analog wird ein Ziel durch einen Knoten

T

si

c1

der physikalischen Quelle verfügt.

b1

f1 e1 g1

d1 c2 S

a2

b2

f2 T

e2 g2

d2 c3 a3

b3

f3 e3 g3

d3

Abbildung 2: Hilfgraph mit drei Ebenen

4

eingefügt wird, der

dargestellt, der unlimitiert mit allen

bunden ist. Ein Beispiel zeigt Abbildung 2.

a1

S

ti

ver-

1.5 Überblick Diese Grundlagen werden für Lösung des Problems benötigt. Im folgenden Abschnitt wird zunächst ein Approximationsalgorithmus beschrieben. Daraufhin wird das Konzept von dynamischen Single Source Shortest Path-Bäumen behandelt, das den Approximationsalgorithmus verbessert. Auÿerdem werden noch einige Detailverbesserungen vorgenommen. Zuletzt wird ein Fazit gezogen.

2 Approximationsalgorithmus für das

Rwa-Problem

Das Problem stellt sich oenbar nur auf Ganzzahlen. Eine Lösung der linearen Relaxation ist möglich, dieser Ansatz jedoch auf Ganzzahlen nicht verwendbar, das Problem auf Ganzzahlen sogar

N P -hart.

Untersuchungen zeigen aber, dass eine Approximation nur einen geringen additiven Fehler mit sich bringt [CR02, Rag94]. Dieser Fehler ist in Kauf zu nehmen, das Ergebnis in

+

der Realität gut verwendbar [BCL 03]. Also ist das Problem mit einer Genauigkeit

(1 + )-Approximation

abschätzbar, der Algorithmus wird als



bezeichnet.

2.1 Idee Ziel ist es, das Mcf-Problem zu lösen. Um dies zu leisten, betrachten wir das dazu duale Problem: Dabei sollen den Pfaden Längen zugewiesen werden, sodass die gesamte Länge des kürzesten Pfades gröÿer als 1 ist. Beim Algorithmus wird der Graph nach Pfaden kürzer als 1 durchsucht und wenn ein solcher gefunden wird, die Daten an ihm entlang geleitet. Zunächst werden die primären Variablen betrachtet: Die Datenmenge auf einer Kante wird um einen Summanden erhöht, der sich anhand der minimalen Kapazität aller Kanten im Pfad berechnet. Danach werden auch die dualen Variablen aktualisiert, also die Pfadlängen mit einem Faktor in Abhängigkeit des Summanden skaliert. Zweck der parallelen Behandlung des primären Problems, also der Datenmenge auf den Kanten, und des sekundären Problems, also der Länge der Kanten, ist, dass über die Länge des kürzesten Pfades bestimmt werden kann, ob sich die Approximation der genauen Lösung gut genug angenähert hat. Daher ist auch die Abbruchbedingung im Approximationsalgorithmus Algorithm 1 über die Länge des kürzesten Pfades deniert. Diese wird nicht in der Ausgabe angegeben [Fle99].

2.2 Algorithmus Im Folgenden wird der

(1 + )-Approximationsalgorithmus

(Algorithm 1) detailliert an-

hand des Codes erklärt. Für diesen gilt:

G = (V, E), |V | = n, |E| = m, C = {(si , ti ), i = 1 . . . k} ⊆ V 2 ,  > 0

•

Eingabe:

•

Ausgabe: Längenfunktion

•

Ausgabe:

L

auf

E:

f (1 + ε)-Approximation

für jeden Pfad für

5

C

auf

G

si → ti

gilt

L(P ath) > 1

Algorithm 1

1: 2: 3: 4: 5: 6: 7: 8:

1

∀e ∈ E, L(e) = δ = (1 + ) ((1 + ) n)−  , fi (e) = 0 {Lower bound on length of a Sssp} λ = δ while λ ≤ 1 +  do for all i = 1 . . . k do P ath ←Sssp((si , ti )) while L(P ) ≤ (1 + ) λ do cm ← mine∈P ath {c (e)} ∀e ∈ P ath do fi (e) ← fi (e) + log cm 1+

{Initializing}

1+

δ

cm ) ∀e ∈ P ath do L(e) ← L(e)(1 +  c(e) P ath ←Sssp((si , ti ))

9: 10: 11: 12: 13: 14:

(1 + )-Approximationsalgorithmus

end while end for

λ ← λ (1 + ) end while

Nach der Initialisierung (Zeile 1 und 2) leitet der Algorithmus die Daten entlang der kürzesten Pfade: Für jede Anfrage (Zeile 4) wird der kürzeste Pfad berechnet (Zeile 5). Solange der berechnete Pfad kürzer als die gesetzte Maximallänge ist (Zeile 6), wird der Pfad bearbeitet: Mit der minimalen Kapazität (Zeile 7) wird die Erhöhung der Datenmenge auf den Kanten (Zeile 8) und die Skalierung der Kantenlängen (Zeile 9) berechnet. Der Algorithmus terminiert, wenn die Länge jedes kürzesten Pfades von der Quelle bis zum Ziel für jede Anfrage >1 ist.

2.3 Korrektheit Die Korrektheit des Algorithmus ist durch folgende drei Lemmata gegeben [Fle99]. Lemma 2.1

Der Algorithmus terminiert nach O m log1+ε 1+ε Schritten. δ


Beweis: Initial gilt L(e) = δ für alle Kanten (s. Algorithm 1, Zeile 1). Da bei jedem Schritt L(P ath) ≤ 1 mit maximal 1+ multipliziert wird, kann ein 1+ 1+ ist die Anzahl der Verbesserungen ≤ m log1+ [Fle99]. δ

des Algorithmus ein Pfad mit Pfad nicht länger als

1+

multipliziert wird, folglich Lemma 2.2

Beweis:

sein. Zusätzlich gilt auch, dass ein Pfad mit mindestens

Es ist zulässig, den Fluss mit log1+ε 1+ε δ zu skalieren.

Wenn der Fluss auf einer Kante erhöht wird, wird, um die Dualität zu erhalten,

die Länge der Kante mit

1∀i folgende zwei ai bezeichnen wir

1 + ai 

Gleichungen:

multipliziert. Nun gelten oensichtlich für alleP 0

1 + a ≤ (1 + )a

Q

i (1 + ai ) ≥ (1 + )

≤ ai ≤

i

ai

. Als

hier eine Hilfsvariable, die für jeden Schritt unterschiedlich ist, aber

immer angegebene Restriktion erfüllt. Initial gilt lässt sich der Schluss ziehen, dass Lemma 2.3

und

f (e) ≤

L(e) = δ ,

nal

L(e) < 1 + .

c(e) log1+ 1+ δ korrekt ist [Fle99].

Wenn ft der Fluss ist, dann gilt:

6

ft log1+ε

1+ε δ

≥ (1 − 2ε) OP T .

Daraus

Beweis:

Aufgrund des aufwendigen Beweises sei hier auf ihn verzichtet. Zu nden ist er

in [GK98].

2.4 Komplexität Die Anzahl der Iterationen lässt sich mit einem Worst Case-Szenario abschätzen: Wenn jeder Sssp aus nur genau einer Kante besteht, ist die Iterationsanzahl maximal, für die sich dann

m log1+

1+ δ




als obere Schranke ergibt. Da sich δ direkt aus dem anzugebenen  ergibt, kann δ so gewählt werden, dass die Anzahl der Iterationen
+

Genauigkeitsparamter in

O m−2 log1+ n

liegt [BCL 03]. Für einen ersten naiven Ansatz verwenden wir

den klassischen Dijkstra-Algorithmus zur Sssp-Berechnung, der in

O (m + n log n)

liegt.

Daraus schlieÿen wir für die Komplexität des gesamten Algorithmus zur Lösung des Rwa-Problems:

O

3 Dynamische



m log1+ n 2

(m + n log n)



Sssp-Bäume (Dsssp)

Der vorgestellte Approximationsalgorithmus Algorithm 1 bietet Verbesserungspotential, wie erwähnt ist der Einsatz des klassischen Dijkstra-Algorithmus ein naiver Ansatz. Ein ezienterer Algorithmus verwendet dynamische Sssp-Bäume.

3.1 Idee Der klassische Dikstra untersucht bei der Berechnung des kürzesten Pfades jeden Knoten im Netzwerk. Beim Approximationsalgorithmus unterscheiden sich die Netzwerktopologien von Schritt zu Schritt nur geringfügig. Es wird nur die Länge einer Kante erhöht. Oensichtlich kommt also nicht jeder Knoten des Netzwerks in Frage, nun auf dem kürzesten Pfad zu liegen. Diese Tatsache wird berücksichtigt, indem der Sssp-Baum auf Basis der Veränderung aktualisiert wird. Der vorgestellte Algorithmus läuft in zwei Schritten ab. Zuerst wird das Netzwerk daraufhin untersucht, welche Knoten sich so geändert haben, dass sie den kürzesten Pfad beeinusst haben könnten. Danach wird dann der konkrete kürzeste Pfad gesucht [FMSN00].

3.2 Erster Schritt Im ersten Schritt wird das Netzwerk eingefärbt. Es wird die direkte Nachbarschaft des vorherigen kürzesten Pfades untersucht und folgende Farben als Hilfe verwendet: rot bedeutet, dass der Knoten für die Berechnung des Sssp von Relevanz ist, weiÿ steht für das genaue Gegenteil. Pinke Knoten können noch weiÿ oder rot werden, sind im Arbeitsqueue

M.

Der Algorithmus färbt wie folgt ein:

•

Knoten pink und dessen Unterbaum weiÿ, wenn Distanz zur Quelle unverändert

•

Knoten rot und dessen Unterbaum pink, sonst

7

3.2.1 Algorithmus Im Folgenden wird der erste Schritt des Dsssp-Algorithmus, die Einfärbung des Graphen (Algorithm 2), detailliert anhand des Codes erklärt. Für diesen gilt:

•

Eingabe:

•

Ausgabe: Eine Menge von roten Knoten

T (si )

Sssp-Baum über

si , si → ti

kürzester Pfad

Algorithm 2 Einfärbung

1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:

{Initializing}

∀y 6= si

a vertex in

si → ti , Enqueue (M , hy, D(y)i)

while NonEmpty(M) do

hz, D(z)i ← ExtractM in(M ) if ∃ nonred neighbor q ∈ / M of z : D(q) + c(q, z) = D(z) color(z) ← pink P (z) ← q

then

else

color(z) ←

red

v of z ∈ / M do Enqueue (M , hv, D(v)i)

for all child

end for end if end while

Nach der Initialisierung (Zeile 1), wird für alle Knoten aus

M

(Zeile 2) beginnend mit

dem am nächsten zur Quelle (Zeile 3) geprüft, ob sich die Distanz zur Quelle geändert hat (Zeile 4). Ist dies der Fall, wird der Knoten rot (Zeile 8) und sein Nachfolger pink (Zeile 9 und 10) gefärbt, sonst der Knoten pink und sein Unterbaum implizit weiÿ (Zeile 5 und 6).

3.2.2 Korrektheit Die folgenden vier Eigenschaften sind so gut gewählt, dass ihre Korrekteit den Algorith-

+

mus veriziert [BCL 03]. Eigenschaft 3.1

Jeder Knoten im Pfad s → t wird in M eingefügt.

Dies zeigt eindeutig die Initialisierung in Algorithm 2, Zeile 1. Eigenschaft 3.2 Jeder Nachfolger eines roten Knoten und kein Nachfolger eines pinken Knoten wird in M eingefügt, solange er nicht im Sssp ist.

Algorithm 2, Zeile 8-10 zeigt, dass alle Nachfolger von roten Knoten in

M

eingefügt wer-

den, und Algorithm 2, Zeile 4-5, dass kein Nachfolger von weiÿen Knoten in

M

eingefügt

wird. Eigenschaft 3.3

Ein Knoten ist genau dann weiÿ, wenn er niemals in M ist.

8

Dies ist implizit dadurch korrekt, dass alle Knoten, die jemals in

M

sind, mindestens

pink sind. Eigenschaft 3.4

bearbeitet wird. Sei hierfür

t(x)

Wenn u und v in M sind, dann bedeutet D(u) ≤ D(v), dass u vor v

der Zeitpunkt zu dem

die Menge der Knoten die vor

v

x

v ein gegebener Knoten, ∆(v) P (v) ∈ ∆(v) der Vater von v . Es

bearbeitet wird,

bearbeitet wird und

gilt:

∀u ∈ ∆(v) : t(u) < t(P (v)) ∧ P4 ∧ D(P (v)) < D(v) → D(u) < D(P (v) < D(v)) ∀u ∈ ∆(v) : t(P (v)) < t(u) gilt nach Denition: t(u) < t(v). Also wird v zumindest M eingereiht, wenn P (v) bearbeitet wird → v ∈ M wenn t(u). M ist Prioritäts-Queue → bei t(u) ist u = min{x ∈ M } → D(u) < D(v). Also gilt die Eigenschaft für ∆(v) ∪ {v}.

in

3.3 Zweiter Schritt Schritt 1 übergibt die Einfärbung des Graphen an Schritt 2, dieser verfügt also über eine Menge von roten Knoten, die in einen neuen kürzesten Pfad involviert sein könnten. Daraus lässt sich der tatsächliche kürzeste Pfad berechnen.

3.3.1 Algorithmus Da der zweite Schritt in der Literatur bereits detailliert erläutert wurde [FMSN00], hier nur eine kurze Erklärung anhand des zusammengefassten Pseudocodes Algorithm 3.

•

Eingabe: Menge von roten Knoten

•

Ausgabe: Kürzester Pfad

Algorithm 3 Berechnung des kürzesten Pfades

1: 2: 3: 4: 5: 6: 7: 8: 9:

∀ red vertex z : Enqueue(Q, hz, D(z)i) while N onEmpty(Q) do hz, D(z)i ← ExtractM in(Q) for all edge (z, h): h is red do if D(z) + c(z, h)
{Initializing}

end if end for end while

In Zeile 1 wird der Heap Knoten

z

darstellt. Hat

z

rote Nachbar und es gilt

Q

D(z) die Priorität des D(z) = ∞, sonst sei u der beste

des Algorithmus so initalisiert, dass

keinen roten Nachbarn, gilt

D(z) = D(u) + c(u, z). Zeile 2 zeigt, dass der ganze Heap z mit minimaler Priorität extrahiert. Dann

abgearbeitet wird. In Zeile 3 wird der Knoten

wird kontrolliert, ob es im direkten Umfeld einen kürzeren Pfad als den aktuell kürzesten gibt (Zeile 4-5). Falls dies so ist, wird der ganze Heap aktualisiert (Zeile 6).

9

3.3.2 Korrektheit Zum Beweis der Korrekheit genügt folgendes Lemma, welches in [FMSN00] bewiesen wird.

Wenn sich die Länge einer Kante erhöht und Schritt 2 eine gute rot-pinkweiÿ-Färbung übergeben bekommt, so wird ein valider Sssp-Baum berechnet. Lemma 3.1

3.4 Komplexität O(αβ log n), wobei α die Anzahl der bearbeiteten Knoten und β ein intelligenter maximaler Grad ist. Beispiele für β sind √ ≤ 3 für planare Graphen, ≤ d für Graphen mit Grad d und = O( m) für generische Die Komplexität des gesamten Dsssp-Algorithmus ist in

Graphen. Auf jeden Fall ist die Komplexität immer kleiner als die des klassischen Dijkstra

O(m + n log n)

+

[BCL 03, FMSN00].

3.5 Verbindung mit Approximationsalgorithmus Es ist nicht möglich, jede Anwendung von Dijkstra in Algorithm 1 durch den DssspAlgorithmus zu ersetzen. Zu den Beispielen, wo eine Ersetzung unmöglich ist, gehören die Fälle, in denen ein kürzester Pfad für eine Anfrage das erste mal berechnet wird. Hier ist oensichtlich keine Berücksichtigung des vorherigen Baums möglich, da ein solcher nicht existiert. Konkret führt das zu einer abstrakten Komplexität des Rwa-Algorithmus, wobei die Komplexität von Sssp und Dsssp noch nicht explizit angegeben sind:

O



log1+ε n ε2

 (k.Sssp + (m − k).Dsssp)

4 Weitere Verbesserungen Zwei weitere Überlegungen zur Verbesserung des Rwa-Algorithmus kommen auf. Betrachtet wird die Berechnung der kürzesten Pfade und der dynamischen kürzesten Pfade. Status Quo: Das Netzwerk hat

n

Knoten und

m

Kanten. Die Gröÿe des Hilfsgraphen

wird maÿgeblich bestimmt durch die Anzahl der Wellenlängen also

O(n2 )

Knoten und

O(wn2 )

w

und der Anfragen, hat

Kanten.

4.1 Kürzeste Pfade Da sich der neue Sssp nur auf eine Quelle und ein Ziel bezieht, können alle anderen Quellen und Ziele ignoriert werden. Dies senkt die Anzahl der relevanten Knoten auf

O(wn)

und Kanten auf

O(wm).

Dadurch verbessern sich Zeile 5 und 10 von Algorithm

+ 1 [BCL 03].

10

4.2 Dynamische kürzeste Pfade Es wird oensichtlich nur eine Ebene bei der Aktualisierung der kürzesten Pfade berücksichtigt, da nach Denition eine Anfrage die Wellenlänge und damit die Ebene nicht

O(αβ log n)

lässt sich in einer

O(m + n log n) nach oben abschätzen. O(n log w) [BCL+ 03].

Der Abschluss der

wechselt. Der Dsssp-Algorithmus mit der Komplexität Ebene leicht durch Dijkstras

Aktualisierung benötigt nocheinmal

5 Ergebnis Verglichen mit Programm, das den naiven Ansatz darstellt, ist die Verbes dem linearen  serung in

O

n4 w2 ε2 log1+ε n . Der Rwa-Algorithmus lässt sich letztendlich abschätzen durch:

O



log1+ε n wn2 (m ε2

 + n log nw)

Der Algorithmus ist also bereits gut und kann auf komplexen Netzwerken arbeiten, bei hochkomplexen Netzwerken weist er aber noch Ezienzprobleme auf. Wenn zusätzlich noch hohe Genauigkeit verlangt wird, kann die Implementierung zu numerischen Ge-

+

nauigkeitsproblemen führen [BCL 03]. Weitere Verbesserungen das Algorithmus können das Problem aber wirtschaftlich lösbar machen und damit das Tor zur kommerziellen Nutzung aufstoÿen [Kau01].

11

Literatur +

[BCL 03]

Bouklit, M., D. Coudert, J-F. Lalande, C. Paul und H. Rivano:

Approximate multicommodity ow for WDM networks design. In: Sibeyn, J. (Herausgeber): SIROCCO 10, Nummer 17 in Proceedings in Informatics, Seiten 4356, Umea, Sweden, 2003. Carleton Scientic.

[CR02]

Lightpath assignment for multibers Wdm optical networks with wavelength translators. In: IEEE Globecom '02, Taiwan, Coudert, D. und H. Rivano:

2002. [FF62]

Ford jr., L. R. und D. R. Fulkerson:

Flows in Networks,

Kapitel I und

II, Seiten 1  49. Princeton University Press, 1962. [Fle99]

Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. In: IEEE Symposium on Foundations of Computer Science, Seiten 2431, 1999. Fleischer, Lisa:

[FMSN00] Frigoni, D., A. Marchetti-Spaccamela und U. Nanni:

Algorithms for Maintaining Shortest Paths Trees.

Fully Dynamic

Journal of Algorithms, 34,

2000. [GK98]

[Kau01]

Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. In: IEEE Symposium on Foundations of Computer Science, Seiten 300309, 1998.

Garg, N. und J. Konemann:

Kauffels, F.-J.:

Durchblick im Netz,

Kapitel 21. Optische Netze, die Zu-

kunft der Datenubertragung. MITP-Verlag, 2001. [Rag94]

Probabilistic construction of deterministic algorithm: Approximating packing integer programs. Journal of Computer and System Sciences,

Raghavan, P.:

38:683  707, 1994. [Tan03]

Tanenbaum, A. S.:

Computernetzwerke,

Kapitel 2.5.4. Verbindungsleitun-

gen und Multiplexing, Seiten 161  171. Pearson Studium, 4 Auflage, 2003. [Wik08a]

Wikipedia:

Backbone

(Telekommunikation).

http://de.wikipedia.org/wiki/Backbone_(Telekommunikation), 03.08.2008. [Wik08b]

Wikipedia:

Multiplexverfahren,

Kapitel Optisches Wellenlängenmultiplex-

verfahren. http://de.wikipedia.org/wiki/Multiplexverfahren, 18.05.2008.

12