1. Знакомство с соседями.

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

2 Измерение стоимости линии.

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

3 Создание пакетов состояния линий .

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

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

4 Вычисление новых маршрутов.

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

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

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

Иерархическая маршрутизация.

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

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

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

Алгоритмы выбора маршрутов для мобильных хостов.

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

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

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

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

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

Широковещательная маршрутизация.

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

1. Широковещательный метод, не требующий от подсети специальных свойств, состоит в простой рассылке отправителем пакета всем адресатам. Такой метод не только неэкономно расходует пропускную способность линий, но также требует от отправителя обладания полным списком всех получателей.

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

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

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

Многоадресная рассылка.

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

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

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