Berechnung der Wahrscheinlichkeit eines Systemausfalls in einem verteilten Netzwerk

Question

Ich versuche, ein mathematisches Modell für die Verfügbarkeit einer Datei in einem verteilten Dateisystem zu erstellen. Ich habe diese Frage bei Mathoverflow gepostet, aber dies könnte genauso gut als CS-Frage eingestuft werden, also mache ich sie auch hier.

Das System funktioniert wie folgt: Ein Knoten speichert eine Datei (mit Löschcodes mit Löschcodes) an R*B-Fernbedienungsknoten, wobei R der Replikationsfaktor und B eine ganzzahlige Konstante ist. Auslöser-codierter Dateien haben die Eigenschaft, dass die Datei mindestens B der Remote-Knoten zur Verfügung gestellt werden kann und ihren Teil der Datei zurückgibt.

Der einfachste Ansatz hierfür ist anzunehmen, dass alle entfernten Knoten unabhängig voneinander sind und die gleiche Verfügbarkeit haben p. Mit diesen Annahmen folgt die Verfügbarkeit einer Datei der Binomialverteilung, dh Binomialverteilung http://bit.ly/dyjwwe

Leider können diese beiden Annahmen einen nicht negativen Fehler einführen, wie in diesem Artikel gezeigt: http://deim.urv.cat/~lluis.pamies/uploads/main/icpp09-paper.pdf.

Eine Möglichkeit, die Annahme zu überwinden, dass alle Knoten die gleiche Verfügbarkeit haben, besteht darin, die Wahrscheinlichkeit jeder möglichen Kombination aus Verfügbarkeit/nicht verfügbarem Knoten zu berechnen und die Summe all dieser Ergebnisse zu übernehmen (was sie in dem oben genannten Artikel vorschlagen. Nur formaler als das, was ich gerade beschrieben habe). Sie können diesen Ansatz als Binärbaum mit Tiefe r*b sehen und jeder Urlaub ist eine mögliche Kombination aus verfügbaren/nicht verfügbaren Knoten. Die Verfügbarkeit der Datei ist dasselbe wie die Wahrscheinlichkeit, dass Sie mit> = B verfügbaren Knoten ankommen. Dieser Ansatz ist korrekter, hat aber rechnerische Kosten von Ordo http://bit.ly/cezcap. Außerdem geht es nicht mit der Annahme der Knotenunabhängigkeit.

Habt ihr Ideen für eine gute Annäherung, die weniger Fehler einführt als die Binomialverteilungsaproximation, aber mit besseren Rechenkosten als mit besseren Rechenkosten http://bit.ly/d52mm9 http://bit.ly/cezcap?

Sie können davon ausgehen, dass die Verfügbarkeitsdaten jedes Knotens ein Satz von Tupeln ist, die aus bestehen (measurement-date, node measuring, node being measured, succes/failure-bit). Mit diesen Daten können Sie beispielsweise die Korrelation der Verfügbarkeit zwischen den Knoten und der Verfügbarkeitsvarianz berechnen.

Answer 1

Für große r und b Sie können eine Methode namens Monte-Carlo-Integration verwenden, siehe EG Integration von Monte Carlo auf Wikipedia (und/oder Kapitel 3.1.2 von SICP), um die Summe zu berechnen. Für kleine r und b und signifikant unterschiedliche Node-Failure-Wahrscheinlichkeiten p[i] Die genaue Methode ist überlegen. Die genaue Definition von klein und groß Wird von einigen Faktoren abhängen und wird am besten experimentell ausprobiert.

Spezifischer Beispielcode: Dies ist ein sehr grundlegender Beispielcode (in Python), um zu demonstrieren, wie ein solches Verfahren funktionieren könnte:

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

Die Funktion entspricht dem Binomial -Testfall und wird ausgeführt N Tests, prüfen Sie, ob b Knoten raus r*b Knoten leben mit einer Wahrscheinlichkeit eines Versagens von p. Ein paar Experimente werden Sie davon überzeugen, dass Sie Werte benötigen N Im Bereich von Tausenden von Stichproben, bevor Sie alle angemessenen Ergebnisse erzielen können, aber im Prinzip ist die Komplexität O(N*r*b). Die Genauigkeit des Ergebniss skaliert als sqrt(N), dh die Genauigkeit um einen Faktor von zwei, den Sie erhöhen müssen N um den Faktor vier. Für ausreichend groß r*b Diese Methode wird eindeutig überlegen.

Erweiterung der Näherung: Sie müssen offensichtlich den Testfall so entwerfen, dass er alle Eigenschaften des Systems respektiert. Sie haben einige Erweiterungen vorgeschlagen, von denen einige leicht implementiert werden können, während andere nicht können. Lassen Sie mich Ihnen ein paar Vorschläge geben:

1) Im Fall von unterschiedlichem, aber unkorrelierten p[i], Die Änderungen des obigen Codes sind minimal: Im Funktionskopf geben Sie ein Array anstelle eines einzelnen Floats über p und Sie ersetzen die Linie if random.random()<p: alivenum += 1 durch

if random.random()<p[j]: alivenum += 1

2) im Fall von korreliert p[i] Sie benötigen zusätzliche Informationen zum System. Die Situation, auf die ich mich in meinem Kommentar bezog, könnte ein solches Netzwerk sein:

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

In diesem Fall A könnte der "Wurzelknoten" und ein Fehler des Knotens sein D könnte den automatischen Versagen mit 100% Wahrscheinlichkeit von Knoten implizieren F, G, H und J; während ein Fehler des Knotens F würde automatisch senken G, H und J usw. Zumindest war dies der Fall, auf den ich mich in meinem Kommentar bezogen hatte (was eine plausible Interpretation ist, da Sie in der ursprünglichen Frage über eine Baumstruktur von Wahrscheinlichkeiten sprechen). In einer solchen Situation müssen Sie den Code ändern, den p bezieht sich auf eine Baumstruktur und for j in ... durchquert den Baum und überspringt die unteren Zweige aus dem aktuellen Knoten, sobald ein Test fehlschlägt. Der resultierende Test ist immer noch, ob alivenum >= b wie zuvor natürlich.

3) Dieser Ansatz fällt fehl, wenn das Netzwerk ein zyklischer Diagramm ist, das nicht durch eine Baumstruktur dargestellt werden kann. In einem solchen Fall müssen Sie zuerst Graphenknoten erstellen, die entweder tot oder lebendig sind, und dann einen Routing -Algorithmus im Diagramm ausführen, um die Anzahl der eindeutigen, erreichbaren Knoten zu zählen. Dies erhöht die Zeitkomplexität des Algorithmus nicht, aber offensichtlich die Codekomplexität.

4) Zeitabhängigkeit ist eine nicht triviale, aber mögliche Änderung, wenn Sie die MTBF/R (Mean-Times-Between-Failures/Reparaturen) kennen, da dies Ihnen die Wahrscheinlichkeiten geben kann p entweder der Baumstruktur oder der unkorrelierten Linear p[i] durch eine Summe von Exponentialen. Anschließend müssen Sie die MC-Procedure zu unterschiedlichen Zeiten mit den entsprechenden Ergebnissen für ausführen p.

5) Wenn Sie lediglich die Protokolldateien haben (wie in Ihrem letzten Absatz angedeutet), erfordert dies eine wesentliche Änderung des Ansatzes, der über das hinausgeht, was ich auf diesem Board tun kann. Die Protokolldateien müssten ausreichend gründlich sein, um ein Modell für das Netzwerkdiagramm zu rekonstruieren (und damit der Diagramm von p) sowie die individuellen Werte aller Knoten von p. Andernfalls wäre die Genauigkeit unzuverlässig. Diese Protokolldateien müssten auch wesentlich länger sein als die Zeitskalen von Ausfällen und Reparaturen, eine Annahmen, die in realen Netzwerken möglicherweise nicht realistisch sind.

Answer 2

Unter der Annahme, dass jeder Knoten eine konstante, bekannte und unabhängige Verfügbarkeitsrate aufweist, kommt ein Klassifik- und Eroberer -Ansatz in den Sinn.

Sagen Sie, Sie haben N Knoten.

1. Teilen Sie sie in zwei Sätze von N/2 Knoten.
2. Berechnen Sie für jede Seite die Wahrscheinlichkeit, dass eine beliebige Anzahl von Knoten ([0,N/2]) sind unten.
3. Multiplizieren Sie diese und summieren Sie diese nach Bedarf, um die Wahrscheinlichkeit einer beliebigen Zahl zu ermitteln (([0,N]) des vollständigen Satzes ist unten.

Schritt 2 kann rekursiv durchgeführt werden und auf der oberen Ebene können Sie so summieren, wie oft mehr als einige Anzahl gesunken sind.

Ich kenne die Komplexität nicht, aber wenn ich raten muss, würde ich bei oder unten sagen, ich würde sagen O(n^2 log n)

---

Die Mechanik kann in einem Terminalfall dargestellt werden. Sagen Sie, wir haben 5 Knoten mit Up -Zeiten . Wir können dies in Segmente aufteilen A mit und B mit . Anschließend können wir diese verarbeiten, um die "n Knoten Up" -Zeiten für jedes Segment zu finden:

Für ein:

Für b:

Die endgültigen Ergebnisse für diese Phase finden Sie durch Multiplizieren der einzelnen der der der a's mit jedem der b's und angemessen zusammenfassen.

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]