28. Алгоритмы маршрутизации в кс

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

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

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

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

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

Заливка

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

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

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

Предполагается, что маршрутизаторам известно расстояние до каждого из соседей. Предположим, что в качестве единицы измерения используется время задержки, и этот параметр относительно каждого из соседей известен маршрутизатору. Через каждые Т миллисекунды все маршрутизаторы посылают своим соседям список с приблизительными задержками для каждого получателя. Они, разумеется, также получаются подобный список от всех своих соседей. Допустим, одна из таких таблиц пришла от соседа Х, и в ней указывается, что время распространения от маршрутизатора Х до маршрутизатора I равно Xi. Если маршрутизатор знает, что время пересылки до маршрутизатора Х равно m, тогда задержка при передаче пакета маршрутизатору I через маршрутизатор X составит Xi + m. Выполнив такие расчеты для всех своих соседей, маршрутизатор может выбрать наилучшие пути и поместить соответствующие записи в новую таблицу. Старая таблица в расчетах не используется.

У этого алгоритма есть существенная проблема – проблема «счета до бесконечности». Конечно, рано или поздно правильный ответ будет найден, но поиск может занять довольно долгое время.

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

Идею можно изложить требованиями к маршрутизатору:

• Обнаружение своих соседей и определение их сетевых адресов

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

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

• Отправка этих пакетов всем маршрутизаторам

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

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

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

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

Широковещание – рассылка пакетов по всем пунктам назначения. Для этого применяют разные способы:

• Рассылка отдельных пакетов по всем направлениям

• Заливка

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

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

• Продвижение по встречному пути

Оба последних алгоритма используют представление сети в виде сетевого графа.

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

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

Поиск узла в равноранговых сетях

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

Пусть система состоит из n пользователей. У каждого из них есть какие-то записи, и каждый готов хранить биты и части индекса, которые могут быть использованы другими. У каждого узла есть IP-адрес, который может быть закодирован m-битным номером с помощью хэш-функции со 160-битным значением. Таким образом, любой IP-адрес можно закодировать числом, называемым идентификатором узла. Концепция состоит в том, что вообще все идентификаторов располагаются в возрастающем порядке, образуя большой круг чисел. Для определения нужного и используется метод хорд…