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

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

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

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

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

Схемы доставки

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

• Unicast доставляет сообщение на один конкретный узел, используя один к одному связь между отправителем и получателем: каждый адрес назначения однозначно идентифицирует единственную конечную точку получателя.
• Транслировать доставляет сообщение всем узлам сети, используя один ко всем ассоциация; одна дейтаграмма от одного отправителя направляется ко всем, возможно, нескольким конечным точкам, связанным с широковещательным адресом. Сеть автоматически реплицирует дейтаграммы по мере необходимости, чтобы достичь всех получателей в рамках широковещательной рассылки, которая обычно представляет собой всю сетевую подсеть.
• Многоадресная рассылка доставляет сообщение группе узлов, которые выразили заинтересованность в получении сообщения, используя один-ко-многим-из-многих или же многие-ко-многим-многим ассоциация; дейтаграммы направляются одновременно за одну передачу многим получателям. Многоадресная рассылка отличается от широковещательной передачи тем, что адрес назначения обозначает подмножество, а не обязательно все доступные узлы.
• Anycast доставляет сообщение любому из группы узлов, обычно ближайшему к источнику, используя один к одному из многих ассоциация, при которой дейтаграммы направляются любому отдельному члену группы потенциальных получателей, которые все идентифицированы одним и тем же адресом назначения. Алгоритм маршрутизации выбирает единственный приемник из группы, исходя из того, какой из них является ближайшим по некоторой мере расстояния.
• Геокаст доставляет сообщение группе узлов в сети на основе их географическое положение. Это специализированная форма многоадресной адресации, используемая некоторыми протоколами маршрутизации для мобильных одноранговых сетей.

Одноадресная рассылка - это основная форма доставки сообщений в Интернете. Эта статья посвящена алгоритмам одноадресной маршрутизации.

Распределение топологии

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

Динамическая маршрутизация пытается решить эту проблему путем автоматического построения таблиц маршрутизации на основе информации, переносимой протоколы маршрутизации, позволяя сети действовать практически автономно, избегая сбоев и блокировок сети. В Интернете доминирует динамическая маршрутизация. Примеры протоколов и алгоритмов динамической маршрутизации включают: Протокол маршрутной информации (РВАТЬ), Сначала откройте кратчайший путь (OSPF) и Расширенный протокол маршрутизации внутреннего шлюза (EIGRP).

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

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

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

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

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

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

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

Алгоритм маршрутизации по состоянию канала, оптимизированный для мобильные специальные сети это оптимизированный протокол маршрутизации состояния канала (OLSR).^[1] OLSR является проактивным; он использует сообщения Hello и Topology Control (TC) для обнаружения и распространения информации о состоянии канала через мобильную специальную сеть. Используя приветственные сообщения, каждый узел обнаруживает информацию о двухсегментном соседе и выбирает набор многоточечные реле (MPR). Протоколы MPR отличают OLSR от других протоколов маршрутизации на основе состояния канала.

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

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

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

Алгоритм маршрутизации вектора пути аналогичен алгоритму вектора расстояния в том смысле, что каждый граничный маршрутизатор объявляет пункты назначения, которых он может достичь, своему соседнему маршрутизатору. Однако вместо того, чтобы рекламировать сети с точки зрения пункта назначения и расстояния до пункта назначения, сети объявляются в виде адресов пункта назначения и описаний пути для достижения этих пунктов назначения. Путь, выраженный в терминах пройденных на данный момент доменов (или конфедераций), переносится в специальном атрибуте пути, который записывает последовательность доменов маршрутизации, через которые прошла информация о доступности. Маршрут определяется как пара между пунктом назначения и атрибутами пути к этому пункту назначения, таким образом, имя, маршрутизация путь-вектор; Маршрутизаторы получают вектор, содержащий пути к набору пунктов назначения.^[2]

Выбор пути

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

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

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

1. Длина префикса: Соответствующая запись в таблице маршрутов с более длинной маской подсети всегда предпочтительна, поскольку она более точно определяет пункт назначения.
2. Метрическая: При сравнении маршрутов, полученных через один и тот же протокол маршрутизации, предпочтительнее использовать более низкий показатель. Невозможно сравнивать метрики между маршрутами, полученными из разных протоколов маршрутизации.
3. Административная дистанция: При сравнении записей таблицы маршрутов из разных источников, таких как разные протоколы маршрутизации и статическая конфигурация, меньшее административное расстояние указывает на более надежный источник и, следовательно, на предпочтительный маршрут.

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

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

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

В высокоскоростных системах каждую секунду передается так много пакетов, что отдельное устройство не может рассчитать полный путь для каждого пакета. Ранние высокоскоростные системы справлялись с этим путем создания коммутация цепи релейный канал один раз для первого пакета между некоторым источником и некоторым пунктом назначения; более поздние пакеты между тем же источником и тем же местом назначения продолжают следовать по тому же пути без пересчета, пока канал срывать. Более поздние высокоскоростные системы вводят пакеты в сеть, при этом ни одно устройство не вычисляет полный путь для этого пакета - несколько агентов.

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

Большинство систем используют детерминированный динамическая маршрутизация алгоритм: когда устройство выбирает путь к определенному конечному пункту назначения, это устройство всегда выбирает тот же путь к этому пункту назначения, пока не получит информацию, которая заставляет его думать, что какой-то другой путь лучше. Некоторые алгоритмы маршрутизации не используют детерминированный алгоритм для поиска «лучший» канал, по которому пакет может добраться от исходного источника до конечного пункта назначения. Вместо этого, чтобы избежать перегрузки в коммутируемых системах или горячих точках сети в пакетных системах, некоторые алгоритмы используют рандомизированный алгоритм - парадигма Valiant - который направляет путь в случайно выбранный промежуточный пункт назначения, а оттуда в его истинный конечный пункт назначения.^[4][5]Во многих ранних телефонных коммутаторах рандомизатор часто использовался для выбора начала пути через многоступенчатая коммутационная матрица.

В зависимости от приложения, для которого выполняется выбор пути, могут использоваться разные показатели. Например, для веб-запросов можно использовать пути с минимальной задержкой, чтобы минимизировать время загрузки веб-страницы, или для массовой передачи данных можно выбрать наименее используемый путь для балансировки нагрузки в сети и увеличения пропускной способности. Популярной целью выбора пути является сокращение среднего времени завершения потоков трафика и общего потребления полосы пропускания сети, что в основном приводит к лучшему использованию пропускной способности сети. Недавно была предложена метрика выбора пути, которая вычисляет общее количество байтов, запланированных на ребрах на путь, как метрику выбора.^[6] Доступен эмпирический анализ нескольких показателей выбора пути, включая это новое предложение.^[7]

Несколько агентов

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

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

В другой модели, например, используется для маршрутизации автоматизированные управляемые машины (AGV) на терминале, резервирование производится для каждого транспортного средства, чтобы предотвратить одновременное использование одной и той же части инфраструктуры. Этот подход также называется контекстно-зависимой маршрутизацией.^[8]

Интернет разделен на автономные системы (AS), такие как интернет-провайдеры (ISP), каждый из которых контролирует маршруты, связанные с его сетью, на нескольких уровнях. Сначала пути уровня AS выбираются через BGP протокол, который создает последовательность AS, через которые проходят пакеты. Каждая AS может иметь несколько путей, предлагаемых соседними AS, из которых можно выбирать. Его решение часто связано с деловыми отношениями с этими соседними AS,^[9] что может быть не связано с качеством пути или задержкой. Во-вторых, после выбора пути уровня AS часто имеется несколько соответствующих путей на уровне маршрутизатора, отчасти потому, что два ISP могут быть подключены в нескольких местах. При выборе единственного пути на уровне маршрутизатора каждый интернет-провайдер обычно использует горячий картофель: отправка трафика по пути, который минимизирует расстояние через собственную сеть провайдера, даже если этот путь увеличивает общее расстояние до пункта назначения.

Рассмотрим двух интернет-провайдеров, А и B. Каждый присутствует в Нью-Йорк, соединенный быстрым каналом с задержкой 5 РС - и каждый присутствует в Лондон подключен по ссылке 5 мс. Предположим, у обоих интернет-провайдеров есть трансатлантические каналы, соединяющие их две сети, но А 's канал имеет задержку 100 мс, а канал B имеет задержку 120 мс. При маршрутизации сообщения от источника в А из Лондона в пункт назначения в B сеть в Нью-Йорке, А может выбрать немедленную отправку сообщения на B В Лондоне. Это спасает А работа по отправке его по дорогостоящему трансатлантическому каналу, но вызывает задержку сообщения 125 мс, тогда как другой маршрут был бы на 20 мс быстрее.

Исследование интернет-маршрутов в 2003 году показало, что между парами соседних интернет-провайдеров более 30% путей имеют завышенную задержку из-за маршрутизации по принципу «горячей картошки», при этом 5% путей имеют задержку не менее 12 мс. Инфляция из-за выбора пути на уровне AS, хотя и значительная, была связана в первую очередь с отсутствием у BGP механизма прямой оптимизации задержки, а не с эгоистичной политикой маршрутизации. Также было высказано предположение, что при наличии соответствующего механизма интернет-провайдеры будут готовы сотрудничать для уменьшения задержки, а не использовать маршрутизацию по принципу «горячей картошки».^[10]

Такой механизм был позже опубликован теми же авторами, сначала для случая двух интернет-провайдеров.^[11] а затем для глобального случая.^[12]

Аналитика маршрута

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

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

В сетях, где доступен логически централизованный контроль над состоянием пересылки, например, с помощью Программно-определяемые сети, могут использоваться методы маршрутизации, направленные на оптимизацию глобальных и общесетевых показателей производительности. Это использовалось крупными интернет-компаниями, которые управляют множеством центров обработки данных в разных географических точках, подключенных с помощью частных оптических каналов, примеры которых включают глобальную глобальную сеть WAN от Microsoft,^[13] Экспресс-магистраль Facebook,^[14] и Google B4.^[15] Глобальные показатели производительности, которые необходимо оптимизировать, включают максимальное использование сети, минимизацию времени завершения потока трафика и максимизацию трафика, доставленного до определенных сроков. В частности, минимизация времени выполнения потока в частной глобальной сети не получила особого внимания со стороны исследовательского сообщества. Тем не менее, с увеличением числа предприятий, которые управляют глобально распределенными центрами обработки данных, подключенными с помощью частных сетей между центрами обработки данных, вероятно, будет наблюдаться увеличение исследовательских усилий в этой области.^[16] В недавней работе по сокращению времени завершения потоков через частную глобальную сеть обсуждается моделирование маршрутизации как проблема оптимизации графа путем перемещения всех очередей в конечные точки. Авторы также предлагают эвристику для эффективного решения проблемы, при этом жертвуя незначительной производительностью.^[17]

Смотрите также

Рекомендации

дальнейшее чтение

внешняя ссылка

• Счет до бесконечности
• «Особенности стабильности» являются способами избежать проблемы «счет до бесконечности».
• Примеры использования Cisco IT о маршрутизации и коммутации
• «IP-маршрутизация и подсети». www.eventhelix.com. Получено 2018-04-28.