Примеры сетевых топологий


Методики ограничений


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

Исторически первой использовалась методика для аппроксимации надежности в стохастических сетях и среди них одна, которой уделялось наибольшее внимание, возникает из интуитивно привлекательной идеи, что ожидаемое значение E[Ф] длины кратчайшего пути/максимального потока/времени завершения может быть получено путем замены случайной длины/максимального потока/времени завершения для каждого ребра на детерминистский параметр, чье значение равно ожидаемой величине, и последующего решения детерминистского варианта проблемы. Это было фактически методикой решения, предложенной в оригинальном рассмотрении PERT в работе Малькольма и др. [D.G.Malcolm et al, “Application of a technique for research and development program evaluation”, Oper. Res. 7 (1959), 646-669]. Кажется фольклором то, что значение, полученное с помощью этой методики является верхней границей истинного значения ЕФ в проблеме PERT и нижней границей в проблемах наикратчайшего пути и максимального потока.

Наиболее успешные исследования концентрируются вокруг аппроксимации значения cdf F(a) =Pr[ФЈa] для Ф. Методика вначале была применена к проблеме PERT с непрерывными значениями параметров ребер, но может быть модифицирована для применения к проблемам кратчайшего пути, наибольшего потока и для случайных переменных ребра с дискретным распределением. В частности, предположим, что нужно вычислить число a, для которого FPERT(a)=b для некоторой специфицированной вероятности b. Заменяем каждую случайную переменную ребра Те на te, для которого Pr[TeЈ te]= b, и решаем для детерминистского значения наикратчайшего времени завершения. Полученная величина снова является верхней границей действительного времени завершения проекта, выдавая cdf значения b.




Начало  Назад  Вперед



Книжный магазин