Введение

Процесс выбора пути в сети передачи данных, маршрутизация в сетях коммутации пакетов.

Маршрутизация – это процесс выбора пути для трафика в сети или между несколькими сетями. В широком смысле маршрутизация выполняется во многих типах сетей, включая сети с коммутацией каналов, такие как общедоступная телефонная сеть (PSTN), и компьютерные сети, такие как Интернет. В сетях коммутации пакетов маршрутизация представляет собой процесс принятия решений на более высоком уровне, направляющий сетевые пакеты от источника к месту назначения через промежуточные сетевые узлы посредством конкретных механизмов пересылки пакетов. Пересылка пакетов – это передача сетевых пакетов от одного сетевого интерфейса к другому. Промежуточные узлы обычно являются сетевыми устройствами, такими как маршрутизаторы, шлюзы, межсетевые экраны или коммутаторы. Компьютеры общего назначения также могут пересылать пакеты и выполнять маршрутизацию, хотя и не имеют специализированного оборудования для этой задачи. Процесс маршрутизации обычно определяет пересылку на основе таблиц маршрутизации. Таблицы маршрутизации содержат записи о маршрутах к различным пунктам назначения сети. Таблицы маршрутизации могут быть заданы администратором, получены путем анализа сетевого трафика или сформированы с использованием протоколов маршрутизации. Маршрутизация, в более узком смысле, часто относится к IP-маршрутизации и противопоставляется коммутации каналов (bridging). IP-маршрутизация предполагает структурированную организацию сетевых адресов, при которой схожие адреса указывают на близость в сети. Структурированные адреса позволяют одной записи в таблице маршрутизации представлять маршрут к группе устройств. В крупных сетях структурированная адресация (маршрутизация в узком смысле) превосходит неструктурированную адресацию (коммутацию каналов). Маршрутизация стала доминирующей формой адресации в Интернете. Коммутация каналов по-прежнему широко используется в локальных сетях.

Топологическое распределение

При статической маршрутизации небольшие сети могут использовать вручную настроенные таблицы маршрутизации. В больших сетях сложные топологии могут быстро меняться, что делает ручное создание таблиц маршрутизации невозможным. Тем не менее, большая часть общедоступной коммутируемой телефонной сети (PSTN) использует предварительно вычисленные таблицы маршрутизации с запасными маршрутами на случай блокировки наиболее прямого маршрута (см. маршрутизация в PSTN). Динамическая маршрутизация пытается решить эту проблему, автоматически формируя таблицы маршрутизации на основе информации, передаваемой маршрутизирующими протоколами, что позволяет сети действовать практически автономно, избегая сбоев и перегрузок сети. Динамическая маршрутизация преобладает в Интернете. Примеры динамических протоколов и алгоритмов маршрутизации включают протокол маршрутной информации (RIP), Open Shortest Path First (OSPF) и Enhanced Interior Gateway Routing Protocol (EIGRP).

Алгоритмы вектора расстояния

Векторные алгоритмы расстояний используют алгоритм Беллмана-Форда. Этот подход присваивает числовое значение стоимости каждой связи между узлами сети. Узлы передают информацию из точки А в точку В по пути, который обеспечивает наименьшую суммарную стоимость (то есть сумму стоимостей связей между используемыми узлами). Когда узел запускается впервые, он знает только о своих непосредственных соседях и прямую стоимость достижения этих соседей. (Эта информация – список пунктов назначения, общая стоимость до каждого из них и следующий узел для отправки данных, чтобы добраться туда – составляет таблицу маршрутизации, или таблицу расстояний.) Каждый узел регулярно отправляет каждому соседнему узлу свою текущую оценку суммарной стоимости достижения всех известных ему пунктов назначения. Соседние узлы анализируют эту информацию и сравнивают ее со своими текущими знаниями; если что-то представляет собой улучшение по сравнению с тем, что у них уже есть, они вносят это в свою таблицу. Со временем все узлы в сети определяют оптимальный следующий узел и суммарную стоимость для всех пунктов назначения. Когда сетевой узел выходит из строя, все узлы, которые использовали его в качестве следующего узла, удаляют соответствующую запись и передают обновленную информацию о маршрутизации всем соседним узлам, которые, в свою очередь, повторяют этот процесс. В конечном итоге все узлы в сети получают обновления и обнаруживают новые пути ко всем пунктам назначения, которые не проходят через вышедший из строя узел.

Алгоритмы состояния связи

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

Оптимизированный алгоритм маршрутизации состояния связи

Алгоритм маршрутизации на основе состояний связей, оптимизированный для мобильных ad hoc сетей, – это оптимизированный протокол маршрутизации на основе состояний связей (OLSR). OLSR является проактивным; он использует сообщения Hello и сообщения управления топологией (TC) для обнаружения и распространения информации о состоянии связей в мобильной ad hoc сети. С помощью сообщений Hello каждый узел обнаруживает информацию о соседях в пределах двух скачков и выбирает набор многоточечных ретрансляторов (MPR). Именно MPR отличают OLSR от других протоколов маршрутизации на основе состояний связей.

Протокол вектора пути

Протоколы векторного расстояния и состояния канала являются протоколами маршрутизации внутри домена. Они используются внутри автономной системы, но не между автономными системами. Оба этих протокола маршрутизации становятся непрактичными в больших сетях и не могут использоваться для междоменной маршрутизации. Маршрутизация по вектору расстояния подвержена нестабильности при наличии более нескольких переходов в домене. Маршрутизация по состоянию канала требует значительных ресурсов для вычисления таблиц маршрутизации, а также создает большой трафик из-за широковещания. Маршрутизация по векторному пути используется для междоменной маршрутизации. Она аналогична маршрутизации по вектору расстояния. Маршрутизация по векторному пути предполагает, что один узел (или несколько) в каждой автономной системе действует от имени всей автономной системы. Этот узел называется узлом-представителем. Узел-представитель создает таблицу маршрутизации и распространяет ее среди соседних узлов-представителей в соседних автономных системах. Идея та же, что и при маршрутизации по вектору расстояния, за исключением того, что обмениваться информацией могут только узлы-представители в каждой автономной системе. Узел-представитель распространяет информацию о пути, а не о метрике узлов в своей автономной системе или других автономных системах. Алгоритм маршрутизации по векторному пути аналогичен алгоритму маршрутизации по вектору расстояния в том смысле, что каждый пограничный маршрутизатор сообщает своим соседним маршрутизаторам о пунктах назначения, до которых он может добраться. Однако вместо того, чтобы сообщать о сетях в терминах пункта назначения и расстояния до него, сети сообщаются как адреса пунктов назначения и описания путей для достижения этих пунктов назначения. Путь, выраженный в терминах пройденных доменов (или конфедераций), содержится в специальном атрибуте пути, который фиксирует последовательность маршрутизирующих доменов, через которые прошла информация о доступности. Маршрут определяется как пара: пункт назначения и атрибуты пути к этому пункту назначения, отсюда и название – маршрутизация по векторному пути. Маршрутизаторы получают вектор, содержащий пути к набору пунктов назначения.

Многочисленные агенты

В некоторых сетях маршрутизация осложняется тем, что ни одна организация не несет ответственности за выбор путей; вместо этого несколько организаций участвуют в выборе путей или даже частей одного пути. Возможны осложнения или неэффективность, если эти организации выбирают пути для оптимизации собственных целей, которые могут противоречить целям других участников. Классическим примером служит дорожное движение, где каждый водитель выбирает путь, минимизирующий время его поездки. При такой маршрутизации равновесные пути могут оказаться длиннее оптимальных для всех водителей. В частности, парадокс Бресса показывает, что добавление новой дороги может увеличить время в пути для всех водителей. В модели единого агента, используемой, например, для маршрутизации автоматизированных управляемых транспортных средств (AGV) на терминале, резервируются ресурсы для каждого транспортного средства, чтобы предотвратить одновременное использование одной и той же части инфраструктуры. Этот подход также называют контекстно-зависимой маршрутизацией. Интернет разделен на автономные системы (АС), такие как интернет-провайдеры (ISP), каждая из которых контролирует маршруты, проходящие через ее сеть. Маршрутизация происходит на нескольких уровнях. Во-первых, пути уровня АС выбираются с помощью протокола BGP, который формирует последовательность АС, через которые передаются пакеты. Каждая АС может иметь несколько путей, предлагаемых соседними АС, из которых можно выбирать. Эти решения о маршрутизации часто коррелируют с деловыми отношениями с этими соседними АС, которые могут не иметь отношения к качеству пути или задержке. Во-вторых, после выбора пути уровня АС часто существует несколько соответствующих путей уровня маршрутизаторов на выбор. Это частично связано с тем, что два ISP могут быть соединены несколькими соединениями. При выборе конкретного пути уровня маршрутизатора, каждый ISP обычно использует стратегию "горячей картошки": отправляет трафик по пути, который минимизирует расстояние внутри собственной сети, даже если это увеличивает общее расстояние до пункта назначения. Например, рассмотрим двух ISP, A и B. У каждого из них есть присутствие в Нью-Йорке, соединенное высокоскоростной линией с задержкой 5 мс, и присутствие в Лондоне, соединенное линией с задержкой 5 мс. Предположим, что у обоих ISP есть трансатлантические линии связи, соединяющие их сети, но задержка в линии A составляет 100 мс, а в линии B – 120 мс. При маршрутизации сообщения из источника в лондонской сети A в пункт назначения в нью-йоркской сети B, A может выбрать немедленную отправку сообщения в B в Лондоне. Это избавляет A от необходимости отправлять сообщение по дорогостоящей трансатлантической линии, но приводит к задержке сообщения в 125 мс, в то время как другой маршрут был бы быстрее на 20 мс. Кроме того, аналогичная проблема маршрутизации может наблюдаться в сотовых сетях, где различные пакеты предназначены для разных конечных точек, и каждая линия связи имеет различную спектральную эффективность. В этом контексте выбор оптимального пути предполагает учет задержки и частоты ошибок пакетов. Для решения этой задачи несколько независимых организаций, по одной для каждой базовой станции, играют ключевую роль в выборе пути, стремясь оптимизировать общую производительность сети. Исследование интернет-маршрутов, проведенное в 2003 году, показало, что между парами соседних ISP более 30% путей имеют увеличенную задержку из-за маршрутизации "горячей картошки", при этом 5% путей задерживаются не менее чем на 12 мс. Увеличение задержки, связанное с выбором пути уровня АС, хотя и значительное, было в основном обусловлено отсутствием в BGP механизма прямой оптимизации задержки, а не эгоистичной политикой маршрутизации. Также было предположено, что при наличии подходящего механизма ISP были бы готовы сотрудничать для снижения задержки, а не использовать маршрутизацию "горячей картошки". Позже те же авторы опубликовали такой механизм, сначала для случая двух ISP, а затем для глобального случая.

Анализ маршрутов

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

Централизованная маршрутизация

В сетях, где доступно логически централизованное управление состоянием пересылки, например, с использованием технологий программно-определяемых сетей (SDN), можно использовать методы маршрутизации, направленные на оптимизацию глобальных и общесетевых показателей производительности. Это применяется крупными интернет-компаниями, которые управляют множеством центров обработки данных в различных географических регионах, соединенных частными оптическими каналами связи, такими как Global WAN от Microsoft, Express Backbone от Facebook и B4 от Google. Глобальные показатели производительности, подлежащие оптимизации, включают максимизацию загрузки сети, минимизацию времени завершения потоков трафика, максимизацию объема трафика, доставленного до определенных сроков, и сокращение времени завершения потоков. В работах, посвященных частным глобальным сетям (WAN), рассматривается моделирование маршрутизации как задачи оптимизации графа путем перенесения всей обработки очередей на конечные точки. Авторы также предлагают эвристический алгоритм для эффективного решения этой задачи с незначительной потерей производительности.