Перемещение пакетов от хоста-отправителя к хосту-получателю

Для того чтобы переместить пакеты от хоста-отправителя к хосту-получателю, сетевой уровень должен определить путь, или маршрут, следования пакетов. Независимо от того, какую службу предоставляет сетевой уровень, деитаграммную службу (в этом случае различные пакеты данной пары отправитель-получатель могут двигаться по разным маршрутам) или службу виртуальных каналов (в этом случае все пакеты, передаваемые данным отправителем данному получателю, будут перемещаться по одному и тому же пути), сетевой уровень должен определить путь продвижения пакета. Этим занимается протокол маршрутизации сетевого уровня.
Как правило, хост напрямую подключен к одному из маршрутизаторов, так называемому маршрутизатору по умолчанию, или маршрутизатору первого ретрансляционного участка. Когда хост передает пакет, этот пакет попадает на маршрутизатор по умолчанию. Мы будем называть маршрутизатор по умолчанию хоста-источника маршрутизатором-источником, а маршрутизатор хоста-приемника по умолчанию маршрутизатором-приемником. Задача выбора пути пакета от хоста-источника к хосту-приемнику, очевидно, сводится к задаче выбора пути пакета от маршрутизатора-источника к маршрутизатору-приемнику.
Сердцевиной любого протокола маршрутизации является алгоритм, определяющий путь пакета от маршрутизатора-источника к маршрутизатору-приемнику (алгоритм маршрутизации). Задача алгоритма маршрутизации проста: для заданного множества маршрутизаторов и линий, соединяющих маршрутизаторы, алгоритм маршрутизации находит «оптимальный» путь от маршрутизатора-источника к маршрутизатору-приемнику. Как правило, «оптимальный» означает путь с «минимальной стоимостью». Мы увидим, однако, что на практике в игру часто вступают такие стратегические соображения, как вопросы безопасности (например, такое требование, как «маршрутизатор X, принадлежащий организации Y, не должен переправлять пакеты, исходящие из сети, принадлежащий организации Z»), усложняя концептуально простые и элегантные алгоритмы, на теории которых покоится практика маршрутизации в современных сетях.

Для формулирования алгоритмов маршрутизации сеть рассматривается как граф (рис. 4.4). Узлы графа представляют маршрутизаторы — точки, в которых принимаются решения о продвижении пакетов, — а линии (в соответствии с терминологией теории графов называемые «ребрами»), соединяющие эти узлы, представляют физические линии между маршрутизаторами. Каждой линии связи соответствует некоторое значение, представляющее «стоимость» пересылки пакета по этой линии. Стоимость может зависеть от физической длины линии (например, стоимость передачи кадра по трансокеанскому кабелю может быть выше, чем по короткому кабелю, проложенному по суше), скорости передачи данных по линии или финансовой стоимости линии. Для наших текущих целей мы просто примем стоимости линий как данное и не станем беспокоиться о том, как они определяются.

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

□ первая линия пути соединена с источником;
□ последняя линия пути соединена с адресатом;
□ для всех i линии с номерами i и i — 1 соединены с одним и тем же узлом;
□ для пути с минимальной стоимостью сумма стоимостей всех линий пути является минимальной по всем возможным путям между отправителем и получателем (обратите внимание, что если все линии имеют одинаковую стоимость, тогда путь с минимальной стоимостью представляет собой также кратчайший путь, то есть путь, состоящий из минимального количества линий между отправителем и получателем).
Например, на рис. 4.4 путь с минимальной стоимостью между узлами А (отправителем) и С (получателем) представляет собой маршрут ADEC. (Как мы увидим, путь проще обозначать узлами, входящими в путь, а не ребрами, образующими путь.)
В качестве простого упражнения попытайтесь найти путь с минимальной стоимостью от узла А до узла F. Скорее всего, вы будете искать путь от узла А до узла F, изучая рис. 4.4 и пробуя несколько маршрутов от узла Л до узла F, каким-то образом определяя, что стоимость выбранного вами пути минимальна из всех возможных путей (вряд ли вам удастся проверить все 17 возможных путей между узлами А и F). Подобные вычисления представляют собой пример централизованного алгоритма маршрутизации — алгоритм маршрутизации рассчитывался в одном месте (вашем мозгу) при наличии полной информации о сети. Обобщая, скажем, что все алгоритмы маршрутизации можно разбить на два класса: глобальные и децентрализованные.
□ Глобальный алгоритм маршрутизации находит путь с наименьшей стоимостью от отправителя до получателя с помощью полной информации о сети. Таким образом, в качестве входных данных алгоритм использует информацию о том, какой узел с каким соединен напрямую линией связи, и о стоимости всех линий. Прежде чем начать сами вычисления, данный алгоритм должен каким-то образом получить эту информацию. Сами вычисления могут производиться на каком-либо одном компьютере (централизованный глобальный алгоритм маршрутизации) или тиражироваться в разных местах. Однако ключевой особенностью здесь является то, что глобальный алгоритм обладает полной информацией о топологии сети и стоимости линий. На практике алгоритмы, обладающие глобальной информацией о состоянии сети, часто называют алгоритмами, основанными на состояниях линий, так как алгоритм должен знать стоимость каждой линии в сети. Мы рассмотрим глобальный алгоритм, основанный на состояниях линий, в подразделе «Алгоритм маршрутизации, основанный на состояниях линий» раздела «Основы маршрутизации».
□ В децентрализованном алгоритме маршрутизации вычисление пути с наименьшей стоимостью выполняется итерационным распределенным образом. Ни один узел не обладает полной информацией о стоимости всех линий сети. Изначально каждому узлу известна только стоимость напрямую присоединенных к нему линий. Затем, путем итерационных вычислений и обмена информацией с соседними узлами (то есть узлами, находящимися на противоположных концах напрямую присоединенных к нему линий) узел постепенно определяет путь с наименьшей стоимостью до получателя или до группы получателей. Мы рассмотрим децентрализованный алгоритм маршрутизации, известный как дистанционно-векторный алгоритм в подразделе «Алгоритм дистанционно-векторной маршрутизации» данного раздела. Он называется дистанционно-векторным алгоритмом, потому что узлу никогда не известен весь маршрут от отправителя до получателя. Вместо этого он знает соседа, которому должен переправить пакет, чтобы достичь получателя по пути с наименьшей стоимостью, а также стоимость этого пути.

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

Третий способ классификации алгоритмов маршрутизации определяется по тому, чувствителен ли алгоритм к перегрузке. В чувствительном к перегрузке алгоритме стоимости линий динамически изменяются, отражая текущий уровень перегрузки в соответствующей линии. Если с временно перегруженной линией ассоциируется высокая стоимость, алгоритм маршрутизации будет стараться выбирать маршруты в обход перегруженной линии. Первые алгоритмы сети ARPAnet были чувствительными к перегрузке, однако попытки использования чувствительных к перегрузке алгоритмов натолкнулись на ряд проблем. Сегодня в Интернете применяются алгоритмы, нечувствительные к перегрузке (такие как RIP, OSPF и BGP), так как стоимость линии, как правило, не отражает ее текущего (или недавнего) уровня перегрузки.

В Интернете, как правило, используются только два типа алгоритмов маршрутизации: динамический глобальный алгоритм, основанный на состояниях линий, и динамический децентрализованный дистанционно-векторный алгоритм. Мы рассмотрим эти алгоритмы соответственно в подразделах «Алгоритм маршрутизации, основанный на состояниях линий» и «Алгоритм дистанционно-векторной маршрутизации», а другие алгоритмы маршрутизации — в подразделе «Другие алгоритмы маршрутизации» данного раздела.