42. Принципы маршрутизации в сетях передачи данных.

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

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

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

Алгоритмы выбора маршрута разбить на два основных класса: адаптивные и неадаптивные.

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

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

Алгоритмы маршрутизации.

Выбор кратчайшего пути.

Идея заключается в построении графа подсети, в котором каждый узел будет соответствовать маршрутизатору, а каждая дуга – линии связи. При выборе маршрута между двумя маршрутизаторами алгоритм просто находит кротчайший путь между ними на графе. Один из способов измерения длины пути состоит в подсчете количества транзитных участков. В таком случае пути АВС и АВЕ имеют одинаковую длину . Можно измерять расстояние в километрах. В таком случае окажется, что путь АВС значительно длиннее пути АВЕ.

Входное дерево для маршрутизатора В.

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

Заливка ( лавинная маршрутизация ).

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

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

На практике чаще применяется вариант данного алгоритма под названием «выборочная заливка». В данном алгоритме маршрутизаторы посылают пакеты не по всем линиям, а только по тем, которые идут приблизительно в нужном направлении.

Маршрутизация на основании потока.

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

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

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

Дистанционно–векторная маршрутизация.

В современных компьютерных сетях обычно используются динамические алгоритмы выбора маршрута. Наиболее популярными являются два динамических алгоритма: дистанционно–векторная маршрутизация и маршрутизация состояния канала.

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

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

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

Маршрутизация с учетом состояний линий.

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

• Обнаруживать своих соседей и узнавать их сетевые адреса.

• Измерять задержку или стоимость связи с каждым из своих соседей.

• Создавать пакет, содержащий всю собранную информацию.

• Посылать этот пакет всем остальным маршрутизаторам.

• Вычислить кратчайший путь ко всем остальным маршрутизаторам.

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