File Allocation Problem Vergleich zweier Modelle

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 (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


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)


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


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


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


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


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



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



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



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


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



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



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



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



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



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



ZUB

L(k)


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


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(


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

Documents

File Allocation Problem Vergleich zweier Modelle