3.8 Лабораторная работа №7 Маршрутизация в вс

Лабораторная работа №7 выполняется после ознакомления основными алгоритмами маршрутизации в глобальной сети.

Цель работы:

Моделирование протоколов маршрутизации в вычислительных сетях.

Задание на лабораторную работу

Напишите программу, моделирующую один из вариантов:

1) Маршрутизацию методом заливки;

2) Маршрутизацию по вектору расстояния;

3) Маршрутизацию по состоянию связей;

4) Групповая маршрутизация. Остовые деревья (Spanning Trees)

5) Групповая маршрутизация. RPF (Reverse Path Forwarding).

6) Групповая маршрутизация. RPF (Reverse Path Forwarding). С усечением (prunes).

7) Групповая маршрутизация. RPF (Reverse Path Forwarding). С наращением (grant).

8) Групповая маршрутизация. CBT (Core Based Trees, Деревья с фиксированным ядром)

9) Групповая маршрутизация методом заливки.

Общие требования:

Программа должна обладать следующими возможностями:

Графический интерфейс.

Возможность вводить ненаправленный граф (входное дерево сети) в виде:

A B <cost>,

где A – имя маршрутизатора, для которого формируется запись;

B – имя узла, с которым есть соединение;

<cost> значение стоимости данного соединения в условных единицах (word);

Ввод можно осуществлять из файла или вручную.

Количество узлов в сети не менее 10;

Возможность просматривать таблицу маршрутизации для каждого узла, если таковая имеется;

Возможность обозначать начальный и конечный узел сети;

Индикация решения (оптимального пути на графе в виде последовательности вершин и суммарной стоимости пути) для заданных в п.4 вершин;

Возможность динамически добавлять и удалять узлы маршрутизаторов на существующей сети

Демонстрировать для добавленных узлов пошаговое формирование таблиц маршрутизации;

Демонстрировать, как меняется таблица маршрутизации соседнего узла если некоторый смежный узел был удален;

Для метода заливки показать пошаговое распространение пакетов оценить количество лишних – дублированных пакетов;

Для метода вектора расстояния продемонстрировать возникновение счета до бесконечности при удалении узла;

Для метода состояния связей продемонстрировать, как влияет динамическое изменение стоимости связи на принимаемые решения о маршрутизации;

Для алгоритмов групповой маршрутизации добавить возможность подсоединения узлов в групповой рассылке или данному групповому адресу. Реализовать возможность нескольких групповых адресов.

Теория.

Для маршрутизации применяются специальные алгоритмы и протоколы (например, RIP, OSPF, NLSP). C помощью протоколов маршрутизации создается карта сети или специальные таблицы маршрутизации, которые хранятся на каждом маршрутизаторе. Одношаговые алгоритмы маршрутизации определяют только следующий маршрутизатор в сети для отправки пакета, каждый маршрутизатор ответственен за выбор одного шага маршрута. В многошаговых алгоритмах узел источник задает полный маршрут следования пакета через промежуточные маршрутизаторы.

Одношаговые алгоритмы делятся на:

алгоритмы фиксированной маршрутизации.

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

алгоритмы простой маршрутизации.

В этом случае таблица маршрутизации вообще не строится, либо строится без участия маршрутизаторов. Бывает несколько видов простой маршрутизации:

Случайная маршрутизация — пакет отсылается в любом случайном направлении, исключая направление с которого он поступил.

Лавинная маршрутизация — пакет широковещательно отсылается по всем направлениям кроме исходного.

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

алгоритмы адаптивной (или динамической) маршрутизации.

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

Адаптивные алгоритмы делятся на алгоритмы дистанционно векторного типа и алгоритмы состояния связей.

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

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

Наиболее распространённым протоколом использующий данный алгоритм является RIP IP, RIP IPX.

Алгоритмы состояния связей.

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

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

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

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

Протоколами на основе алгоритмов состояния связей, являются протоколы is is стека osi и протокол OSPF стека TCP/IP.

Мультикастингом (multicasting) называется рассылка дейтаграмм группе получателей. Для идентификации групп используются специальные адреса получателя; эти адреса в стеке протокола TCP/IP назначаются из класса D в диапазоне 224.0.0.0 – 239.255.255.255. Дейтаграмма, направленная на групповой адрес, должна быть доставлена всем участникам группы.

Маршрутизация групповых дейтаграмм

Веерная рассылка (Flooding)

Веерная рассылка – наиболее простой метод маршрутизации групповых дейтаграмм, при котором дейтаграмма рассылается во все сети системы независимо от наличия в той или иной сети членов группы. При поступлении групповой дейтаграммы маршрутизатор проверяет, впервые ли он получает эту дейтаграмму. Если да, то маршрутизатор рассылает дейтаграмму через все свои интерфейсы, кроме того, с которого она была получена. Иначе дейтаграмма игнорируется.

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

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

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

Остовые деревья (Spanning Trees)

В системе сетей выбирается корневой маршрутизатор, после этого из графа системы выделяется подграф-дерево, соединяющий корневой маршрутизатор со всеми остальными маршрутизаторами системы. Эта процедура производится на этапе инициализации системы – в процессе работы дерево не изменяется.

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

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

Однако групповые дейтаграммы по-прежнему рассылаются во все сети независимо от наличия в них получателей, кроме того:

требуется реализация механизма (протокола) выбора корневого узла и построения дерева;

весь групповой трафик ложится на одни и те же связи (сети), составляющие, возможно, небольшое подмножество всей системы сетей;

для некоторых пар отправитель-получатель путь по установленному дереву будет неоптимальным.

RPF

Метод RPF (Reverse Path Forwarding) состоит в следующем.

Маршрутизатор получил через интерфейс I групповую дейтаграмму от источника S. Если через I лежит кратчайший маршрут от данного маршрутизатора до узла S, то ретранслировать дейтаграмму через все интерфейсы кроме того, с которого она получена. Иначе дейтаграмму игнорировать.

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

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

Важно отметить, что для реализации метода RPF необходимо иметь доступ к таблице маршрутов. Более того, для реализации модифицированного алгоритма требуется доступ к внутренним данным протокола внутренней маршрутизации (например, к базе данных состояния связей OSPF) – иначе нельзя сделать вывод о маршрутах, используемых другими узлами системы (источниками групповых дейтаграмм).

Следующая модификация RPF призвана учесть наличие или отсутствие получателей групповой дейтаграммы в сетях системы с тем, чтобы дейтаграммы рассылались только в те сети, где есть члены данной группы. Применяемый для этого метод называется prunes – усечение (от английского prune – "обрезать ветви дерева").

Первая групповая дейтаграмма распространяется обычным образом по алгоритму RPF и достигает всех маршрутизаторов системы. Если к какому-то "конечному" маршрутизатору не присоединены члены данной группы (это устанавливается с помощью протокола IGMP), он посылает через тот интерфейс, откуда получил групповую дейтаграмму, специальное сообщение Prune (по адресу данной группы). Это сообщение, принятое маршрутизатором, находящемся в вышестоящем узле дерева, означает "не посылать больше через этот интерфейс дейтаграммы от данного источника для данной группы". Вышестоящий маршрутизатор помечает этот интерфейс как pruned (усеченный) на определенный срок. По истечении этого срока процесс повторяется сначала. Однако имеется сообщение Graft (от английского "прививать растение"), позволяющее быстро подсоединиться к существующему дереву (то есть отменить ранее посланное Prune), не дожидаясь очередной рассылки "пробной" дейтаграммы.

Если Prune получено от всех нижележащих маршрутизаторов, маршрутизатор отправляет Prune еще более вышестоящему маршрутизатору – таким образом можно усекать целые поддеревья.

Метод RPF (с усечением) обладает следующими чрезвычайно существенными достоинствами:

групповые дейтаграммы от каждого источника рассылаются по оптимальным путям – и эти пути определяются динамически в момент рассылки;

при этом учитывается членство в группах – дейтаграммы в сети, где нет получателей, не рассылаются;

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

Недостатки рассматриваемого метода:

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

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

Необходимость наличия интерфейса к структурам данных модуля маршрутизации (или необходимость создания "сопровождающего" протокола маршрутизации) увеличивает сложность реализации RPF.

Несмотря на описанные недостатки, именно метод RPF лежит в основе многих протоколов групповой маршрутизации.

CBT

Метод CBT (Core Based Trees, Деревья с фиксированным ядром) основан на том, что для каждой группы назначается главный маршрутизатор, называемый ядром, – он будет корнем дерева рассылки. Все маршрутизаторы, к которым могут быть подключены потенциальные члены группы, знают адрес ядра. После того, как член группы зарегистрировался на маршрутизаторе с помощью протокола IGMP, маршрутизатор посылает в сторону ядра сообщение Join для присоединения к дереву рассылки. Промежуточные маршрутизаторы, пересылая это сообщение в сторону ядра, одновременно помечают интерфейсы, через которые получены сообщения Join, как принадлежащие дереву рассылки для данной группы. Сообщение следует до ядра или до первого маршрутизатора, уже присоединенного к дереву рассылки.

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

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

Достоинства этого метода:

все групповые дейтаграммы рассылаются только участникам группы (в отличие от RPF нет "пробных" дейтаграмм);

размер таблицы принадлежности интерфейсов к деревьям рассылки, которую требуется хранить на маршрутизаторе, меньше чем при использовании метода RPF (произведение числа групп на число интерфейсов; для всех источников одной группы используется одно дерево);

не требуется доступ к маршрутным таблицам.

Недостатки CBT аналогичны недостаткам метода остовых деревьев:

весь групповой трафик ложится на одни и те же связи (сети), составляющие, возможно, небольшое подмножество всей системы сетей; узким местом является ядро;

для некоторых пар отправитель-получатель путь по установленному дереву будет неоптимальным.