Расчет вероятности сбоя системы в распределенной сети

Question

Я пытаюсь построить математическую модель доступности файла в распределенной файловой системе. Я разместил этот вопрос в MathOverflow, но это может быть классифицировано как CS-вопрос, поэтому я также даю ему шанс.

Система работает следующим образом: узел хранит файл (encoed с использованием кодов стирания) в узлах ремитов r * b, где r - коэффициент репликации, а b - целочисленная константа. Файлы, закодированные с помощью Erasure, обладают свойством, что файл может быть восстановлен, если по крайней мере b из удаленных узлов доступны и вернуть его часть файла.

Простейший подход к этому состоит в том, чтобы предположить, что все удаленные узлы независимы друг от друга и имеют одинаковую доступность p. С учетом этих допущений наличие файла следует за биномиальным распределением, т. Е. Binomial distribution http://bit.ly/dyJwwE

К сожалению, эти два предположения могут ввести ошибку, отличную от нее, как показано в этой статье: http://deim.urv.cat/~lluis.pamies/uploads/Main/icpp09-paper.pdf.

Один из способов преодоления предположения, что все узлы имеют одинаковую доступность, - это рассчитать вероятность каждой возможной комбинации доступного/недоступного узла и взять сумму всех этих результатов (что является тем, что они предлагают в выше, только формально, чем то, что я только что описал). Этот подход можно рассматривать как двоичное дерево с глубиной r * b, и каждый выход - одна из возможных комбинаций доступных/недоступных узлов. Доступность файла - это то же самое, что вероятность того, что вы придете в отпуск с> = b доступными узлами. Этот подход является более правильным, но имеет вычислительную стоимость Ordo http://bit.ly/cEZcAP. Кроме того, это не касается предположения об отсутствии узла.

Есть ли у вас идеи хорошего приближения, которые вводят меньше ошибок, чем биномиальное распределение-аппроксимация, но с лучшей вычислительной стоимостью, чем http://bit.ly/d52MM9 http://bit.ly/cEZcAP?

Вы можете предположить, что данные доступности каждого узла представляют собой набор кортежей, состоящий из (measurement-date, node measuring, node being measured, succes/failure-bit). С помощью этих данных можно, например, рассчитать соотношение доступности между узлами и дисперсию доступности.

Answer 1

Для больших r и b вы можете использовать метод, называемый интеграцией Монте-Карло, см., Например, Monte Carlo integration on Wikipedia (и/или глава 3.1.2 SICP) для вычисления суммы. Для небольших r и b и значительно отличающихся вероятностей отказа узлов p[i] точный метод превосходит. Точное определение small и большое будет зависеть от нескольких факторов и наилучшим образом испытать эксперимент.

Специальный код образца: Это очень простой пример кода (в Python), чтобы продемонстрировать, как такая процедура может работать:

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 

Функция соответствует биномиальному тесту и запускает N тестов, проверяя, есть ли b узлов из r*b узлов с вероятностью отказа p. Несколько экспериментов убедят вас, что вам нужны значения N в диапазоне тысяч образцов, прежде чем вы сможете получить разумные результаты, но в принципе сложность O(N*r*b). Точность результата оценивается как sqrt(N), т. Е. Для повышения точности в два раза вам необходимо увеличить коэффициент N в четыре раза. Для достаточно большого r*b этот метод будет явно превосходить.

Расширение аппроксимации: Вам, очевидно, необходимо разработать тестовый корпус таким образом, чтобы он учитывал все свойства системы. Вы предложили пару расширений, некоторые из которых могут быть легко реализованы, а другие - нет. Позвольте мне дать вам несколько предложений:

1) В случае отличных, но некоррелированных p[i] изменения в приведенном выше коде минимальны: в головке функции вы передаете массив вместо одного поплавка p, и вы заменяете линия if random.random()<p: alivenum += 1 по

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

2) В случае коррелированных p[i] Вам необходима дополнительная информация о системе. Ситуацией я имел в виду в моем комментарии может быть сетью, как это:

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

В этом случае A может быть «корневой узел» и отказ узла D может означать автоматический отказ с 100% вероятностью узлы F, G, H и J; в то время как сбой узла F автоматически снизит G, H и J и т. д. По крайней мере, это был случай, о котором я говорил в своем комментарии (что является правдоподобной интерпретацией, поскольку вы говорите о древовидной структуре вероятностей в исходном вопросе) , В такой ситуации вам потребуется изменить код, который p относится к древовидной структуре, а for j in ... обходит дерево, пропуская нижние ветви с текущего узла, как только тест завершится с ошибкой. Итоговый тест по-прежнему остается, конечно, как alivenum >= b.

3) Этот подход потерпит неудачу, если сеть представляет собой циклический граф, который не может быть представлен древовидной структурой. В таком случае вам нужно сначала создать узлы графа, которые либо мертвы, либо живы, а затем запустить алгоритм маршрутизации на графике, чтобы подсчитать количество уникальных достижимых узлов. Это не увеличит сложность времени алгоритма, но, очевидно, сложность кода.

4) Зависимость времени - это нетривиальная, но возможная модификация, если вы знаете mtbf/r (среднее время между ошибками/ремонт), поскольку это может дать вам вероятности p либо древовидной структуры, либо некоррелированный линейный номер p[i] на сумму экспонент. Затем вам нужно будет запустить MC-процедуру в разное время с соответствующими результатами для p.

5) Если у вас есть только файлы журнала (как указано в последнем абзаце), для этого потребуется существенная модификация подхода, который выходит за рамки того, что я могу сделать на этой плате. Журнальные файлы должны быть достаточно тщательными, чтобы можно было восстановить модель для сетевого графика (и, следовательно, график p), а также отдельные значения всех узлов p. В противном случае точность будет ненадежной. Эти лог-файлы также должны быть значительно длиннее, чем временные шкалы сбоев и ремонта, допущения, которые могут быть нереалистичными в реальных сетях.

Answer 2

Предполагая, что каждый узел имеет постоянную, известную и независимую доступность, подход «Разделить и завоевывать» приходит на ум.

Скажите, у вас есть N узлы.

1. Разделить их на два набора N/2 узлов.
2. Для каждой стороны вычислите вероятность того, что любое количество узлов ([0,N/2]) будет опущено.
3. Умножьте и суммируйте их по мере необходимости, чтобы найти вероятность того, что любое число ([0,N]) полного набора не работает.

Шаг 2 может быть выполнен рекурсивно и на верхнем уровне, который вы можете суммировать, поскольку нужно найти, как часто больше, чем некоторое число.

Я не знаю, сложность этого, но если я должен догадаться, я бы сказал, на уровне или ниже O(n^2 log n)

---

Механика это можно проиллюстрировать на корпусе терминала. Скажем, у нас есть 5 узлов с разворотом . Мы можем разделить его на сегменты A с и B с . Затем мы можем обработать их, чтобы найти "N узлов до" раз для каждого сегмента:

: с

Для B:

конечных результатов для этой стадии может быть найден путем умножения каждого из a-х лет с каждым из b-х и суммируя соответствующим образом.

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]