File Allocation Problem- Vergleich von zwei Methoden unter

 Documents

 162 views
of 40
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
File Allocation Problem Vergleich zweier Modelle Stefan Nolting Inhalt File Allocation Problem FAP with worst-case delay  Zielfunktion …
Share
Transcript
File Allocation Problem Vergleich zweier Modelle Stefan Nolting Inhalt File Allocation Problem FAP with worst-case delay  Zielfunktion  Nebenbedingungen  Lösungsweg Exkurs: Lagrange Relaxation FAP with average delay Vergleich FAP-WCD / FAP-AD File Allocation Problem - Vergleich zweier Modelle 2 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 werden Wege stehen vorher eindeutig fest  stellt ein wichtiges Kriterium beim Design eines verteilten Filesystems dar File Allocation Problem - Vergleich zweier Modelle 3 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 4 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 Anfragen die zulässigen Antwortzeiten für verschiedene Anfragen und Dateien können unterschiedlich sein File Allocation Problem - Vergleich zweier Modelle 5 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 6 Allgemeines (2) Unterscheidung zwischen Anfragen betrifft 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 7 FAP-WCD FAP with worst-case delay Zielfunktion: die Betriebskosten sollen minimiert werden Kosten für Datenspeicherung Kommunikationskosten für die Anfragen Kommunikationskosten für die Änderungen File Allocation Problem - Vergleich zweier Modelle 8 FAP-WCD : Zielfunktion Kosten für die Datenspeicherung Kosten der Speicherung für Datei d an Knoten j N F Z1   c j  x j d d j 1 d 1 = 1, wenn eine Kopie von Datei d im Knoten j existiert für alle Knoten und alle Dateien File Allocation Problem - Vergleich zweier Modelle 9 FAP-WCD : Zielfunktion Kommunikationskosten für die Anfragen = 1, wenn ein Anfrage von Umfang der Anfragen von Knoten i nach Datei d Knoten i nach Datei d nach j geroutet wird N F N Z 2   Q  t ij  y d d i ij i 1 d 1 j 1 zwischen allen Kosten für Datentransport Knoten und für von Knoten i nach Knoten j jede Datei File Allocation Problem - Vergleich zweier Modelle 10 FAP-WCD : Zielfunktion Kommunikationskosten für die Änderungen Umfang der Änderungen die Daten müssen auf allen von Knoten i aus, an der Datei Kopien geändert werden d durchgeführt werden  NN  F Z 3  U i   x j  t ij  d d i 1 d 1  j 1  falls auf Knoten j eine Kopie für alle Knoten existiert, muß eine Daten- und alle Dateien transfer von i nach j erfolgen File Allocation Problem - Vergleich zweier Modelle 11 FAP-WCD : Zielfunktion N   c j  U i  t ij d d d j ( Z1  Z 3) i 1 Kosten die abhängig d von den x j sind  d  Q  t ij d ij i (Z 2) Kosten die abhängig d von den y ij sind N F N F N Z      y d   d d d j 1 d 1 j x j i 1 d 1 j 1 ij ij File Allocation Problem - Vergleich zweier Modelle 12 FAP-WCD : Nebenbedingungen N y d 1 i, d (1) ij j 1 jede Anfrage von Knoten i nach Datei d muss genau einmal bedient werden d x y 0 d j ij i , d , j ( 2) 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 13 FAP-WCD : Nebenbedingungen N  y w T d d ij ij i i, d (3) j 1 die worst-case-Antwortzeit einer Anfrage von Knoten i nach Datei d, muss kleiner oder gleich der maximal akzeptablen Antwortzeit sein  y  Qˆ  C d d l l ij i l ( 4) i , j P das maximale Übertragungsvolumen darf nicht größer sein als die Bandbreite der Verbindung File Allocation Problem - Vergleich zweier Modelle 14 FAP-WCD : Nebenbedingungen F  S  x  CAP d d j j j (5) d 1 die an Knoten j gespeicherten Dateien dürfen die Kapazität des Knotens nicht überschreiten d {0,1} d x ,y j ij ( 6) File Allocation Problem - Vergleich zweier Modelle 15 FAP-WCD : Nebenbedingungen einige Variablen lassen sich schon jetzt festlegen d S  CAP  xj  0 d d j  y 0 ij d w T d ij i  y 0 ij Nach diesen Festlegungen dominiert Nebenbedingung (1) Nebenbedingung (3)  Nebenbedingung (3) ist redundant File Allocation Problem - Vergleich zweier Modelle 16 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 17 Exkurs: Lagrange Relaxation als Lagrange-Funktion erhält man L() = min {cTx + (Ax-b) : xX} 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 18 Exkurs: Lagrange Relaxation ZUB L(k)  File Allocation Problem - Vergleich zweier Modelle 19 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  k   k   k   Z UB  L      0  2 k Ax b k File Allocation Problem - Vergleich zweier Modelle 20 FAP-WCD (Wdh.) N F N F N Z     x j    y d d d d min j ij ij j 1 d 1 i 1 d 1 j 1 u.d.N F  S  x  CAP N y d d d (1) 1 (5) j j ij d 1 j 1 d {0,1} d d ( 2) x y d j ij 0 ( 6) x ,y j ij  y  Qˆ  c d d l ( 4) ij i l i , jP File Allocation Problem - Vergleich zweier Modelle 21 FAP-WCD nach einer Lagrange Relaxation für die Bedingungen (1) und (4) erhält man  N F d  N    Z   u i    yij  1  d  i 1 d 1  j 1   Z D u, w  min  L     ˆ  d   wl   l yij Qi c  d    l *  l 1  i , jP  u.d.N (2), (5) und (6) ZD(u,w) liefert eine untere Schranke File Allocation Problem - Vergleich zweier Modelle 22 FAP-WCD für feste u und w ist ZD(u,w) einfach zu bestimmen  yij ist jetzt nur noch in der Bed. (2) d enthalten und wir durch x j nach oben d beschränkt Koeffizienten vor dem yij sind unabhängig, d deshalb lassen sich die yij durch einen d Koeffizientenvergleich bestimmen falls die Summe der Koeffizienten negativ ist, wird yij auf x j gesetzt d d File Allocation Problem - Vergleich zweier Modelle 23 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 besteht Add Drop File Allocation Problem - Vergleich zweier Modelle 24 Initiale Heuristik : Add-Drop Add es 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 Drop es werden solange die Kopien gelöscht, die die Kosten am meisten reduzieren, bis eine Bedingung verletzt würde File Allocation Problem - Vergleich zweier Modelle 25 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 26 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 d 1 d  d y 0 y 1 x i ij ii File Allocation Problem - Vergleich zweier Modelle 27 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 28 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 29 Ablauf Anfangslösung, liefert Add-Drop neue obere Schranke durch Heuristik 2 und Heuristik 3 Untere Schranke durch Lagrange Relaxation neue untere Schranke durch Subgradienten- verfahren  File Allocation Problem - Vergleich zweier Modelle 30 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 31 FAP-AD FAP with avarage delay Das Problem ist identisch zum FAP-WCD der einzige Unterschied ist, dass jetzt die durchschnittliche Antwortzeit betrachtet wird die 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 32 FAP-AD die Zielfunktion und die Neben- bedingungen bleiben gleich als einzige Nebenbedingung ändert sich Bed. (3) N  y a T d d ij ij i i, d (3a ) j 1 durchschnittliche Antwortzeit für Kommunikation zwischen Knoten i und j File Allocation Problem - Vergleich zweier Modelle 33 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 Optimierer Simulator File Allocation Problem - Vergleich zweier Modelle 34 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 35 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 36 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 37 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 38 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 39 File Allocation Problem Vergleich zweier Modelle Ende
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks