File Allocation ProblemVergleich zweier Modelle
Stefan Nolting
File Allocation Problem - Vergleich zweier Modelle 2
Inhalt
File Allocation Problem
FAP with worst-case delayZielfunktion
Nebenbedingungen
Lösungsweg
Exkurs: Lagrange Relaxation
FAP with average delay
Vergleich FAP-WCD / FAP-AD
File Allocation Problem - Vergleich zweier Modelle 3
File Allocation Problem (FAP)
Plazierung von Files und deren Kopien in einem verteilten Filesystem
Bestimmen der Anzahl der Kopien und deren Position im System
die Kosten für das Speichern der Files und der nötigen Kommunikation sollen minimiert werdenWege stehen vorher eindeutig fest
stellt ein wichtiges Kriterium beim Design eines verteilten Filesystems dar
File Allocation Problem - Vergleich zweier Modelle 4
Lösungsansätze (1)
es existieren viele unterschiedliche Modelle
die meisten beachten nicht die
Antwortzeiten auf eine Anfrage
oder sie betrachten sie nur als eine globale
und systemweite Bedingung
unrealistisch, da es i.d.R. eine Prioritäts-
struktur für Anfragen gibt (realtime-
Anwendungen Stapelverarbeitung)
File Allocation Problem - Vergleich zweier Modelle 5
Lösungsansätze (2)
hier sollen zwei Modelle für das FAP
betrachtet werden
sie verfolgen als Ziele
die Minimierung der Betriebskosten
und die Einhaltung bestimmter
Antwortzeiten für on-line Anfragendie zulässigen Antwortzeiten für
verschiedene Anfragen und Dateien können
unterschiedlich sein
File Allocation Problem - Vergleich zweier Modelle 6
Allgemeines (1)
wir betrachten ein Netzwerk mit
N Knoten
F gespeicherten Dateien
L Verbindungen
i und j identifizieren Knoten in dem
verteilten System
d identifiziert eine Datei
l identifiziert eine Verbindung
File Allocation Problem - Vergleich zweier Modelle 7
Allgemeines (2)
Unterscheidung zwischen
Anfragenbetrifft nur eine Datei bzw. eine Kopie der
Datei
Änderungen um die Konsistenz zu wahren muß eine
Änderung auf allen Kopien erfolgen
der Aufwand von Anfragen und
Änderungen ist unterschiedlich
File Allocation Problem - Vergleich zweier Modelle 8
FAP-WCD
FAP with worst-case delay
Zielfunktion:
die Betriebskosten sollen minimiert
werdenKosten für Datenspeicherung
Kommunikationskosten für die Anfragen
Kommunikationskosten für die Änderungen
File Allocation Problem - Vergleich zweier Modelle 9
FAP-WCD : Zielfunktion
Kosten für die Datenspeicherung
N
j
d
j
F
d
d
j xcZ1 1
1
Kosten der Speicherung für Datei d an Knoten j
= 1, wenn eine Kopie von Datei d im Knoten j existiertfür alle Knoten und
alle Dateien
File Allocation Problem - Vergleich zweier Modelle 10
FAP-WCD : Zielfunktion
Kommunikationskosten für die Anfragen
N
i
F
d
N
j
d
ijij
d
iytQZ
1 1 1
2
Umfang der Anfragen von Knoten i nach Datei d
= 1, wenn ein Anfrage von Knoten i nach Datei d nach j geroutet wird
Kosten für Datentransport von Knoten i nach Knoten j
zwischen allen Knoten und für
jede Datei
File Allocation Problem - Vergleich zweier Modelle 11
FAP-WCD : Zielfunktion
N
jij
d
j
N
i
F
d
d
i txUZ11 1
3
Kommunikationskosten für die Änderungen
Umfang der Änderungen die von Knoten i aus, an der Datei
d durchgeführt werden
Daten müssen auf allen Kopien geändert werden
für alle Knoten und alle Dateien
falls auf Knoten j eine Kopie existiert, muß eine Daten-
transfer von i nach j erfolgen
File Allocation Problem - Vergleich zweier Modelle 12
FAP-WCD : Zielfunktion
tUc ij
N
i
d
i
d
j
d
j
1 )31( ZZ
yxd
ij
N
i
F
d
N
j
d
ij
d
j
N
j
F
d
d
jZ
1 1 11 1
Kosten die abhängig von den sindx
d
j
Kosten die abhängig von den sindy
d
ij
tQ ij
d
i
d
ij )2(Z
File Allocation Problem - Vergleich zweier Modelle 13
FAP-WCD : Nebenbedingungen
11
N
j
d
ijy di, )1(
0 yxd
ij
d
j jdi ,, )2(
jede Anfrage von Knoten i nach Datei d muss genau einmal bedient werden
eine Anfrage nach d kann genau dann von Knoten j erfüllt werden, wenn es eine Kopie von d in j gibt
File Allocation Problem - Vergleich zweier Modelle 14
FAP-WCD : Nebenbedingungen
Twy d
iij
N
j
d
ij
1di, )3(
CQy l
ji
d
i
d
ij
Pl
,
ˆ l )4(
die worst-case-Antwortzeit einer Anfrage von Knoten i nach Datei d, muss kleiner oder gleich der maximal akzeptablen Antwortzeit sein
das maximale Übertragungsvolumen darf nicht größer sein als die Bandbreite der Verbindung
File Allocation Problem - Vergleich zweier Modelle 15
FAP-WCD : Nebenbedingungen
CAPxS j
d
j
F
d
d 1
j )5(
}1,0{, yxd
ij
d
j)6(
die an Knoten j gespeicherten Dateien dürfen die Kapazität des Knotens nicht überschreiten
File Allocation Problem - Vergleich zweier Modelle 16
FAP-WCD : Nebenbedingungen
einige Variablen lassen sich schon jetzt festlegen
CAPS j
d 0 xd
j0 y
d
ij
Twd
iij 0 y
d
ij
Nach diesen Festlegungen dominiert Nebenbedingung (1) Nebenbedingung (3)
Nebenbedingung (3) ist redundant
File Allocation Problem - Vergleich zweier Modelle 17
Exkurs: Lagrange Relaxation
gegeben: ein Optimierungsproblem
z* = min cTx
u.d.N. Ax b
x X
alle Restriktionen, die man vernachlässigt, werden mit dem Lagrange Multiplikator in die Zielfunktion aufgenommen
z* = min cTx + (Ax-b)
u.d.N. x X
File Allocation Problem - Vergleich zweier Modelle 18
Exkurs: Lagrange Relaxation
als Lagrange-Funktion erhält man
L() = min {cTx + (Ax-b) : xX}
Für jeden Vector 0 stellt L() eine
untere Schranke für das Optimierungs-
problem dar
als neues Optimierungsproblem ergibt sich
L* = max L()
Falls (Ax-b) = 0 ist, ist L* sogar optimal
File Allocation Problem - Vergleich zweier Modelle 19
Exkurs: Lagrange Relaxation
ZUB
L(k)
File Allocation Problem - Vergleich zweier Modelle 20
Exkurs: Subgradientenmehode
Bestimmung von
k+1 = k + k(Axk-b)
k gibt die Schrittweite an mit der man sich in die Richtung des Subgradienten bewegt
Bestimmung von k
bAx
LZk
UB
k
k
k
20 k
File Allocation Problem - Vergleich zweier Modelle 21
FAP-WCD (Wdh.)
yxd
ij
N
i
F
d
N
j
d
ij
d
j
N
j
F
d
d
jZ
1 1 11 1min
u.d.N
11
N
j
d
ijy)1(
0 yxd
ij
d
j)2(
cQy l
ji
d
i
d
ij
Pl
,
ˆ)4(
CAPxS j
d
j
F
d
d 1
)5(
}1,0{, yxd
ij
d
j)6(
File Allocation Problem - Vergleich zweier Modelle 22
FAP-WCD nach einer Lagrange Relaxation für die
Bedingungen (1) und (4) erhält man
L
l ji
ld
i
d
ijl
N
i
F
d
N
j
d
ij
d
i
D
P
wu
lcQyw
yuZZ
1 ,
1 1 1
ˆ*
1
min,
u.d.N (2), (5) und (6)
ZD(u,w) liefert eine untere Schranke
File Allocation Problem - Vergleich zweier Modelle 23
für feste u und w ist ZD(u,w) einfach zu
bestimmen
FAP-WCD
yd
ij
xd
j
ist jetzt nur noch in der Bed. (2) enthalten und wir durch nach oben beschränkt
yd
ij
yd
ij
Koeffizienten vor dem sind unabhängig, deshalb lassen sich die durch einen Koeffizientenvergleich bestimmen
yd
ijxd
j
falls die Summe der Koeffizienten negativ ist, wird auf gesetzt
File Allocation Problem - Vergleich zweier Modelle 24
FAP-WCD
wir benötigen eine zulässige Lösung (bzw. obere Schranke) für die Bestimmung der Schrittweite
eine Anfangslösung liefert eine initiale Heuristik die aus zwei Phasen bestehtAddDrop
File Allocation Problem - Vergleich zweier Modelle 25
Initiale Heuristik : Add-Drop
Addes wird versucht, möglichst viele
Anfragen lokal zu befriedigen, ohne jedoch die Kapazität der Knoten zu überschreiten
wenn eine zulässige Lösung gefunden ist, beginnt die Phase Drop
Dropes werden solange die Kopien gelöscht,
die die Kosten am meisten reduzieren, bis eine Bedingung verletzt würde
File Allocation Problem - Vergleich zweier Modelle 26
Lagrange Relaxation
nach Add-Drop habe wir eine zulässige Lösung, die eine obere Schranke darstellt
durch die jetzt folgende Lagrange Relaxation, können die Bed. (1) und (4) verletzt sein
falls Bed. (4) verletzt ist werden Verbindungen überlastet
eine zulässige Lösung kann durch Heuristik 2 gefunden werden
File Allocation Problem - Vergleich zweier Modelle 27
Heuristik 2
für die Verbindungen die überlastet sind werden alle Anfragen ermittelt die diese Verbindung benutzten
diese werden nach dem Volumen der Anfragen sortiert
um eine zulässige Lösung zu erhalten versucht man, die Anfragen mit dem höchsten Volumen lokal zu befriedigen
0yd
ij1y
d
ii1x
d
i
File Allocation Problem - Vergleich zweier Modelle 28
Heuristik 3
wird durchgeführt, wenn die Bedingung (1) verletzt wird
zwei Möglichkeiten für Verletzung
Anfragen werden von mehreren Knoten bedient
die Anfrage wird von dem Knoten
erfüllt, zu dem die geringsten Kommunikationskosten entstehen
File Allocation Problem - Vergleich zweier Modelle 29
Heuristik 3
Anfrage wird von keinem Knoten bedient für alle Knoten, die eine Kopie der
nachgefragten Datei haben, wird geprüft, ob es eine Verbindung dorthin gibt, die nicht ausgelastet ist
falls es keine Verbindung gibt wird die
Anfrage lokal erledigt
sonst wird sie von dem Knoten erledigt,
zu dem die geringsten Kosten entstehen
File Allocation Problem - Vergleich zweier Modelle 30
Ablauf
Anfangslösung, liefert Add-Drop
Untere Schranke durch Lagrange
Relaxation
neue obere Schranke durch Heuristik 2 und
Heuristik 3
neue untere Schranke durch Subgradienten-
verfahren
File Allocation Problem - Vergleich zweier Modelle 31
Branch and Bound
DFS
die obere Schranke wird initial durch Add-Drop bestimmt, und wird an jedem Knoten durch die Heuristiken 2 und 3 verbessert
die untere Schranke wird an jedem Knoten durch die Subgradientenmethode ermittelt
der Baum entwickelt sich anhand der y Variablen
File Allocation Problem - Vergleich zweier Modelle 32
FAP-AD
FAP with avarage delay
Das Problem ist identisch zum FAP-WCD der einzige Unterschied ist, dass jetzt die
durchschnittliche Antwortzeit betrachtet wirddie durchschnittliche Antwortzeit einer
Anfrage von Knoten i nach Datei d muss kleiner oder gleich der maximal akzeptablen Antwortzeit sein
File Allocation Problem - Vergleich zweier Modelle 33
FAP-AD
die Zielfunktion und die Neben-bedingungen bleiben gleich
als einzige Nebenbedingung ändert sich Bed. (3)
Tay d
iij
N
j
d
ij
1di, )3( a
durchschnittliche Antwortzeit für Kommunikation zwischen Knoten i und j
File Allocation Problem - Vergleich zweier Modelle 34
FAP-AD
die worst-case Antwortzeit ist konstant die durchschnittliche Antwortzeit ist eine
Funktion, die abhängig vom Netzwerkfluß ist
daher muß die Vorgehensweise angepaßt werden
die Arbeit wird aufgeteilt auf zwei Komponenten OptimiererSimulator
File Allocation Problem - Vergleich zweier Modelle 35
FAP-AD : Optimierer
der Optimierer führt die gleichen Schritte aus, die auch für das Lösen des FAP-WCD nötig waren
er stoppt jedoch an der Stelle, wo Branch-and-Bound aufgerufen wird
an dieser Stelle haben wir eine Lösung die alle Bedingungen erfüllt, außer die neue Bedingung, die die durchschnittliche Antwortzeit betrifft
File Allocation Problem - Vergleich zweier Modelle 36
FAP-AD : Simulator
die gefundene Lösung wird an den
Simulator übergeben, falls sie besser als
die aktuelle ist
der Simulator generiert die durchschnitt-
lichen Antwortzeiten für die gefundene
Lösung
falls die generierten Zeiten die Bed. (3a)
erfüllen, wird die gefundene Lösung als
aktuell beste Lösung übernommen
File Allocation Problem - Vergleich zweier Modelle 37
Laufzeitvergleich: FAP-WCD vs. MPSX
FAP-WCD ist einem Standard-LP-Löser, weit überlegen
der Standard-LP-Löser MPSX hat für dieses Problem eine CPU-Rechenzeit die ca. 10 bis 100 mal länger ist
File Allocation Problem - Vergleich zweier Modelle 38
Vergleich FAP-WCD - FAP-AD
FAP-AD liefert keine optimalen Ergebnisse, da hier nicht der Branch-and-Bound Prozeß durchlaufen wird
die Testergebnisse zeigen im schlimmsten Fall Differenzen von 5% zwischen der oberen und der unteren Schranke
für zwei von 45 Netzwerkkonfigurationen hat FAP-AD keine Lösung gefunden, die die Bedingung für die durchschnittliche Antwortzeit erfüllte
File Allocation Problem - Vergleich zweier Modelle 39
Vergleich FAP-WCD - FAP-AD
die CPU-Rechenzeit von FAP-AD ist im Durchschnitt 2-mal so lang wie die von FAP-WCD
da bei dem Vergleich die Werte für die akzeptable Antwortzeit gleich gewählt worden sind, ist die Bed. (3) in beim FAP-WCD strenger
FAP-WCD produziert in der Regel eine größere Anzahl an Kopien und geringfügig größere Kosten
File Allocation Problem Vergleich zweier Modelle
EndeEnde