Задача выбора пропускных способностей и распределения потоков (ВПС и РП)

 

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

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

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

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

1. Положить .

2. Выполнить алгоритм ВПС для потока и найти оптимальное множество пропускных способностей, используя линеаризованные стоимости.

3. Используя длины , выполнить алгоритм ОП при на каждом шаге. Полученный в результате оптимальный поток обозначается через .

4. Если для больше либо равен для , то STOP; поток дает локальный минимум. В противном случае положить и прейти к шагу 2.

 

Алгоритм сходится, так как имеется лишь конечное число потов по кратчайшим маршрутам.

При этом (из формулы ) задается равенством:

 

.

Отсюда следует, что и отрицательные циклы существовать не могут

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

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

Задачу ВПС и РП можно сформулировать в двойственной форме:

 

 

Дано:	топология сети.
Минимизировать:	.
Варьируются:	{ }и { }.
Ограничение:	.

 

 

Описанный выше алгоритм ВПС и РП применим к этой двойственной задаче, если заменить определение длины новым определением .

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

 

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

 

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

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 адресуемого объекта.

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

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

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

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

 

Маршрутизация пакетов.

Используются следующие основные способы маршрутизации:

Маршрутизация по предыдущему опыту – передача пакета в направлении, выбираемом на основе анализа потока, проходящего через узел. Пакеты снабжаются счетчиком числа пройденных узлов. Пакет со значением 1 – определяет соседний узел; пакет со значением счетчика 2 определяет узел, находящийся на расстоянии 2 шагов и т.д. Эти данные позволяют установить топологию сети и на ее основе построить таблицу для выбора маршрутов. Постоянно анализируя число пройденных узлов, можно изменить таблицу маршрутов, если появился пакет с числом пройденных узлов меньше ранее зарегистрированного. Этот способ позволяет узлам приспособиться к изменениям топологий сети, однако процесс адаптации протекает медленно и неэффективно.

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

Адаптивная маршрутизация – учитывает состояние СПД. Узлы обмениваются таблицами, в которых записаны все задержки от данного узла до любого другого. Обмен – периодически, что снижает эффективность сети.

 

Управление потоками.

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

Управление потоком в сети – ограничение входного потока в сеть с целью недопущения перегрузки.