Компьютерные сети. 6-е изд. - Эндрю Таненбаум

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

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

5.2. Алгоритмы маршрутизации в рамках одной сети

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

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

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

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

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

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

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

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

Алгоритмы маршрутизации можно разделить на два основных класса: неадаптивные и адаптивные. Неадаптивные алгоритмы (nonadaptive algorithms) не учитывают текущую топологию и не измеряют трафик. Вместо этого путь для каждой пары станций определяется заранее, в автономном режиме, а список маршрутов загружается в маршрутизаторы во время загрузки сети. Эта процедура называется статической маршрутизацией (static routing). Она не реагирует на сбои, поэтому обычно используется в тех случаях, когда выбор маршрута очевиден. Например, маршрутизатор F на илл. 5.3 должен отправлять пакеты в сеть, на маршрутизатор E, независимо от конечного адреса назначения.

Адаптивные алгоритмы (adaptive algorithms), напротив, реагируют на изменения топологии, а иногда и на загруженность линий. Такие алгоритмы динамической маршрутизации (dynamic routing) различаются по нескольким параметрам. Они могут получать информацию от соседних маршрутизаторов или от всех маршрутизаторов сети. Некоторые меняют путь при смене топологии, другие — через определенные равные интервалы времени по мере изменения нагрузки. Наконец, для оптимизации они используют разные показатели: расстояние, количество транзитных участков (переходов) или ожидаемое время передачи.

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

5.2.1. Принцип оптимальности

Прежде чем перейти к конкретным алгоритмам, сформулируем общее утверждение, описывающее оптимальные маршруты независимо от топологии или трафика, — принцип оптимальности (optimality principle); см. работу Беллмана (Bellman, 1957).

Согласно этому принципу, если