Лабораторная работа №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. Дейтаграмма, направленная на групповой адрес, должна быть доставлена всем участникам группы.