На кратчайших путях

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

Однако при этом возникает возможность появления колебаний на­грузок в сети, особенно вероятная в дейтаграммных сетях, т.к. дейтаграммная сеть, в отличие от сети с виртуальными каналами, очень быстро реагирует на обновление кратчайших путей и может почти мгновенно перенаправить весь график по новым кратчайшим пу­тям. 22

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

Можно показать, что рассмотренный тип неустойчивости прояв­ляется в том случае, когда длина линии d_ij возрастает непрерывно и монотонно с ростом проходящей по линии нагрузки x_ij. и если d_ij = 0 при x_ij=0 [I]. Поэтому данные колебания можно погасить путем добавления положительной константы к длине линии так, чтобы d_ij=a>0. При этом скалярная величина a (длина линии при нулевой нагрузке) называется коэффициентом смещения.

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

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

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

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

Дата добавления: 2015-07-25