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

сумма информационных потоков от всех узлов, предшествующих узлу i на путях от концевых
вершин к корню дерева, и потока hi, формируемого объектом xi.
      Задача синтеза древовидной сети впервые рассматривалась в работе Прима, в которой
предложен точный алгоритм синтеза сети минимальной стоимости, но без учета ограничений
на пропускные способности линий связи и, как следствие, на суммарный поток, передаваемый
по ветвям. Вместе с тем доказано, что алгоритм доставляет оптимальное решение и состоит из
следующих шагов. Пусть первоначально рассматривается исходное множество несвязанных
объектов (вершин) X={xi}.
      1. Выбирается произвольная вершина (подграф) xi и определяется стоимость введения
ребра (i, j), связывающего xi с некоторым подграфом xj: cij.
      2. Если подграфы xi и xj состоят из нескольких вершин, то выбирается ребро, достав-
ляющее топологическое расстояние между подграфами (минимум из всех пар возможных рас-
стояний): среди всех пар (i, j) определяется такая пара (i*, j*), для которой
                                           ci*j* = min cij.
                                                   ∀(i,j)
      3. Подграфы xi* и xj* объединяются в один: xij*= xi*∪xj*. На этом итерация алгоритма
Прима завершается, а сами итерации повторяются до тех пор, пока имеются изолированные
подграфы (их количество на каждой итерации уменьшается на единицу).

      2.2.4. Метод насыщения сечения

      Рассмотрим метод насыщения сечения (сечением называется множество узлов и линий,
удаление которых разбивает сеть на две несвязные части). Предположим, что нагрузка в сети
увеличивается до предела. Начиная с некоторого момента алгоритм маршрутизации или ис-
пользуемая процедура распределения потоков станет направлять потоки по альтернативным
путям, пока в сети не образуется сечение из почти насыщенных линий. Далее увеличение неко-
торых потоков в сети будет сопровождаться чрезмерным увеличением задержки. Появившееся
сечение отражает слабость топологии сети, которую можно улучшить, добавив еще одну ли-
нию, соединяющую узлы, находящиеся с двух сторон сечения. Как правило, новая линия долж-
на соединять узлы, находящиеся, по крайней мере, на расстоянии двух шагов от краев сечения.
      Опытный разработчик обычно умеет находить такие варианты топологий сети, которые
оказываются значительно лучше вариантов, найденных с помощью какой-нибудь простой про-
граммы, поэтому одним из наиболее мощных инструментов разработки топологии является со-
четание метода насыщения сечений с интуицией разработчика, время от времени корректи-
рующего работу программы.

      2.3. Иерархические сети и сети с неоднородной средой

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


                                               26