Задача выбора пропускных способностей.

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

,

где - стоимость в расчете на единицу пропускной способности i-го канала. может меняться от какого-либо параметра канала. Например, он часто берется пропорциональным физической длине канала.

Для минимизации составим функцию Лагранжа.

,где

Отсюда

; что дает

или

.

Найдем , умножив последнее равенство на и, просуммировав по i, получим:

Откуда

.

 

Обозначим (9),

тогда

(10)

Это и есть оптимальное решение задачи ВПС. При таком наборе пропускная способность любого канала будет иметь по крайней мере пропускная способность (то есть минимально требуемое значение) и, кроме того, некоторая дополнительная пропускная способность. Отметим, что стоимость минимальной пропускной способности i-го канала равна ; взяв сумму по всем каналам, получим допустимую стоимость. Разность между полной стоимостью и минимально допустимой стоимостью равна и задается (9). Поэтому называется добавочной стоимостью.

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

Если подставить (9) в выражение для , то получим:

 

 

, где (11)

Это равенство – минимальная средняя задержка в сети, пропускные способности в которой выбраны оптимально.

При , . Если задача ВПС имеет реализуемое (осуществимое) решение(то есть ). Если задача не имеет реализуемого решения. Уравнения (10) и (11) дают полное решение ВПС.

Рассмотрим частный случай , при этом, не теряя общности, можно положить d=1. Этот случай имеет место при рассмотрении спутниковых каналов связи, в которых расстояние между двумя различными точками(на Земле, та как логический канал – это узел-узел) в зоне спутника по существу является одинаковым независимо от расстояния между этими точками на поверхности земли. Здесь Если , то есть сумма всех пропускных способностей сети, которые обозначим как . Тогда выражения для и

имеют вид:

где (это не коэффициент использования, просто совпадают обозначения), - средняя длина пути;

т.е.

(12)

 

(13)

 

введена потому, что она является заданной величиной.

Величина просто равна отношению (средней скорости, с которой биты входят в сеть от внешних источников) к C(суммарной пропускной способности сети).

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

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

 

 

Рис.10. Звездообразная сеть.

 

Здесь средняя длина пути 2. Теперь следует сделать выбор между полной сетью, звездообразной сетью и всеми остальными промежуточными меду ними.

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

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

Такая процедура предлагает более чем 1 путь и, кроме того, она дает упорядочение по предпочтению этих путей – обычно длинные пути менее предпочтительны, чем прямые.

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

Было заключено, что при линейной стоимостной функции, при минимизации возможна широкая (и, может быть, нежелательная) вариация значений .В результате была поставлена новая задача ВПС, в которой следует минимизировать функцию:

Выбор этой функции обусловлен тем, что большие значения , возведенные в большие степени, увеличивают ее намного больше, чем ранее, так что любая процедура минимизации с k>1 приведет к уменьшению разницы между .

Решая эту задачу как прежде, получим

.

При имеем:

Отметим, что все получаются равными.

При получим:

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

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

 

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

1.Какое оптимальное значение пропускной способности канала в задаче ВПС?

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

3.Охарактеризуйте фиксированную процедуру выбора маршрута.

4.Охарактеризуйте процедуру выбора маршрута, допускающую альтернативы.

5. Какая величина называется пропорциональным набором пропускным способностей?

6. Что такое полносвязная сеть?

7. Чему равна средняя длина пути в сети?

8. При каких значениях ρ оптимальной топологией является полносвязная сеть?

Лекция №5