Маршрутизация

В среде передачи данных по пакетам, как, например, в интернете, логически адресованные пакеты данных выводятся за пределы исходной подсети и передаются в сторону целевой сети. Маршрутизация составляет основу работы интернета — без неё сама инфраструктура сети была бы невозможна, а все подсети существовали бы обособленно. На пути к пункту назначения пакеты могут проходить через множество промежуточных сетей. В интернете процесс маршрутизации обычно происходит на уровне IP-протокола. В модели OSI маршрутизация — ключевая функция третьего уровня.

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

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

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

На основе маршрутных таблиц маршрутизатор строит специальную forwarding-таблицу (таблицу пересылки), содержащую сопоставления "шаблон адреса назначения → выходной интерфейс". При обработке каждого входящего пакета маршрутизатор определяет, по какому интерфейсу передавать пакет дальше, опираясь на эту таблицу.

В локальных сетях широко используется так называемая маршрутизация с указанием источника (англ. source routing). В этом случае исходная станция знает весь путь к станции назначения и заносит адрес следующего сетевого узла в заголовок сообщения. Каждый следующий узел повторяет этот процесс, следуя заранее заданному маршруту. Такой подход применяется, например, в Usenet Mail Service.

Одним из популярных примеров является динамическая маршрутизация источником (англ. Dynamic Source Routing), при которой исходная станция находит допустимый маршрут к пункту назначения через процедуру обнаружения маршрута (route discovery), после чего путь сохраняется в заголовке каждого пакета. Каждый промежуточный узел обязан переслать пакет по указанному маршруту, а в двусторонних беспроводных сетях корректность пересылки может контролироваться предыдущим hop-узлом.

Протоколы маршрутизации обеспечивают обмен маршрутной информацией между сетями и позволяют маршрутизаторам строить свои таблицы динамически. Традиционная IP-маршрутизация проста, поскольку реализует принцип "next-hop routing": маршрутизатор отправляет пакет ближайшему по его представлению наиболее выгодному соседу на пути к целевой сети. Если такой выбор оказался неверным, пакет всё равно, как правило, достигает своего назначения.

Динамическая маршрутизация, несмотря на сложность, значительно увеличила гибкость интернета и позволила ему экспоненциально расти после появления IP в 1983 году. При сбоях в магистралях интернета (например, летом 2002 года, когда оператор KPNQwest отключил свою европейскую сеть волоконно-оптической связи из-за банкротства) протоколы позволяют в течение секунд переложить трафик по альтернативным маршрутам, что предотвращает масштабные сбои.

Однако сбоя стандартного шлюза (обычно первого маршрутизатора на пути) динамическая маршрутизация не компенсирует: если у хоста нет альтернативы стандартному шлюзу, именно этот маршрутизатор становится критическим. Для решения данной проблемы были разработаны протоколы HSRP, VRRP и CARP.

Алгоритмы маршрутизации применяют два основных подхода:

• Сообщать всем сетевым участникам своих соседей: протоколы типа англ. Link-State (например, OSPF) предоставляют каждому маршрутизатору полную топологию сети, благодаря чему он может самостоятелно рассчитывать кратчайшие маршруты.
• Сообщать только соседям свою «картину мира»: протоколы типа англ. Distance Vector (например, Routing Information Protocol — RIP) обмениваются информацией о стоимости маршрута до различных целевых узлов. Выбирая для передачи пакет ближайшего «наилучшего» соседа к цели, решение о кратчайшем пути распределяется между несколькими маршрутизаторами.
  • Более сложный вариант — англ. Path Vector-протоколы (например, Border Gateway Protocol — BGP^[1]), в которых применяется улучшенная обработка циклов.

Кроме того, алгоритмы маршрутизации различаются по степени централизации и динамичности:

• Централизация: где локализован алгоритм — централизованно в управляющем центре сети или распределён по всем узлам?
• Динамичность: адаптивен ли алгоритм, т.е. зависит ли актуальная маршрутная таблица от состояния сети (топология, загрузка), либо её значения относительно постоянны?

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

К типам алгоритмов маршрутизации относятся:

• Статическая маршрутизация
• Централизованная маршрутизация
• Delta routing
• Многоточечная (broadcast) маршрутизация
• Hot Potato
• Backward Learning, распределённая адаптивная маршрутизация (RIP, OSPF, IS-IS и др.)

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

Является адаптивной технологией. В сети присутствует центр управления маршрутизацией (Routing Control Center, RCC), получающий от всех узлов данные о состоянии (например, список активных соседей, имеются очереди и объём переданного трафика). Центр рассчитывает оптимальные пути с учётом всей топологии и рассылает новые маршрутные таблицы по узлам.

Преимущества:

• Центр управления владеет доступом ко всей информации и принимает оптимальные решения;
• Узлам не надо проводить сложные вычисления.

Недостатки:

• Сложность расчётов для крупных сетей;
• Сбой центра парализует всю сеть при отсутствии резервного комплекса;
• Возможна рассинхронизация, когда более отдалённые от центра узлы получают новые таблицы позже;
• Центр управления испытывает значительную нагрузку.

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

К числу таких методов относятся:

• Многоточечная (broadcast) маршрутизация
• Hot Potato
• Backward Learning
• Delta Routing

В этом случае пакет отправляется всем участникам сети. Существует две разновидности: создание отдельных копий для каждого узла или метод «затопления». Последний предельно прост и неадаптивен: входящий пакет передаётся по всем направлениям, кроме того, откуда он пришёл. Для борьбы с лавинообразным ростом пакетов можно использовать:

• обнаружение дубликатов по номерам пакетов,
• контроль времени жизни (подсчёт хопов — переходов),
• избирательное затопление (выделение только некоторых направлений),
• случайный отбор направления (random walk).

В этой схеме каждый узел старается максимально быстро избавиться от входящего пакета (аналогия с «горячей картошкой»). В «cold potato routing» напротив, узел задерживает передачу до появления оптимального выхода. На практике часто применяется комбинация с статической маршрутизацией^[2]: если основной ("лучший") выход свободен, пакет пересылается по нему; в случае занятости выбирается любой другой свободный выход, даже если он менее предпочтителен.

Плюсы:

• Быстрое принятие решений;
• Минимальные требования к вычислениям;
• Хорошее распределение нагрузки.

Минусы:

• При росте нагрузки оптимальность падает;
• Возможны циклы (пакеты проходят один маршрутизатор несколько раз).

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

В таком сценарии в пакетах хранятся:

• идентификатор источника;
• счётчик хопов (увеличивается на каждом переходе).

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

Является комбинацией централизованного и изолированного подходов: каждый узел периодически оценивает стоимость своих связей (например, по задержке, загрузке, пропускной способности) и отправляет их в центр управления. Центр вычисляет k лучших маршрутов между i и j (для всех пар), выбирая только те, которые различаются по начальному каналу. Узлы хранят список таких эквивалентных маршрутов и могут выбирать между ними по реальным затратам.

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

• количество хопов (переходов),
• оценочная задержка в миллисекундах,
• оценочное количество ожидающих пакетов.

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

К главным протоколам этого типа относятся:

• distance vector routing
• link state routing

Протоколы типа distance vector используют для определения маршрута вектор направления и расстояния (метрика — количество переходов). Для вычисления маршрута обычно применяется алгоритм Беллмана — Форда.

Изменения в топологии сети приводят к рассылке обновлений: если маршрутизатор фиксирует сбой связи или соседа, пересчитывается путь и отправляются соответствующие уведомления. Процесс доходит до согласования между всеми участниками, однако конвергенция может занимать слишком много времени (проблема "count-to-infinity"^[3]).

К данному типу относится, например, RIP.

Link state-протоколы являются альтернативой distance vector и призваны компенсировать их недостатки. В отличие от distance vector, где каждый узел знает только о своих соседях, link state-протоколы позволяют каждому маршрутизатору владеть полной топологией сети, которая хранится в виде базы данных топологии (аналог подробной карты, одинаковой у всех внутри одной зоны).

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

Для актуализации данных link state-протоколы отправляют обновления только при изменении топологии (новый маршрутизатор, отключение, смена стоимости связи) или периодически раз в 30 минут.

К таким протоколам относятся OSPF и IS-IS.

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

Маршрутная метрика — это численный показатель, который помогает алгоритму маршрутизации сравнивать маршруты между собой. К числу учитываемых параметров могут относиться пропускная способность, задержка, число хопов, стоимость пути, нагрузка, MTU, надёжность и стоимость передачи. Например, если оптимальной считается минимальная дистанция, из всех возможных маршрутов будет выбран тот, что имеет наименьшую величину метрики. Однако если алгоритм оперирует параметрами вроде пропускной способности, там самый высокий показатель может означать наилучший маршрут. Маршрутные таблицы чаще всего содержат только оптимальные маршруты, а link-state или базы топологий — всю исходную информацию. Выбор метрики зависит от конкретного протокола: например, RIP учитывает только количество хопов, игнорируя пропускную способность.

В интернете различают два основных типа маршрутизации в зависимости от области применения:

• внутридоменная (intra-domain routing) — внутри автономной системы (AS);
• междоменная (inter-domain routing) — между разными автономными системами.

Термин «domain» здесь относится к автономной системе, а не к DNS-доменам сайтов.

Внутридоменная маршрутизация использует так называемые interior gateway protocols (IGP). Как правило, её цель — «техническая» эффективность: выбор кратчайших путей, максимизация пропускной способности реального трафика. Оптимизация такой маршрутизации называется трафик-инжинирингом.

Для обмена между автономными системами применяются exterior gateway protocols (EGP), фактически почти всегда — BGP. Основная задача междоменного маршрутизирования — обеспечение финансово эффективной эксплуатации собственной сети. Для этого не все маршруты и информации обмениваются с соседями. Как правило, содержание и правила обмена фиксируются в договорах и реализуются настройками маршрутизаторов (policy-based routing).

Некоторые протоколы, например, исходный NetBIOS, не поддерживают маршрутизацию: адресация возможна только по MAC-адресу сетевой карты. То же справедливо и для IP-коммуникаций внутри одной подсети — после определения MAC-адреса по протоколу ARP или NDP пакеты содержат одновременно MAC- и IP-адреса отправителя и получателя.

Когда источник и получатель находятся в разных сетях, требуется маршрутизатор. Если компьютер (например, Telnet-клиент) передаёт пакет за пределы своей сети, он определяет ближайший маршрутизатор, получает по ARP его MAC-адрес и формирует пакет, где:

• MAC-адрес назначения — адрес маршрутизатора,
• IP-адрес назначения — адрес получателя,
• порт назначения — номер порта (например, 23 для Telnet-сервера),
• MAC и IP-адреса отправителя, используемый локально порт,
• остальные данные.

Маршрутизатор, приняв «свой» пакет, ищет следующего маршрутизатора, снова определяет его MAC-адрес и меняет в пакете адрес на следующий по пути, IP- и портовые адреса не затрагиваются. Так процесс повторяется до тех пор, пока предпоследний маршрутизатор не пересылает пакет в локальную сеть приёмника, где меняется только MAC-адрес назначения.

Ответ сервера формируется аналогично: адрес маршрутизатора, отвечающего за возврат, IP-адрес клиента, нужный порт (например, 5387), MAC и IP-адрес сервера и данные ответа. После всех переходов последний маршрутизатор формирует пакет с нужным MAC- и IP-адресом клиента, портом и отвечает обратно.

При завершении сессии (например, Telnet) временный порт освобождается.

В зависимости от положения маршрутизатора в сети (является ли он частью или границей автономной системы), он может одновременно использовать route-протоколы разных классов:

• Interior Gateway Protocols (IGP, внутренние) — для обмена маршрутами в одной автономной системе. Наиболее известные:
  • IGRP/EIGRP
  • OSPF
  • IS-IS
  • RIP
  • R-SMLT
• Exterior Gateway Protocols (EGP, внешние) — маршрутизация между автономными системами:
  • BGP (глобальный стандарт BGP4, с 2002 года)
  • EGP (устаревший стандарт, ранее связывал backbone-сети интернета)
• Ad hoc-протоколы маршрутизации используются в сетях с минимальной или отсутствующей инфраструктурой:
  • OLSR — обычно в мобильных сетях;
  • AODV — применяется в небольших сетях со статическим трафиком.

Протоколы могут взаимодействовать: например, внутренние маршруты (IGP) можно экспортировать во внешние (EGP). При противоречиях между маршрутами, полученными из разных протоколов, выбор определяет административное расстояние (administrative distance).

* различные (или их комбинации) метрики

В рамках производственного планирования под маршрутизацией подразумевается определение последовательности операций в составе сложных технологических процессов. В промышленности для каждого объекта составляется технологическая карта и/или маршрутный лист, которые сопровождают изделие и фиксируют его статус после каждого этапа^[4].