Маршрутизация — это процесс выбора пути для трафика в сети или между несколькими сетями или между ними. В широком смысле маршрутизация выполняется во многих типах сетей, включая сети с коммутацией каналов , такие как телефонная сеть общего пользования (PSTN), и компьютерные сети , такие как Интернет .
В сетях с коммутацией пакетов маршрутизация — это процесс принятия решений более высокого уровня, который направляет сетевые пакеты от источника к месту назначения через промежуточные сетевые узлы с помощью определенных механизмов пересылки пакетов. Пересылка пакетов — это передача сетевых пакетов от одного сетевого интерфейса к другому. Промежуточными узлами обычно являются сетевые устройства, такие как маршрутизаторы , шлюзы , межсетевые экраны или коммутаторы . Компьютеры общего назначения также пересылают пакеты и выполняют маршрутизацию, хотя у них нет специально оптимизированного оборудования для этой задачи.
Процесс маршрутизации обычно управляет пересылкой на основе таблиц маршрутизации . Таблицы маршрутизации хранят записи маршрутов к различным пунктам назначения в сети. Таблицы маршрутизации могут быть заданы администратором, изучены путем наблюдения за сетевым трафиком или построены с помощью протоколов маршрутизации .
Маршрутизация в более узком смысле этого слова часто относится к IP-маршрутизации и противопоставляется мостовому соединению . IP-маршрутизация предполагает, что сетевые адреса структурированы и что сходство адресов подразумевает близость внутри сети. Структурированные адреса позволяют одной записи таблицы маршрутизации представлять маршрут к группе устройств. В больших сетях структурированная адресация (маршрутизация в узком смысле) превосходит неструктурированную адресацию (мост). Маршрутизация стала доминирующей формой адресации в Интернете. Мостовое соединение по-прежнему широко используется в локальных сетях .
Схемы маршрутизации различаются по способу доставки сообщений:
Одноадресная рассылка является доминирующей формой доставки сообщений в Интернете. В этой статье основное внимание уделяется алгоритмам одноадресной маршрутизации.
При статической маршрутизации небольшие сети могут использовать таблицы маршрутизации, настроенные вручную. Более крупные сети имеют сложную топологию , которая может быстро меняться, что делает невозможным ручное построение таблиц маршрутизации. Тем не менее, большая часть коммутируемой телефонной сети общего пользования (PSTN) использует заранее рассчитанные таблицы маршрутизации с резервными маршрутами, если самый прямой маршрут блокируется (см. Маршрутизацию в PSTN ).
Динамическая маршрутизация пытается решить эту проблему путем автоматического построения таблиц маршрутизации на основе информации, передаваемой протоколами маршрутизации , что позволяет сети действовать практически автономно, избегая сетевых сбоев и блокировок. Динамическая маршрутизация доминирует в Интернете. Примеры протоколов и алгоритмов динамической маршрутизации включают протокол информации о маршрутизации (RIP), протокол открытого кратчайшего пути (OSPF) и расширенный протокол маршрутизации внутреннего шлюза (EIGRP).
Алгоритмы вектора расстояния используют алгоритм Беллмана-Форда . Этот подход присваивает номер стоимости каждому каналу между каждым узлом в сети. Узлы отправляют информацию из точки А в точку Б по пути, который приводит к наименьшей общей стоимости (т. е. сумме затрат каналов между используемыми узлами).
Когда узел запускается впервые, он знает только о своих непосредственных соседях и прямых затратах, связанных с их достижением. (Эта информация — список пунктов назначения, общая стоимость каждого из них и следующий переход для отправки данных — составляет таблицу маршрутизации или таблицу расстояний .) Каждый узел регулярно отправляет сообщения каждому соседнему узлу. его собственная текущая оценка общей стоимости поездки до всех известных ему пунктов назначения. Соседние узлы изучают эту информацию и сравнивают ее с тем, что им уже известно; все, что представляет собой улучшение того, что у них уже есть, они вставляют в свою таблицу. Со временем все узлы в сети обнаруживают лучший следующий переход и общую стоимость для всех пунктов назначения.
Когда сетевой узел выходит из строя, любые узлы, которые использовали его в качестве следующего перехода, отбрасывают запись и передают обновленную информацию о маршрутизации всем соседним узлам, которые, в свою очередь, повторяют процесс. В конце концов, все узлы в сети получают обновления и открывают новые пути ко всем пунктам назначения, не затрагивающие нижний узел.
При применении алгоритмов состояния канала графическая карта сети является фундаментальными данными, используемыми для каждого узла. Чтобы создать свою карту, каждый узел заполняет всю сеть информацией о других узлах, к которым он может подключиться. Затем каждый узел независимо собирает эту информацию в карту. Используя эту карту, каждый маршрутизатор независимо определяет путь с наименьшей стоимостью от себя до каждого другого узла, используя стандартный алгоритм кратчайших путей , такой как алгоритм Дейкстры . Результатом является граф дерева с корнем в текущем узле, так что путь через дерево от корня до любого другого узла является путем с наименьшей стоимостью к этому узлу. Затем это дерево служит для построения таблицы маршрутизации, которая определяет лучший следующий переход от текущего узла к любому другому узлу.
Алгоритм маршрутизации по состоянию канала, оптимизированный для мобильных одноранговых сетей, представляет собой оптимизированный протокол маршрутизации по состоянию канала (OLSR). [2] OLSR проявляет инициативу; он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала через мобильную одноранговую сеть. Используя сообщения Hello, каждый узел обнаруживает информацию о соседях с двумя переходами и выбирает набор многоточечных ретрансляторов (MPR). MPR отличает OLSR от других протоколов маршрутизации по состоянию канала.
Вектор расстояния и маршрутизация по состоянию канала являются протоколами внутридоменной маршрутизации. Они используются внутри автономной системы , но не между автономными системами. Оба этих протокола маршрутизации становятся трудноразрешимыми в больших сетях и не могут использоваться при междоменной маршрутизации. Маршрутизация с использованием вектора расстояния может быть нестабильной, если в домене имеется более нескольких переходов. Маршрутизация состояния канала требует значительных ресурсов для расчета таблиц маршрутизации. Это также создает интенсивное движение транспорта из-за наводнений.
Маршрутизация вектора пути используется для междоменной маршрутизации. Это похоже на маршрутизацию вектора расстояния. Маршрутизация по вектору пути предполагает, что один узел (их может быть много) в каждой автономной системе действует от имени всей автономной системы. Этот узел называется узлом динамика. Узел динамика создает таблицу маршрутизации и объявляет ее соседним узлам динамика в соседних автономных системах. Идея такая же, как и маршрутизация по вектору расстояния, за исключением того, что только узлы громкоговорителей в каждой автономной системе могут взаимодействовать друг с другом. Узел-спикер объявляет путь, а не метрику узлов в своей автономной системе или других автономных системах.
Алгоритм маршрутизации вектора пути аналогичен алгоритму вектора расстояния в том смысле, что каждый пограничный маршрутизатор объявляет пункты назначения, которых он может достичь, своему соседнему маршрутизатору. Однако вместо того, чтобы рекламировать сети с точки зрения пункта назначения и расстояния до него, сети рекламируются как адреса назначения и описания пути для достижения этих пунктов назначения. Путь, выраженный в терминах пройденных к настоящему моменту доменов (или конфедераций), передается в специальном атрибуте пути, который записывает последовательность доменов маршрутизации, через которые прошла информация о достижимости. Маршрут определяется как пара между пунктом назначения и атрибутами пути к этому пункту назначения, отсюда и имя, маршрутизация вектора пути; Маршрутизаторы получают вектор, содержащий пути к набору пунктов назначения. [3]
Выбор пути включает в себя применение метрики маршрутизации к нескольким маршрутам для выбора (или прогнозирования) наилучшего маршрута. Большинство алгоритмов маршрутизации используют одновременно только один сетевой путь. Многопутевая маршрутизация и, в частности, методы многопутевой маршрутизации с равной стоимостью позволяют использовать несколько альтернативных путей.
В компьютерных сетях метрика вычисляется с помощью алгоритма маршрутизации и может охватывать такую информацию, как пропускная способность , задержка в сети , количество переходов , стоимость пути, нагрузка, максимальная единица передачи , надежность и стоимость связи. [4] В таблице маршрутизации хранятся только наилучшие возможные маршруты, тогда как базы данных состояния каналов или топологические базы данных могут хранить также всю остальную информацию.
В случае перекрытия или равенства маршрутов алгоритмы учитывают следующие элементы в порядке приоритета, чтобы решить, какие маршруты установить в таблицу маршрутизации:
Поскольку метрика маршрутизации специфична для данного протокола маршрутизации, многопротокольные маршрутизаторы должны использовать некоторую внешнюю эвристику для выбора между маршрутами, полученными из разных протоколов маршрутизации. Например, маршрутизаторы Cisco присваивают каждому маршруту значение, известное как административное расстояние , где меньшие административные расстояния указывают на маршруты, полученные по протоколу, который считается более надежным.
Локальный администратор может настроить маршруты для конкретного хоста, которые обеспечивают больший контроль над использованием сети, позволяют проводить тестирование и повышают общую безопасность. Это полезно для отладки сетевых подключений или таблиц маршрутизации.
В некоторых небольших системах одно центральное устройство заранее определяет полный путь каждого пакета. В некоторых других небольших системах какое бы периферийное устройство ни вводило пакет в сеть, заранее определяет полный путь этого конкретного пакета. В любом случае устройству планирования маршрута необходимо знать много информации о том, какие устройства подключены к сети и как они связаны друг с другом. Получив эту информацию, он может использовать такой алгоритм, как алгоритм поиска A* , чтобы найти лучший путь.
В высокоскоростных системах каждую секунду передается так много пакетов, что одному устройству невозможно вычислить полный путь для каждого пакета. Ранние высокоскоростные системы решали эту проблему с помощью коммутации каналов , устанавливая один раз путь для первого пакета между некоторым источником и некоторым пунктом назначения; более поздние пакеты между тем же источником и тем же пунктом назначения продолжают следовать по тому же пути без перерасчета до тех пор, пока канал не будет разорван . Более поздние высокоскоростные системы вводят пакеты в сеть, причем ни одно устройство никогда не рассчитывает полный путь для пакетов.
В больших системах существует так много соединений между устройствами, и эти соединения меняются так часто, что ни одному устройству невозможно даже знать, как все устройства соединены друг с другом, не говоря уже о том, чтобы вычислить полный путь через них. Такие системы обычно используют маршрутизацию следующего перехода .
Большинство систем используют детерминированный алгоритм динамической маршрутизации . Когда устройство выбирает путь к определенному конечному пункту назначения, оно всегда выбирает один и тот же путь к этому пункту назначения, пока не получит информацию, которая заставит его подумать, что какой-то другой путь лучше.
Некоторые алгоритмы маршрутизации не используют детерминированный алгоритм для поиска наилучшего канала для доставки пакета от исходного источника к конечному пункту назначения. Вместо этого, чтобы избежать перегрузок в пакетных системах, некоторые алгоритмы используют рандомизированный алгоритм — парадигму Валианта — который маршрутизирует путь к случайно выбранному промежуточному пункту назначения, а оттуда к его истинному конечному пункту назначения. [5] [6] Во многих ранних телефонных коммутаторах рандомизатор часто использовался для выбора начала пути через многоступенчатую коммутационную структуру .
В зависимости от приложения, для которого осуществляется выбор пути, могут использоваться разные метрики. Например, для веб-запросов можно использовать пути с минимальной задержкой, чтобы минимизировать время загрузки веб-страницы, а для массовой передачи данных можно выбрать наименее используемый путь, чтобы сбалансировать нагрузку в сети и увеличить пропускную способность. Популярной целью выбора пути является сокращение среднего времени завершения потоков трафика и общего потребления полосы пропускания сети. Недавно была предложена метрика выбора пути, которая вычисляет общее количество байтов, запланированных на ребрах каждого пути, в качестве метрики выбора. [7] Доступен эмпирический анализ нескольких показателей выбора пути, включая это новое предложение. [8]
В некоторых сетях маршрутизация осложняется тем, что ни один объект не отвечает за выбор путей; вместо этого в выборе путей или даже частей одного пути участвуют несколько объектов. Если эти организации выберут пути оптимизации своих собственных целей, которые могут противоречить целям других участников, могут возникнуть осложнения или неэффективность.
Классический пример — дорожное движение, в котором каждый водитель выбирает путь, который сводит к минимуму время в пути. При такой маршрутизации равновесные маршруты могут оказаться длиннее оптимальных для всех водителей. В частности, парадокс Брасса показывает, что добавление новой дороги может увеличить время в пути для всех водителей.
В модели с одним агентом, используемой, например, для маршрутизации автоматически управляемых транспортных средств (AGV) на терминале, резервирование производится для каждого транспортного средства, чтобы предотвратить одновременное использование одной и той же части инфраструктуры. Этот подход также называется контекстно-зависимой маршрутизацией. [9]
Интернет разделен на автономные системы (АС), такие как провайдеры интернет-услуг (ISP), каждая из которых контролирует маршруты, входящие в ее сеть. Маршрутизация происходит на нескольких уровнях. Сначала пути уровня AS выбираются с помощью протокола BGP , который создает последовательность AS, через которые проходят пакеты. Каждая AS может иметь несколько путей, предлагаемых соседними AS, из которых можно выбирать. Эти решения о маршрутизации часто коррелируют с деловыми отношениями с соседними AS, [10] которые могут быть не связаны с качеством пути или задержкой. Во-вторых, после выбора пути на уровне AS часто существует несколько соответствующих путей на уровне маршрутизатора. Частично это связано с тем, что два интернет-провайдера могут быть связаны через несколько соединений. При выборе единственного пути на уровне маршрутизатора каждый Интернет-провайдер обычно использует «горячую» маршрутизацию : передачу трафика по пути, который минимизирует расстояние через собственную сеть Интернет-провайдера, даже если этот путь удлиняет общее расстояние до пункта назначения.
Например, рассмотрим двух интернет-провайдеров : 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] Facebook Express Backbone, [17] и Google B4. [18]
Глобальные показатели производительности, подлежащие оптимизации, включают максимальное использование сети, минимизацию времени завершения потока трафика, максимизацию трафика, доставляемого до определенных сроков, и сокращение времени завершения потоков. [19] В более поздней версии частной глобальной сети рассматривается моделирование маршрутизации как проблемы оптимизации графа путем перемещения всех очередей к конечным точкам. Авторы также предлагают эвристику для эффективного решения проблемы, жертвуя незначительной производительностью. [20]
Для устранения горячих точек сети ... двухфазный алгоритм маршрутизации.
При этом каждый пакет сначала отправляется в случайно выбранный промежуточный пункт назначения;
из промежуточного пункта назначения он пересылается в конечный пункт назначения.
Этот алгоритм, называемый универсальной маршрутизацией, предназначен для максимизации пропускной способности и минимизации задержек в условиях большой нагрузки.
