КАТЕГОРИИ: Архитектура-(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; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |