сети, с, где n-число дуг топологии, 7l4i0- интенсивность потока в i-й линии связи, c4i0- пропускная способность i-й линии связи, n- число линий связи, 7g0- суммарный входной трафик сети.

Рассмотрим некоторые эвристические алгоритмы синтеза структур распределенных информационных сетей.

Метод "насыщения сечения" (НС)

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

необходимо увеличить. Это можно сделать либо увеличив пропускную способность ветвей, либо добавляя ветви к сечению.

Алгоритм НС "пытается" удержать производительность сети в определенных границах при итеративном снижении общей стоимости линий и соблюдении ограничений на пропускные способности, задержку и надежность сети. Если N410 и N420 - число узлов в каждом из компонентов, разделенных множеством ветвей сечения, к -

число ветвей в сечении, и трафик равномерно распределен между узлами, то верхний предел пропускной способности (производительности) сети можно получить в виде:

Алгоритм НС начинает работу с топологии типа "дерево" или другой слабосвязанной топологии и включает следующие шаги.

Шаг 1. Определить оптимальные потоки в ветвях (решение задачи РП) . Этот шаг - маршрутизация - выполняется после каждой модификации топологии сети для генерации новых потоков в ветвях.

Шаг 2. Найти насыщенное сечение. Эта процедура выполняется на каждом шаге маршрутизации.

Шаг 3. Добавить наиболее эффективную ветвь (или увеличить пропускную способность ветви) для объединения двух компонентов (двух частей сети, разделяемых сечением).

Наиболее эффективная ветвь определяется по критерию стоимости (наименьшей стоимости), но при этом учитывается и повышение пропускной способности при введении этой ветви: ищется компромисс между повышением пропускной способности и стоимостью. Для определения наиболее эффективной ветви пользуются

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

Шаг 4. Исключить наименее эффективную по критерию стоимости ветвь из каждой подсети (компонент): выбирается наименее используемая линия с учетом стоимости.

Шаг 5. Повторять шаги 3 и 4 до тех пор, пока не будет получено реализуемое решение (реализуемая топология). Обычно под реализуемым понимается решение, обеспечивающее производительность сети в пределах 5% от планируемой величины.

Шаг 6. Заменить последовательность цепочки ветвей, используемых в основном для транзитного трафика, одной эквивалентной линией.

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

Метод устранения ветвей (УВ)

Применяется в тех случаях, когда дискретные стоимости могут быть с достаточным основанием аппроксимированы вогнутыми кривыми. Этот метод представляет собой итеративную форму решения задачи ВПС и РП. Используется тот факт, что ветви могут быть устранены, и, следовательно, будут внесены топологические

изменения по мере выполнения алгоритма, решающего задачу ВПС и РП в непрерывной форме. Такое устранение ветвей (каналов передачи) происходит потому, что стоимость сети D является вогнутой по потокам функцией. Поэтому этот итеративный алгоритм называют также вогнутым методом устранения ребер (ВМУР).

Подоптимальный алгоритм УВ работает следующим образом.

Шаг 1. Выбрать исходную топологию, в качестве которой в большинстве случаев целесообразна полносвязная топология или близкая к ней.

Шаг 2. Для каждой ветви из топологии провести линейную аппроксимацию. При каждой итерации в следующем шаге для пропускной способности использовать величину, линеаризованную около значения потока для этой ветви.

Шаг 3. Выполнить алгоритм ВПС и РП. Если при какой-либо итерации нарушается ограничение связности, т.е. при устранении неэкономичной линии нарушается условие k-связности, то прекратить оптимизацию и перейти к шагу 4. В противном случае провести алгоритм ВПС и РП до конца (он основан на алгоритме ОП) и после этого перейти к шагу 4.

Шаг 4. Дискретизировать непрерывные пропускные спообности, полученные с помощью подоптимального решения задачи ВПС и РП. Например, непрерывная пропускная способность может быть округлена до ближайшего допустимого дискретного значения такого, что для него продолжает выполняться условие T 7,0 [T]. При этом, по-видимому, изменится полная стоимость сети D.

Шаг 5. Провести окончательную оптимизацию потока применением алгоритма ОП и, если потребуется, даже подстройкой пропускных способностей и потоков.

Шаг 6. Повторить шаги 3 - 5 для ряда реализуемых начальных потоков с помощью случайного выбора исходных длин с потоками, направляемыми по кратчайшим маршрутам.

Шаг 7. Повторить шаги 1 - 6 для ряда начальных топологий.

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

Порядок выполнения работы

Используя эвристический алгоритм синтеза структуры информационной сети (указывается преподавателем) студент должен выбрать оптимальную структуру.

Используя опцию меню "Create/delete chanel" студент создает необходимую исходную структуру сети. Затем, используя опцию "Edit path", определяются пути доставки информации, т.е проводится распределение потоков. В данном режиме включенные в сеть каналы связи отображаются на экране пунктирными линиями, а включенные в маршрут - сплошными. Опцией "Select city" выбирается город, для которого строится маршрутная сеть (на экране

он отмечается прямоугольником), затем, используя опцию "Select channel", включаются (или исключаются) каналы из маршрутов данного города, при этом используются опции "Create path" и "Delete path".

Опцией "Go back" производится возврат в основное меню.После выбора всех маршрутов осуществляется подстройка параметров каналов связи (опция "Channel params").

Возможна коррекция исходной структуры и повторение шагов оптимизации.

Контрольные вопросы к работе

1. Дать математическую постановку задачи синтеза распределенной сети.

2. Как рассчитывается задержка в распределенной сети?

3. Какие модели и ограничения приняты при синтезе структуры информационной сети?