Маршрутизация — это процесс выбора пути для трафика в сети или между или через несколько сетей. В широком смысле маршрутизация выполняется во многих типах сетей, включая сети с коммутацией каналов , такие как телефонная сеть общего пользования (PSTN), и компьютерные сети , такие как Интернет .
В сетях с коммутацией пакетов маршрутизация — это процесс принятия решений на более высоком уровне, который направляет сетевые пакеты от источника к месту назначения через промежуточные сетевые узлы с помощью специальных механизмов пересылки пакетов. Пересылка пакетов — это транзит сетевых пакетов от одного сетевого интерфейса к другому. Промежуточные узлы — это обычно сетевые аппаратные устройства, такие как маршрутизаторы , шлюзы , брандмауэры или коммутаторы . Компьютеры общего назначения также пересылают пакеты и выполняют маршрутизацию, хотя у них нет специально оптимизированного оборудования для этой задачи.
Процесс маршрутизации обычно направляет пересылку на основе таблиц маршрутизации . Таблицы маршрутизации поддерживают запись маршрутов к различным сетевым пунктам назначения. Таблицы маршрутизации могут быть указаны администратором, изучены путем наблюдения за сетевым трафиком или построены с помощью протоколов маршрутизации .
Маршрутизация, в более узком смысле этого термина, часто относится к IP-маршрутизации и противопоставляется мостовому соединению . IP-маршрутизация предполагает, что сетевые адреса структурированы и что схожие адреса подразумевают близость внутри сети. Структурированные адреса позволяют одной записи таблицы маршрутизации представлять маршрут к группе устройств. В больших сетях структурированная адресация (маршрутизация, в узком смысле) превосходит неструктурированную адресацию (мостовое соединение). Маршрутизация стала доминирующей формой адресации в Интернете. Мостовое соединение по-прежнему широко используется в локальных сетях .
Схемы маршрутизации различаются по способу доставки сообщений:
Unicast — доминирующая форма доставки сообщений в Интернете. В этой статье рассматриваются алгоритмы маршрутизации unicast.
При статической маршрутизации небольшие сети могут использовать вручную настроенные таблицы маршрутизации. Более крупные сети имеют сложную топологию , которая может быстро меняться, что делает ручное построение таблиц маршрутизации невозможным. Тем не менее, большая часть телефонной сети общего пользования (PSTN) использует предварительно вычисленные таблицы маршрутизации с резервными маршрутами, если наиболее прямой маршрут блокируется (см. маршрутизацию в PSTN ).
Динамическая маршрутизация пытается решить эту проблему, автоматически создавая таблицы маршрутизации на основе информации, передаваемой протоколами маршрутизации , что позволяет сети действовать практически автономно, избегая сетевых сбоев и блокировок. Динамическая маршрутизация доминирует в Интернете. Примерами протоколов и алгоритмов динамической маршрутизации являются Routing Information Protocol (RIP), Open Shortest Path First (OSPF) и Enhanced Interior Gateway Routing Protocol (EIGRP).
Алгоритмы векторов расстояний используют алгоритм Беллмана–Форда . Этот подход назначает номер стоимости каждой из связей между каждым узлом в сети. Узлы отправляют информацию из точки A в точку B по пути, который приводит к наименьшей общей стоимости (т. е. сумме стоимостей связей между используемыми узлами).
Когда узел впервые запускается, он знает только о своих непосредственных соседях и прямых затратах на их достижение. (Эта информация — список пунктов назначения, общая стоимость для каждого и следующий переход для отправки данных, чтобы добраться туда, — составляет таблицу маршрутизации или таблицу расстояний .) Каждый узел на регулярной основе отправляет каждому соседнему узлу свою собственную текущую оценку общей стоимости, чтобы добраться до всех известных ему пунктов назначения. Соседние узлы проверяют эту информацию и сравнивают ее с тем, что они уже знают; все, что представляет собой улучшение того, что у них уже есть, они вставляют в свою собственную таблицу. Со временем все узлы в сети обнаруживают лучший следующий переход и общую стоимость для всех пунктов назначения.
Когда сетевой узел выходит из строя, все узлы, которые использовали его в качестве следующего перехода, отбрасывают запись и передают обновленную информацию о маршрутизации всем соседним узлам, которые, в свою очередь, повторяют процесс. В конечном итоге все узлы в сети получают обновления и находят новые пути ко всем пунктам назначения, которые не включают в себя вышедший из строя узел.
При применении алгоритмов состояния канала графическая карта сети является основными данными, используемыми для каждого узла. Для создания своей карты каждый узел наполняет всю сеть информацией о других узлах, к которым он может подключиться. Затем каждый узел независимо собирает эту информацию в карту. Используя эту карту, каждый маршрутизатор независимо определяет наименее затратный путь от себя до каждого другого узла, используя стандартный алгоритм кратчайших путей , такой как алгоритм Дейкстры . Результатом является древовидный граф с корнем в текущем узле, такой что путь через дерево от корня до любого другого узла является наименее затратным путем к этому узлу. Затем это дерево служит для построения таблицы маршрутизации, которая указывает наилучший следующий переход для перехода от текущего узла к любому другому узлу.
Алгоритм маршрутизации по состоянию канала, оптимизированный для мобильных сетей ad hoc, — это оптимизированный протокол маршрутизации по состоянию канала (OLSR). [2] OLSR является проактивным; он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала через мобильную сеть ad hoc. Используя сообщения Hello, каждый узел обнаруживает информацию о соседях с 2 переходами и выбирает набор многоточечных ретрансляторов (MPR). MPR отличают OLSR от других протоколов маршрутизации по состоянию канала.
Маршрутизация по вектору расстояния и по состоянию канала являются протоколами внутридоменной маршрутизации. Они используются внутри автономной системы , но не между автономными системами. Оба эти протокола маршрутизации становятся неуправляемыми в больших сетях и не могут использоваться в междоменной маршрутизации. Маршрутизация по вектору расстояния подвержена нестабильности, если в домене больше нескольких переходов. Маршрутизация по состоянию канала требует значительных ресурсов для расчета таблиц маршрутизации. Она также создает большой трафик из-за лавинной маршрутизации.
Маршрутизация по вектору пути используется для междоменной маршрутизации. Она похожа на маршрутизацию по вектору расстояния. Маршрутизация по вектору пути предполагает, что один узел (их может быть много) в каждой автономной системе действует от имени всей автономной системы. Этот узел называется узлом- спикером. Узел-спикер создает таблицу маршрутизации и объявляет ее соседним узлам-спикерам в соседних автономных системах. Идея та же, что и у маршрутизации по вектору расстояния, за исключением того, что только узлы-спикеры в каждой автономной системе могут общаться друг с другом. Узел-спикер объявляет путь, а не метрику узлов в своей автономной системе или других автономных системах.
Алгоритм маршрутизации path-vector похож на алгоритм маршрутизации distance-vector в том смысле, что каждый пограничный маршрутизатор объявляет пункты назначения, которых он может достичь, своему соседнему маршрутизатору. Однако вместо объявления сетей в терминах пункта назначения и расстояния до этого пункта назначения, сети объявляются в виде адресов назначения и описаний путей для достижения этих пунктов назначения. Путь, выраженный в терминах доменов (или конфедераций), пройденных до сих пор, переносится в специальном атрибуте пути, который записывает последовательность доменов маршрутизации, через которые прошла информация о достижимости. Маршрут определяется как сопряжение между пунктом назначения и атрибутами пути к этому пункту назначения, отсюда и название, маршрутизация path-vector; Маршрутизаторы получают вектор, который содержит пути к набору пунктов назначения. [3]
Выбор пути подразумевает применение метрики маршрутизации к нескольким маршрутам для выбора (или прогнозирования) наилучшего маршрута. Большинство алгоритмов маршрутизации используют только один сетевой путь за раз. Многопутевая маршрутизация и, в частности, методы многопутевой маршрутизации с равной стоимостью позволяют использовать несколько альтернативных путей.
В компьютерных сетях метрика вычисляется алгоритмом маршрутизации и может охватывать такую информацию, как пропускная способность , задержка сети , количество переходов , стоимость пути, нагрузка, максимальная единица передачи , надежность и стоимость связи. [4] Таблица маршрутизации хранит только наилучшие возможные маршруты, в то время как базы данных о состоянии каналов или топологические базы данных могут хранить также всю другую информацию.
В случае перекрывающихся или одинаковых маршрутов алгоритмы учитывают следующие элементы в порядке приоритета, чтобы решить, какие маршруты следует установить в таблицу маршрутизации:
Поскольку метрика маршрутизации специфична для данного протокола маршрутизации, многопротокольные маршрутизаторы должны использовать некоторую внешнюю эвристику для выбора между маршрутами, полученными из разных протоколов маршрутизации. Например, маршрутизаторы Cisco приписывают каждому маршруту значение, известное как административное расстояние , где меньшие административные расстояния указывают на маршруты, полученные из протокола, который считается более надежным.
Локальный администратор может настроить маршруты, специфичные для хоста, которые обеспечивают больший контроль над использованием сети, разрешают тестирование и повышают общую безопасность. Это полезно для отладки сетевых подключений или таблиц маршрутизации.
В некоторых небольших системах одно центральное устройство заранее определяет полный путь каждого пакета. В некоторых других небольших системах любое периферийное устройство, которое вводит пакет в сеть, заранее определяет полный путь этого конкретного пакета. В любом случае устройству планирования маршрута необходимо знать много информации о том, какие устройства подключены к сети и как они подключены друг к другу. Получив эту информацию, оно может использовать алгоритм, например алгоритм поиска A*, чтобы найти наилучший путь.
В высокоскоростных системах каждую секунду передается так много пакетов, что для одного устройства невозможно рассчитать полный путь для каждого пакета. Ранние высокоскоростные системы справлялись с этим с помощью коммутации каналов , устанавливая путь один раз для первого пакета между некоторым источником и некоторым пунктом назначения; последующие пакеты между тем же источником и тем же пунктом назначения продолжают следовать по тому же пути без пересчета до разрыва цепи . Более поздние высокоскоростные системы вводят пакеты в сеть, и ни одно устройство никогда не вычисляет полный путь для пакетов.
В больших системах существует так много соединений между устройствами, и эти соединения меняются так часто, что для любого устройства невозможно даже знать, как все устройства соединены друг с другом, не говоря уже о том, чтобы вычислить полный путь через них. Такие системы обычно используют маршрутизацию следующего перехода .
Большинство систем используют детерминированный алгоритм динамической маршрутизации . Когда устройство выбирает путь к определенному конечному пункту назначения, это устройство всегда выбирает один и тот же путь к этому пункту назначения, пока не получит информацию, которая заставит его подумать, что какой-то другой путь лучше.
Несколько алгоритмов маршрутизации не используют детерминированный алгоритм для поиска наилучшего пути для пакета от его исходного источника до его конечного пункта назначения. Вместо этого, чтобы избежать перегруженных точек в пакетных системах, несколько алгоритмов используют рандомизированный алгоритм — парадигму Валианта — который прокладывает путь к случайно выбранному промежуточному пункту назначения, а оттуда к его истинному конечному пункту назначения. [5] [6] Во многих ранних телефонных коммутаторах рандомизатор часто использовался для выбора начала пути через многоступенчатую коммутационную матрицу .
В зависимости от приложения, для которого выполняется выбор пути, могут использоваться различные метрики. Например, для веб-запросов можно использовать пути с минимальной задержкой, чтобы минимизировать время загрузки веб-страницы, или для передачи больших объемов данных можно выбрать наименее используемый путь, чтобы сбалансировать нагрузку по сети и увеличить пропускную способность. Популярная цель выбора пути — сократить среднее время завершения потоков трафика и общее потребление полосы пропускания сети. Недавно была предложена метрика выбора пути, которая вычисляет общее количество байтов, запланированных на ребрах на путь, в качестве метрики выбора. [7] Был предоставлен эмпирический анализ нескольких метрик выбора пути, включая это новое предложение. [8]
В некоторых сетях маршрутизация осложняется тем, что ни один субъект не отвечает за выбор путей; вместо этого в выборе путей или даже частей одного пути участвуют несколько субъектов. Сложности или неэффективность могут возникнуть, если эти субъекты выбирают пути для оптимизации своих собственных целей, которые могут конфликтовать с целями других участников.
Классический пример — движение в дорожной системе, в которой каждый водитель выбирает путь, который минимизирует время в пути. При такой маршрутизации равновесные маршруты могут быть длиннее оптимальных для всех водителей. В частности, парадокс Браеса показывает, что добавление новой дороги может увеличить время в пути для всех водителей.
В одноагентной модели, используемой, например, для маршрутизации автоматизированных управляемых транспортных средств (AGV) на терминале, резервирование выполняется для каждого транспортного средства, чтобы предотвратить одновременное использование одной и той же части инфраструктуры. Этот подход также называется контекстно-зависимой маршрутизацией. [9]
Интернет разделен на автономные системы (AS), такие как поставщики интернет-услуг (ISP), каждый из которых контролирует маршруты, включающие его сеть. Маршрутизация происходит на нескольких уровнях. Во-первых, пути уровня AS выбираются с помощью протокола BGP , который создает последовательность AS, через которые проходят пакеты. У каждого AS может быть несколько путей, предлагаемых соседними AS, из которых можно выбирать. Эти решения о маршрутизации часто коррелируют с деловыми отношениями с этими соседними AS, [10] которые могут быть не связаны с качеством пути или задержкой. Во-вторых, после выбора пути уровня AS часто есть несколько соответствующих путей уровня маршрутизатора для выбора. Это отчасти связано с тем, что два ISP могут быть подключены через несколько соединений. При выборе одного пути уровня маршрутизатора для каждого ISP общепринятой практикой является использование маршрутизации «горячая картошка» : отправка трафика по пути, который минимизирует расстояние через собственную сеть ISP, даже если этот путь удлиняет общее расстояние до пункта назначения.
Например, рассмотрим двух интернет-провайдеров, A и B. Каждый из них имеет представительство в Нью-Йорке , соединенное быстрым каналом с задержкой5 мс — и у каждого есть представительство в Лондоне , соединенное 5-мс каналом. Предположим, что у обоих провайдеров есть трансатлантические каналы, соединяющие их две сети, но канал A имеет задержку 100 мс, а канал B — 120 мс. При маршрутизации сообщения от источника в лондонской сети A к пункту назначения в нью-йоркской сети B, A может решить немедленно отправить сообщение B в Лондон. Это экономит A работу по отправке его по дорогостоящему трансатлантическому каналу, но приводит к тому, что сообщение испытывает задержку 125 мс, когда другой маршрут был бы на 20 мс быстрее.
Кроме того, похожая проблема маршрутизации может наблюдаться в сотовых сетях, где разные пакеты предназначены для разных конечных точек, и каждое соединение демонстрирует различную спектральную эффективность. В этом контексте выбор оптимального пути включает в себя учет задержки и частоты ошибок пакетов. Чтобы решить эту проблему, несколько независимых сущностей, по одной на каждую базовую станцию, играют решающую роль в выборе пути, стремясь оптимизировать общую производительность сети. [11]
Исследование измерений интернет-маршрутов 2003 года показало, что между парами соседних интернет-провайдеров более 30% путей имеют завышенную задержку из-за маршрутизации по принципу «горячая картошка», при этом 5% путей задерживаются не менее чем на 12 мс. Задержка из-за выбора пути на уровне AS, хотя и существенная, в первую очередь объясняется отсутствием в BGP механизма прямой оптимизации задержки, а не эгоистичными политиками маршрутизации. Также было высказано предположение, что при наличии подходящего механизма интернет-провайдеры будут готовы сотрудничать для сокращения задержки, а не использовать маршрутизацию по принципу «горячая картошка». [12] Такой механизм был позже опубликован теми же авторами, сначала для случая двух интернет-провайдеров [13], а затем для глобального случая. [14]
Поскольку Интернет и IP-сети стали критически важными бизнес-инструментами, возрос интерес к методам и приемам мониторинга состояния маршрутизации сетей. Неправильная маршрутизация или проблемы с маршрутизацией приводят к нежелательному снижению производительности, нестабильности или простоям. Мониторинг маршрутизации в сети осуществляется с помощью инструментов и приемов анализа маршрутов . [15]
В сетях, где логически централизованный контроль над состоянием пересылки доступен, например, с использованием программно-определяемых сетей , могут использоваться методы маршрутизации, направленные на оптимизацию глобальных и общесетевых показателей производительности. Это использовалось крупными интернет-компаниями, которые управляют множеством центров обработки данных в разных географических точках, подключенных с помощью частных оптических каналов, примерами которых являются Global WAN от Microsoft, [16] Express Backbone от Facebook, [17] и B4 от Google. [18]
Глобальные показатели производительности для оптимизации включают максимизацию использования сети, минимизацию времени завершения потока трафика, максимизацию трафика, доставленного до определенных крайних сроков, и сокращение времени завершения потоков. [19] Работа над более поздней версией частной WAN обсуждает моделирование маршрутизации как проблему оптимизации графа путем перемещения всех очередей в конечные точки. Авторы также предлагают эвристику для эффективного решения проблемы, жертвуя незначительной производительностью. [20]
Чтобы устранить горячие точки сети, ... двухфазный алгоритм маршрутизации. Он включает в себя отправку каждого пакета сначала в случайно выбранный промежуточный пункт назначения; из промежуточного пункта назначения он пересылается в конечный пункт назначения. Этот алгоритм, называемый универсальной маршрутизацией, предназначен для максимизации пропускной способности и минимизации задержки в условиях большой нагрузки.
