Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Волновые методы маршрутизации

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

 

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

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

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

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

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

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

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

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

 

 

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

В общем случае в сети с волновым методом маршрутизации форми­руются три "волны" сигналов: поисковая, ответная и заключитель­ная [5].

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

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

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

 

<== предыдущая лекция | следующая лекция ==>
Исходный граф сети | Влияние длины проводника на передачу высокочастотных сигналов
Поделиться с друзьями:


Дата добавления: 2014-01-06; Просмотров: 403; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.