Алгоритмы маршрутизации. Принцип оптимальности маршрута. Выбор кратчайшего пути. Заливка.

 

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

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

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

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

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

Принцип оптимальности маршрута

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

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

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

Идея заключается в построении графа подсети, в котором каждый узел будет соответствовать маршрутизатору, а каждая дуга — линии связи. При выборе маршрута между двумя маршрутизаторами алгоритм просто пат ин кратчайший путь между ними на графе.Один из способов измерения длины пути состоит в подсчете количества транзитных участков. Однако помимо учета количества транзитных участков и физической длины линий возможен учет и других параметров. Например: + среднюю длину очереди и время задержки пересылки, определяемые каждый час с помощью передачи специального тестового пакета. В таком графе кратчайший путь определяется как самый быстрый путь, а не путь с самой короткой длиной кабеля или путь, состоящий из минимального числа отдельных отрезков кабеля.Известно несколько алгоритмов вычисления кратчайшего пути между двумя узлами графа. Один из них был создан знаменитым Дейксгрой (Dijkstra) в 1959 году. Каждый узел помечается (в скобках) расстоянием до него от узла отправителя по наилучшему известному пути.

 

Заливка

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

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

Чтобы предотвратить неограниченный рост размера списка, можно снабдить все списки счетчикомк , показывающим, что все порядковые номера вплоть до к уже встречались. И когда приходит пакет, можно очень легко проверить, не яв­ляется ли он дубликатом. При положительном ответе такой пакет отвергается. Кроме того, не нужно хранить весь список до к, поскольку этот счетчик очень действенно подытоживает его.

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

 

 

⇐ Предыдущая16171819202122232425Следующая ⇒

Поделиться: