Выбор топологии сети.
Рассмотрим задачу
ВТПС и РП в ее двойственной форме, то
есть минимизацию
при заданном максимальном среди заданных
.
Заданными являются положения узлов и
потоки
.
В реальных сетях встречается трудный
случай (заданного) множества дискретных
пропускных способностей. Если не делать
никаких аппроксимаций этих дискретных
стоимостей, то прямое решение задачи
ВТПС и РП требует численного решения
с
переменными(пропускными способностями)
и решения задачи о потоках . Это слишком
сложно. Рассмотрим эвристическое
решение, которое находится в
5-10% от оптимума ( в конце концов, редко можно угадать с большей точностью, так что с технической точки зрения это вполне удовлетворительно).Решение задачи представляет собой итеративную форму решения ВПС и РП. Оно использует тот факт, что каналы могут быть устранены (то есть будут внесены топологические изменения) по мере выполнения алгоритмов ВПС и РП. Так как является вогнутой по потокам { } функцией, то этот алгоритм называется вогнутым методом устранения ребер (ВМУР).
ПОДОПТИМАЛЬНЫЙ АЛГОРИТМ ВМУР.
Выбрать исходную топологию (часто на практике хорошо выбрать полносвязную сеть).
Для каждого канала провести степенную
или линейную
аппроксимацию.Выполнить алгоритм ВПС И РП. Если при какой-либо итерации нарушается ограничение связности(например, двусвязности – больше и равное двум число путей между узлами), то прекратить оптимизацию и перейти к шагу 4.
Дискретизировать непрерывные пропускные способности, полученные с помощью ВПС и РП. Например, непрерывные пропускные способности могут быть округлены до ближайшего допустимого(
дискретного значения, такого, что для
него продолжает выполняться условие
.
При этом, видимо, изменится полная
стоимость
.Провести окончательную оптимизацию потока путем применения алгоритма ОП (и, если требуется, даже подстройкой пропускных способностей и потоков).
Повторить шаги 3-5 для ряда реализуемых случайных начальных потоков ( с помощью случайного выбора исходных длин с потоками, направленными по кратчайшим маршрутам).
Повторить шаги 1-6 для ряда начальных топологий.
Опыт показывает, что к хорошим результатам приводят от 20-30 повторений в шаге 6 и несколько (5-7) исходных топологий (их которых одна полносвязная, а другие – сильносвязные сети) в шаге 7.
Эти методы представляют современное состояние проектирования подсети связи сетей ЭВМ.
Контрольные вопросы:
1.Приведите подоптимпльный алгоритм ВПС И РП.
2. Сформулируйте задачу ВПС и РП в двойственной форме с решением.
3. Приведите алгоритм ВМУР.
4. В чем заключается метод отыскания потока?
5. Приведите алгоритм отыскания потоков, идущих по кратчайшим путям.
6. Приведите оптимальный алгоритм ОП для выбора маршрутов.
7. В чем заключается подоптимальный метод ОП?
8. Приведите алгоритм ОП для фиксированной процедуры выбора маршрута.
Лекция № 6