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

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

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

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

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

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

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

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

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

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

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

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

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

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