Анализ работоспособности и стохастические потоки и длины путей

Предыдущие четыре главы касались мер связности. В контексте коммуникационных сетей базовым предположением для этих мер является то, что до тех пор, пока между двумя узлами имеется соединение, они беспрепятственно могут обмениваться данными. Во многих практических постановках задач это совсем не так. В частности, такие параметры как задержка, длина пути, полоса пропускания и прочее может иметь жизненную важность: сеть не просто должна быть связанной, она должна обеспечивать определенный уровень функциональности. Эта точка зрения ведет к разработке мер работоспособности. Чтобы изучать такие меры, нужна дополнительная информация, такая как длины, пропускные способности каналов, сопряженные с компонентами сети. Кроме того, возможно, что должна быть представлена информация, характеризующая загрузку сети, например, набор требований к трафику между определенными узлами сети. Вообще, объявление ценности такой информации изменяет природу проблемы надежности от вероятностной характеристики состояний типа “исправен/сломан” к оценке, включающей в себя множественные состояния системы и ее компонент. Во многих случаях это просто приводит к более комплексному варианту проблемы двух состояний, но это также включает задачи определения усредненного поведения и/или к введению “непрерывных” состояний и системных переменных, которые требуют существенно других методик решения. Мы обращаемся с этим более общим типом проблемы надежности, как с проблемой многих состояний и намерены ввести меры работоспособности, а также некоторые другие меры (метрики).

Общий формат для проблем сетей со многими состояниями рассматривается в данной статье следующим образом:

У нас есть сеть G=(V,E) с набором случайных переменных {Xe: eОE}, сопряженных со связями (ребрами) этой сети. Значение, присваиваемое случайной переменной ребра, представляет собой параметр, такой как длина пути, пропускная способность или задержка. В большей части данного раздела мы будем предполагать, что каждая случайная переменная связи может принимать q дискретных значений.
Во многих ситуациях случай, когда q=2 (система с двумя состояниями) представляет вполне реалистическую модель. Здесь является обычным называть состояния “плохим” и “хорошим”. В случае “хорошего” состояния связь работает со специфицированной пропускной способностью, длиной и т.д., а в случае “плохого” состояния - канал не работает, имеет нулевую пропускную способность, бесконечную длину и пр. (Случайные величины могут также быть приписаны вершинам графа сети, чтобы охарактеризовать требования в пропускной способности или задержке в узле сети. Мы не касаемся здесь этих моделей, за исключением упоминания того, что они часто моделируются как проблемы со стохастическими параметрами связей). Соответствие вектора

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

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

В контексте анализа работоспособности мы интерпретируем

как метрику работоспособности, когда сеть находится в состоянии

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

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

Содержание раздела