Войти
Маршрутизация - это процесс выбора пути для трафика в сети, между или между несколькими сетями. В общем, маршрутизация выполняется во многих типах сетей, включая сети с коммутацией каналов, такие как коммутируемая телефонная сеть общего пользования (PSTN) и компьютерные сети, например, Интернет.
. В сетях с коммутацией пакетов маршрутизация - это процесс принятия решений на более высоком уровне, который направляет сетевые пакеты от их источника к месту назначения через промежуточные сетевые узлы посредством специальные механизмы пересылки пакетов. Пересылка пакетов - это передача сетевых пакетов от одного сетевого интерфейса к другому. Промежуточные узлы обычно представляют собой сетевое оборудование устройства, такие как маршрутизаторы, шлюзы, межсетевые экраны или коммутаторы. Универсальные компьютеры также пересылают пакеты и выполняют маршрутизацию, хотя у них нет специально оптимизированного оборудования для этой задачи.
Процесс маршрутизации обычно управляет пересылкой на основе таблиц маршрутизации. Таблицы маршрутизации содержат записи маршрутов к различным сетевым пунктам назначения. Таблицы маршрутизации могут быть указаны администратором, изучены путем наблюдения за сетевым трафиком или созданы с помощью протоколов маршрутизации.
Маршрутизация в более узком смысле этого слова часто относится к IP-маршрутизации и контрастирует с мостом. IP-маршрутизация предполагает, что сетевые адреса структурированы и что аналогичные адреса подразумевают близость в сети. Структурированные адреса позволяют одной записи в таблице маршрутизации представлять маршрут к группе устройств. В больших сетях структурированная адресация (маршрутизация в узком смысле) превосходит неструктурированную адресацию (мостовое соединение). Маршрутизация стала доминирующей формой адресации в Интернете. Мостовое соединение по-прежнему широко используется в локальных сетях.
| Схемы маршрутизации |
|---|
| Unicast
|
| Broadcast
|
| Multicast
|
| Anycast
|
| Geocast
|
|
Схемы маршрутизации различаются по способу доставки сообщений:
Одноадресная передача является доминирующей формой доставки сообщений в Интернете. Эта статья посвящена алгоритмам одноадресной маршрутизации.
При статической маршрутизации небольшие сети могут использовать вручную настроенные таблицы маршрутизации. Более крупные сети имеют сложную топологию, которая может быстро меняться, что делает невозможным создание таблиц маршрутизации вручную. Тем не менее, большая часть коммутируемой телефонной сети общего пользования (PSTN) использует предварительно вычисленные таблицы маршрутизации с резервными маршрутами, если наиболее прямой маршрут становится заблокированным (см. маршрутизация в PSTN ).
Динамическая маршрутизация пытается решить эту проблему путем автоматического построения таблиц маршрутизации на основе информации, переносимой протоколами маршрутизации, что позволяет сети действовать практически автономно, избегая сетевых сбоев и блокировок. В Интернете доминирует динамическая маршрутизация. Примеры протоколов и алгоритмов динамической маршрутизации включают Протокол информации о маршрутизации (RIP), Первый открытый кратчайший путь (OSPF) и Расширенный протокол маршрутизации внутреннего шлюза (EIGRP).
Алгоритмы вектора расстояния используют алгоритм Беллмана – Форда. Этот подход присваивает номер стоимости каждому каналу между каждым узлом в сети. Узлы отправляют информацию из точки A в точку B по пути, который приводит к наименьшей общей стоимости (т. Е. Сумме затрат на связи между используемыми узлами).
Когда узел запускается впервые, он знает только о своих непосредственных соседях и о прямых затратах на их достижение. (Эта информация - список пунктов назначения, общая стоимость каждого из них и следующий переход для отправки данных, чтобы добраться туда - составляет таблицу маршрутизации или таблицу расстояний.) Каждый узел на регулярной основе отправляет каждому соседнему узлу собственная текущая оценка общих затрат на то, чтобы добраться до всех известных ему мест назначения. Соседние узлы исследуют эту информацию и сравнивают ее с тем, что им уже известно; все, что представляет собой улучшение того, что у них уже есть, они вставляют в свою таблицу. Со временем все узлы в сети обнаруживают лучший следующий переход и общую стоимость для всех пунктов назначения.
Когда сетевой узел выходит из строя, все узлы, которые использовали его в качестве следующего перехода, сбрасывают запись и передают обновленную информацию о маршрутизации всем соседним узлам, которые, в свою очередь, повторяют процесс. В конце концов, все узлы в сети получают обновления и обнаруживают новые пути ко всем пунктам назначения, которые не связаны с нижним узлом.
При применении алгоритмов состояния канала графическая карта сети является фундаментальными данными, используемыми для каждого узла. Чтобы создать свою карту, каждый узел заполняет всю сеть информацией о других узлах, к которым он может подключиться. Затем каждый узел независимо собирает эту информацию в карту. Используя эту карту, каждый маршрутизатор независимо определяет путь с наименьшей стоимостью от самого себя до каждого другого узла, используя стандартный алгоритм кратчайших путей, такой как алгоритм Дейкстры. Результатом является древовидный граф с корнем в текущем узле, так что путь через дерево от корня к любому другому узлу представляет собой путь с наименьшей стоимостью к этому узлу. Затем это дерево служит для построения таблицы маршрутизации, которая определяет наилучший следующий переход от текущего узла к любому другому узлу.
Алгоритм маршрутизации состояния канала, оптимизированный для мобильных одноранговых сетей, является оптимизированным протоколом маршрутизации состояния канала (OLSR). OLSR является проактивным; он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала через мобильную специальную сеть. Используя сообщения Hello, каждый узел обнаруживает информацию о двухсегментном соседе и выбирает набор многоточечных ретрансляторов (MPR). Протоколы MPR отличают OLSR от других протоколов маршрутизации на основе состояния канала.
Вектор расстояния и маршрутизация по состоянию канала являются протоколами внутридоменной маршрутизации. Они используются внутри автономной системы, но не между автономными системами. Оба этих протокола маршрутизации становятся неразрешимыми в больших сетях и не могут использоваться в междоменной маршрутизации. Маршрутизация на основе вектора расстояния может быть нестабильной, если в домене больше нескольких переходов. Маршрутизация состояния канала требует значительных ресурсов для расчета таблиц маршрутизации. Это также создает интенсивный трафик из-за наводнения.
Маршрутизация вектора пути используется для междоменной маршрутизации. Это похоже на маршрутизацию вектора расстояния. Маршрутизация по векторному пути предполагает, что один узел (их может быть много) в каждой автономной системе действует от имени всей автономной системы. Этот узел называется узлом динамика. Узел динамика создает таблицу маршрутизации и объявляет ее соседним узлам динамика в соседних автономных системах. Идея аналогична векторной маршрутизации расстояния, за исключением того, что только узлы динамиков в каждой автономной системе могут связываться друг с другом. Узел динамика объявляет путь, а не метрику узлов в своей автономной системе или других автономных системах.
Алгоритм маршрутизации вектора пути аналогичен алгоритму вектора расстояния в том смысле, что каждый пограничный маршрутизатор объявляет пункты назначения, которых он может достичь, своему соседнему маршрутизатору. Однако вместо того, чтобы рекламировать сети с точки зрения пункта назначения и расстояния до пункта назначения, сети объявляются в виде адресов пункта назначения и описаний пути для достижения этих пунктов назначения. Путь, выраженный в терминах пройденных на данный момент доменов (или конфедераций), переносится в специальном атрибуте пути, который записывает последовательность доменов маршрутизации, через которые прошла информация о доступности. Маршрут определяется как пара между пунктом назначения и атрибутами пути к этому пункту назначения, таким образом, имя, маршрутизация путь-вектор; Маршрутизаторы получают вектор, содержащий пути к набору пунктов назначения.
Выбор пути включает применение метрики маршрутизации к нескольким маршрутам для выбора (или прогнозирования) лучший маршрут. Большинство алгоритмов маршрутизации одновременно используют только один сетевой путь. Многопутевая маршрутизация и, в частности, методики многопутевой маршрутизации с одинаковой стоимостью позволяют использовать несколько альтернативных путей.
В компьютерных сетях показатель вычисляется алгоритмом маршрутизации и может охватывать такую информацию, как полоса пропускания, сетевая задержка, количество переходов, стоимость пути, нагрузка, максимальная единица передачи, надежность и стоимость связи. Таблица маршрутизации хранит только наилучшие возможные маршруты, тогда как состояние канала или топологические базы данных могут также хранить всю остальную информацию.
В случае перекрытия или равных маршрутов алгоритмы рассматривают следующие элементы в порядке приоритета, чтобы решить, какие маршруты устанавливать в таблицу маршрутизации:
Поскольку метрика маршрутизации специфична для данного протокола маршрутизации, многопротокольные маршрутизаторы должны использовать некоторую внешнюю эвристику для выбора между маршрутами, полученными из разных протоколов маршрутизации. Маршрутизаторы Cisco, например, присваивают значение, известное как административное расстояние, каждому маршруту, где меньшие административные расстояния указывают маршруты, полученные из протокола, который считается более надежным.
Локальный администратор может настроить маршруты для конкретных хостов, которые обеспечивают больший контроль над использованием сети, позволяют проводить тестирование и улучшают общую безопасность. Это полезно для отладки сетевых подключений или таблиц маршрутизации.
В некоторых небольших системах одно центральное устройство заранее определяет полный путь каждого пакета. В некоторых других небольших системах любое пограничное устройство, вводящее пакет в сеть, заранее определяет полный путь этого конкретного пакета. В обеих этих системах этому устройству планирования маршрута необходимо знать много информации о том, какие устройства подключены к сети и как они связаны друг с другом. Получив эту информацию, он может использовать такой алгоритм, как алгоритм поиска A *, чтобы найти лучший путь.
В высокоскоростных системах каждую секунду передается так много пакетов, что отдельное устройство не может рассчитать полный путь для каждого пакета. Ранние высокоскоростные системы справлялись с этим, устанавливая канал переключения релейный канал один раз для первого пакета между некоторым источником и некоторым пунктом назначения; более поздние пакеты между тем же источником и тем же местом назначения продолжают следовать по тому же пути без пересчета до тех пор, пока канал teardown не будет. Более поздние высокоскоростные системы вводят пакеты в сеть, при этом ни одно устройство не вычисляет полный путь для этого пакета - несколько агентов.
В больших системах существует так много соединений между устройствами, и эти соединения меняются так часто, что ни одно устройство не может даже знать, как все устройства соединены друг с другом, не говоря уже о том, чтобы вычислить полный путь через них. Такие системы обычно используют маршрутизацию следующего перехода.
Большинство систем используют детерминированный алгоритм динамической маршрутизации : когда устройство выбирает путь к определенному конечному пункту назначения, это устройство всегда выбирает тот же путь к этому пункту назначения, пока не получит информацию, которая делает его думаю, что какой-нибудь другой путь лучше. Некоторые алгоритмы маршрутизации не используют детерминированный алгоритм для поиска «наилучшего» канала, по которому пакет может добраться от исходного источника до конечного пункта назначения. Вместо этого, чтобы избежать перегрузки в коммутируемых системах или горячих точках сети в пакетных системах, некоторые алгоритмы используют рандомизированный алгоритм - парадигму Valiant - который направляет путь к случайно выбранному промежуточному пункту назначения, а оттуда - к его истинному конечному пункту назначения. Во многих ранних телефонных коммутаторах рандомизатор часто использовался для выбора начала пути через многоступенчатую коммутационную матрицу.
. В зависимости от приложения, для которого выполняется выбор пути, могут использоваться разные показатели. используемый. Например, для веб-запросов можно использовать пути с минимальной задержкой, чтобы минимизировать время загрузки веб-страницы, или для массовой передачи данных можно выбрать наименее используемый путь для балансировки нагрузки в сети и увеличения пропускной способности. Популярной целью выбора пути является сокращение среднего времени завершения потоков трафика и общего потребления полосы пропускания сети, что в основном приводит к лучшему использованию пропускной способности сети. Недавно была предложена метрика выбора пути, которая вычисляет общее количество байтов, запланированных на ребрах на путь, как метрику выбора. Доступен эмпирический анализ нескольких показателей выбора пути, включая это новое предложение.
В некоторых сетях маршрутизация осложняется тем фактом, что ни один объект не отвечает за выбор путей; вместо этого несколько объектов участвуют в выборе путей или даже частей одного пути. Осложнения или неэффективность могут возникнуть, если эти организации выберут способы оптимизации своих собственных целей, которые могут вступать в противоречие с целями других участников.
Классический пример связан с движением в дорожной системе, в которой каждый водитель выбирает путь, минимизирующий время в пути. При такой маршрутизации маршруты равновесия могут быть длиннее оптимальных для всех водителей. В частности, парадокс Браесса показывает, что добавление новой дороги может увеличить время в пути для всех водителей.
В другой модели, например, используемой для маршрутизации автоматических управляемых транспортных средств (AGV) на терминале, резервирование выполняется для каждого транспортного средства, чтобы предотвратить одновременное использование одной и той же части инфраструктуры. Этот подход также называется контекстно-зависимой маршрутизацией.
Интернет разделен на автономные системы (AS), такие как интернет-провайдеры (ISP), каждый из которых контролирует маршруты, связанные с его сетью, на нескольких уровнях. Во-первых, пути на уровне AS выбираются с помощью протокола BGP, который создает последовательность AS, через которые проходят пакеты. Каждая AS может иметь несколько путей, предлагаемых соседними AS, из которых можно выбирать. Его решение часто связано с деловыми отношениями с этими соседними AS, которые могут не иметь отношения к качеству пути или задержке. Во-вторых, после выбора пути уровня AS часто имеется несколько соответствующих путей на уровне маршрутизатора, отчасти потому, что два ISP могут быть подключены в нескольких местах. При выборе единого пути на уровне маршрутизатора каждый интернет-провайдер обычно использует горячую маршрутизацию : отправка трафика по пути, который минимизирует расстояние через собственную сеть интернет-провайдера, даже если этот путь удлиняет общее расстояние до пункта назначения.
Рассмотрим двух интернет-провайдеров, A и B. Каждый из них присутствует в Нью-Йорке, соединен быстрым каналом с задержкой 5 мс - и каждый присутствует в Лондон соединен линией 5 мс. Предположим, что у обоих интернет-провайдеров есть трансатлантические каналы, которые соединяют их две сети, но канал A имеет задержку 100 мс, а канал B - 120 мс. При маршрутизации сообщения от источника в лондонской сети A к пункту назначения в нью-йоркской сети B, A может выбрать немедленную отправку сообщения B в Лондоне. Это избавляет A от работы по отправке его по дорогостоящему трансатлантическому каналу, но вызывает задержку сообщения 125 мс, тогда как другой маршрут был бы на 20 мс быстрее.
Исследование интернет-маршрутов в 2003 году показало, что между парами соседних интернет-провайдеров более 30% путей имеют завышенную задержку из-за маршрутизации по принципу «горячей картошки», при этом 5% путей задерживаются как минимум на 12 мс.. Инфляция из-за выбора пути на уровне AS, хотя и значительная, объяснялась в первую очередь отсутствием у BGP механизма прямой оптимизации задержки, а не эгоистичной политикой маршрутизации. Было также высказано предположение, что при наличии соответствующего механизма интернет-провайдеры будут готовы сотрудничать для уменьшения задержки, а не использовать маршрутизацию по принципу горячего картофеля.
Такой механизм был позже опубликован теми же авторами, сначала для случай двух интернет-провайдеров, а затем глобальный случай.
Поскольку Интернет и IP-сети становятся критически важными бизнес-инструментами, возрос интерес к методам и методы мониторинга состояния маршрутизации сетей. Неправильная маршрутизация или проблемы с маршрутизацией вызывают нежелательное снижение производительности, переключение и / или простои. Мониторинг маршрутизации в сети достигается с помощью инструментов и методов анализа маршрутов.
В сетях, где доступно логически централизованное управление состоянием пересылки, например, с использованием Программно-определяемых сетей, методы маршрутизации могут использоваться с этой целью. для оптимизации глобальных и общесетевых показателей производительности. Это использовалось крупными интернет-компаниями, которые управляют множеством центров обработки данных в разных географических точках, подключенных с помощью частных оптических каналов, примеры которых включают Microsoft Global WAN, Facebook Express Backbone и Google B4. Глобальные показатели производительности, которые следует оптимизировать, включают максимальное использование сети, минимизацию времени завершения потока трафика и максимизацию трафика, доставленного до определенных сроков. В частности, минимизация времени выполнения потока в частной глобальной сети не получила особого внимания со стороны исследовательского сообщества. Однако с увеличением числа предприятий, которые управляют глобально распределенными центрами обработки данных, подключенными с помощью частных сетей между центрами обработки данных, вероятно, будут наблюдаться все более активные исследования в этой области. В недавней работе по сокращению времени завершения потоков через частную глобальную сеть обсуждается моделирование маршрутизации как проблема оптимизации графа путем перемещения всех очередей в конечные точки. Авторы также предлагают эвристику для эффективного решения проблемы, жертвуя при этом незначительной производительностью.
 | В Викиверситете есть обучающие ресурсы по маршрутизации |
 | На Викискладе есть материалы, связанные с маршрутизацией. |
