Выбор топологии сети

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

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

ПОДОПТИМАЛЬНЫЙ АЛГОРИТМ ВМУР.

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

2. Для каждого канала провести степенную или линейную аппроксимацию.

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

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

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

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

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

Опыт показывает, что к хорошим результатам приводят от 20-30 повторений в шаге 6 и несколько (5-7) исходных топологий (их которых одна полносвязная, а другие – сильносвязные сети) в шаге 7.

Эти методы представляют современное состояние проектирования подсети связи сетей ЭВМ.

Контрольные вопросы:

1.Приведите подоптимпльный алгоритм ВПС И РП.

2. Сформулируйте задачу ВПС и РП в двойственной форме с решением.

3. Приведите алгоритм ВМУР.

4. В чем заключается метод отыскания потока?

5. Приведите алгоритм отыскания потоков, идущих по кратчайшим путям.

6. Приведите оптимальный алгоритм ОП для выбора маршрутов.

7. В чем заключается подоптимальный метод ОП?

8. Приведите алгоритм ОП для фиксированной процедуры выбора маршрута.

Лекция № 6

Адресация, маршрутизация пакетов и управление потоками данных.

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

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

Иерархическое кодирование – способ построения имен (адресов) путем присоединения к локальным именам имен систем, которым принадлежит объект. Имя (адрес) имеет следующий вид: A, B, …, Q, R, где А – имя системы, В – имя подсистемы системы А, R – имя объекта в подсистеме Q, входящей в ранее указанную подсистему. По такому способу строится почтовая адресация: имя страны, имя города, улицы, дома и т.д.

Распределение адресов – состоит в присвоении постоянных имен (адресов) лишь отдельным процессам, которым выдают разрешение на доступ к системе, выделяя для доступа временные адреса. Пусть, например, системе А выделены адреса с 0001 до 0999, а системе В – с 1000 до 1999. Для доступа к этим системам выделяются постоянные адреса, например, 0001 для системы А и 1000 для системы В. Когда в системе А инициируется процесс Х, ему присваивается общесетевой адрес, например, 0125. Процесс из системы А обратится к процессу с локальным именем Y в системе В по адресу 1000. Система В с помощью процесса 1000 выделяет процессу Y временный адрес, например, 1021 (общесетевой). По окончании взаимодействия эти адреса становятся свободными.

Отображение адресов – присвоение любому объекту общесетевого адреса. Адреса преобразуются (отображаются) любой системой в локальные имена. Например, обращаясь по сетевому адресу 1256, преобразуется в локальное имя Y адресуемого объекта.

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

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

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

В существующих сетях используются разнообразные способы адресации. В настоящее время отсутствуют подробные стандарты на способы адресации абонентов СПД и процессов и их портов, связанных с СПД транспортно-сеансовыми службами систем.

Дата добавления: 2014-01-06