Проектирование реляционных баз данных. Ковалев А.В - 29 стр.

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

      2.4.4. Метод исключения ветвей при выпуклой функции стоимости

      В предыдущем разделе рассмотрено применение метода девиации потока к решению за-
дачи выбора пропускных способностей каналов и распределения потоков в предположении, что
стоимость линии связи пропорциональна ее пропускной способности. В этом методе потоки
направляются согласно весам, представляющим увеличение задержки сообщений при увеличе-
нии нагрузки в каналах сети. Если поток в канале становится малым, то пропускная способ-
ность также мала и приращение стоимости при увеличении потока становится большим. Как
следствие, происходит дальнейшее уменьшение потока в канале. Такие каналы в процессе ра-
боты алгоритма пытаются избавиться от проходящих по ним компонент потока; канал с нуле-
вым потоком приобретает вес и в дальнейшем не используется.
      На этих соображениях основывается метод оптимизации топологии, в котором в качестве
начальной берут сильносвязную сеть, методом девиации потоков решают задачу распределения
потоков и выбора пропускных способностей каналов и в получившемся решении в сети сохра-
няют лишь линии с ненулевыми потоками. Эти линии и образуют искомую топологию.
      Оптимизацию топологии сети путем исключения линий можно проводить и в том случае,
когда зависимость между стоимостью линии и ее пропускной способностью задается выпуклой
функцией. На самом деле существует ограниченный набор возможных пропускных способнос-
тей для линий связи, и их стоимости образуют возрастающую ступенчатую функцию. Заменив
для удобства анализа эту кривую непрерывной выпуклой функцией, можно применить метод
девиации потоков для исключения линий из сильносвязной сети. При этом не следует забывать
требований минимальной связности сети и нарушать ее удалением слишком большого числа
линий. Такой метод оптимизации топологии сетей известен под названием "метод исключения
ветвей при выпуклой функции стоимости". Установлено, что данный метод дает достаточно
хорошие результаты, однако порождаемые им топологии сильно зависят от вида функции стои-
мость-пропускная способность.

      2.5. Оценка надежности и коэффициента готовности

      Преимуществом ячеистых сетей передачи данных по сравнению с радиальными, кольце-
выми и древовидными является их повышенная устойчивость к возможным отказам линий свя-
зи. Следует отметить, что отказ узлов сети также сильно влияют на работоспособность, и поэ-
тому понятие связности, учитывающее узлы и линии, следовательно, является более точной
мерой надежности сети, чем реберная связность, учитывающая только состояние линий. Тем не
менее для простоты изложения будем рассматривать только отказ линий связи. Учет совмест-
ного влияния отказов узлов и линий связи более сложен, однако не вносит принципиальных
отличий.
      В простейшем случае можно считать, что отказ и восстановление работоспособности ка-
ждой линии происходят независимо от остальных, так что ее можно описать единственным па-
раметром p, который означает вероятность того, что линия неисправна. Основная цель - выра-
зить характеристику надежности сети как функцию от параметра p и топологии сети. Характе-
ристику надежности сети можно определить различными способами. Например, можно опреде-
лить ее как долю времени, в течение которого два узла соединены друг с другом, усредненного

                                               31