Компьютерные сети. 6-е изд.

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

Алгоритм маршрутизации (routing algorithm) — это компонент программного обеспечения сетевого уровня, отвечающий за выбор выходной линии для отправки поступившего пакета. Если сеть использует дейтаграммную службу, выбор маршрута должен производиться заново для каждого пакета, так как оптимальный путь мог измениться. При использовании виртуальных каналов маршрут определяется только при создании нового канала, и после этого по нему следуют все пакеты данных. Этот подход называют сеансовой маршрутизацией (session routing), так как путь существует на протяжении всего сеанса связи (например, пока вы подключены к VPN).

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

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

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

Такие свойства, как равнодоступность и эффективность, могут показаться очевидными — вряд ли кто-нибудь станет возражать против них, — однако они зачастую несовместимы. Для примера рассмотрим ситуацию на илл. 5.5. Предположим, что трафик между станциями A и A', B и B', а также C и C' настолько интенсивный, что горизонтальные линии связи полностью загружены. Чтобы максимально увеличить общий поток данных, трафик между станциями X и X' нужно полностью остановить. К сожалению, станции X и X' могут с этим не согласиться. Очевидно, необходим компромисс между общей эффективностью и равным выделением канала для каждой отдельной станции.

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

Илл. 5.5. Конфликт между справедливостью и эффективностью сети