каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 1 Маршрутизация

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 2 Цели маршрутизации 1. Обеспечить минимальную возможную задержку и максимальную пропускную способность. 2. Обеспечить прохождение пакета сквозь сеть за минимальную стоимость. 3. Обеспечить каждый пакет максимальной возможной защитой и надежностью.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 3 Цели разработки алгоритмов маршрутизации оптимальность; оптимальность; простота и низкие непроизводительные затраты; простота и низкие непроизводительные затраты; живучесть и стабильность; живучесть и стабильность; быстрая сходимость; быстрая сходимость; гибкость. гибкость.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 4 О птимальность Оптимальность, вероятно, является самой общей целью разработки. Она характеризует способность алгоритма маршрутизации выбирать "наилучший" маршрут. Наилучший маршрут зависит от показателей и от "веса" этих показателей, используемых при проведении расчета. Например, алгоритм маршрутизации мог бы использовать несколько пересылок с определенной задержкой, но при расчете "вес" задержки может быть им оценен как очень значительный. Естественно, что протоколы маршрутизации должны строго определять свои алгоритмы расчета показателей.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 5 Живучесть и стабильность Алгоритмы маршрутизации должны обладать живучестью. Другими словами, они должны четко функционировать в случае неординарных или непредвиденных обстоятельств, таких как отказы аппаратуры, условия высокой нагрузки и некорректные реализации. Т.к. роутеры расположены в узловых точках сети, их отказ может вызвать значительные проблемы. Часто наилучшими алгоритмами маршрутизации оказываются те, которые выдержали испытание временем и доказали свою надежность в различных условиях работы сети.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 6 Быстрая сходимость Алгоритмы маршрутизации должны быстро сходиться. Сходимость - это процесс соглашения между всеми роутерами по оптимальным маршрутам. Когда какое- нибудь событие в сети приводит к тому, что маршруты или отвергаются, или становятся доступными, роутеры рассылают сообщения об обновлении маршрутизации. Сообщения об обновлении маршрутизации пронизывают сети, стимулируя пересчет оптимальных маршрутов и, в конечном итоге, вынуждая все роутеры придти к соглашению по этим маршрутам. Алгоритмы маршрутизации, которые сходятся медленно, могут привести к образованию петель маршрутизации или выходам из строя сети.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 7 На Рисунке изображена петля маршрутизации. В данном случае, в момент времени t1 к роутеру 1 прибывает пакет. Роутер 1 уже был обновлен и поэтому он знает, что оптимальный маршрут к пункту назначения требует, чтобы следующей остановкой был роутер 2. Поэтому роутер 1 пересылает пакет в роутер 2. Роутер 2 еще не был обновлен, поэтому он полагает, что следующей оптимальной пересылкой должен быть роутер 1. Поэтому роутер 2 пересылает пакет обратно в роутер 1. Пакет будет продолжать скакать взад и вперед между двумя роутерами до тех пор, пока роутер 2 не получит корректировку маршрутизации, или пока число коммутаций данного пакета не превысит допустимого максимального числа

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 8 Простота и низкие непроизводительные затраты Алгоритмы маршрутизации разрабатываются как можно более простыми. Другими словами, алгоритм маршрутизации должен эффективно обеспечивать свои функциональные возможности, с минимальными затратами программного обеспечения и коэффициентом использования. Особенно важна эффективность в том случае, когда программа, реализующая алгоритм маршрутизации, должна работать в компьютере с ограниченными физическими ресурсами.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 9 Гибкость Алгоритмы маршрутизации должны быть также гибкими. Другими словами, алгоритмы маршрутизации должны быстро и точно адаптироваться к разнообразным обстоятельствам в сети. Например, предположим, что сегмент сети отвергнут. Многие алгоритмы маршрутизации, после того как они узнают об этой проблеме, быстро выбирают следующий наилучший путь для всех маршрутов, которые обычно используют этот сегмент. Алгоритмы маршрутизации могут быть запрограммированы таким образом, чтобы они могли адаптироваться к изменениям полосы пропускания сети, размеров очереди к роутеру, величины задержки сети и других переменных.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 10 Протокол поддержки маршрутной таблицы (RTMP) Протокол, который организует и поддерживает маршрутные таблицы AppleTalk, называется Протоколом поддержки маршрутной таблицы (RTMP). Маршрутные таблицы RTMP содержат данные о каждой сети, до которой может дойти дейтаграмма. В эти данные входит порт роутера, который ведет к сети пункта назначения, ID узла следующего роутера, который принимает данный пакет, расстояние до сети назначения, выраженное числом пересылок, и текущее состояние этих данных (хорошее, подозрительное или плохое). Периодический обмен маршрутными таблицами позволяет роутерам объединенных сетей гарантировать обеспечение непротиворечивой текущей информацией. На Рисунке представлен образец таблицы RTMP и соответствующая архитектура сети.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 11

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 12 Типы алгоритмов 1. Статическими или динамическими 2. Одномаршрутными или многомаршрутными 3. Одноуровневыми или иерархическими 4. С интеллектом в главной вычислительной машине или в роутере 5. Внутридоменными и междоменными 6. Алгоритмами состояния канала или вектора расстояний

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 13 Показатели алгоритмов (метрики) В алгоритмах маршрутизации используется много различных показателей. Сложные алгоритмы маршрутизации при выборе маршрута могут базироваться на множестве показателей, комбинируя их таким образом, что в результате получается один отдельный (гибридный) показатель. Ниже перечислены показатели, которые используются в алгоритмах маршрутизации: 1. Длина маршрута 2. Надежность 3. Задержка 4. Ширина полосы пропускания 5. Нагрузка 6. Стоимость связи

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 14 Особенные способы маршрутизации служебной информации Алгоритмы Маршрутизации СИ Адресные алгоритмы Безадресные алгоритмы Одноадресная маршрутизация Многоадресная маршрутизация Доведение по фиксированным маршрутам Дерево кратчайших путей К деревьям кратчайших путей Граф кратчайших путей Доведение методом «лавина»

Диаграмма команд при активации путей и соединений

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 16 При установлении сессии узел-отправитель выбирает из списка виртуальных соединений первое, находящееся в исходном состоянии. Если соответствующий выбранному виртуальному соединению явный путь находится в недействующем состоянии, то выбирается другое виртуальное соединение из списка. Если так образом будут рассмотрены и забракованы все виртуальные соединения, то модуль управления сессией будет оповещен о невозможности ее установления в данном классе обслуживания. Если будет найдено виртуальное соединение с действующим явным путем, то осуществляются последовательно активизация явного пути, активизация виртуального соединена и активизация сессии. На этом рисунке приведены диаграммы следования маршрутных команд при восстановлении и активизации явного пути, а также при активизации виртуального соединения.

каф. ВТ, ТОГУ, г. Хабаровск, вед. преп. Шоберг А.Г. 17 Соответствие между виртуальным соединением и явными путями в SNA Понятие виртуального соединения определено только на узле-получателе и узле-отправителе. На транзитном узле маршрутизация блоков PIU осуществляется на основе номера явного пути и адреса подзоны получателя, указанных в заголовке FID4. На рисунке показаны соответствия между виртуальным соединением, явным путем и ГП, устанавливаемые па граничных и транзитных узлах одного соединения.