Маршрутизация с ограничением поворотов - Turn restriction routing

А алгоритм маршрутизации решает путь, по которому следует пакет от источника до места назначения маршрутизаторы в сеть. Важным аспектом, который следует учитывать при разработке алгоритма маршрутизации, является предотвращение тупик. Маршрутизация с ограничением поворотов[1][2] алгоритм маршрутизации для сетка -семья топологии который позволяет избежать взаимоблокировок, ограничивая типы поворотов, разрешенных в алгоритме при определении маршрута от источника узел к узлу назначения в сети.

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

Причина тупика

Тупик (показан на рис.1) - это ситуация, в которой дальнейшая транспортировка пакетов невозможна из-за насыщения сетевых ресурсов, например буферы или ссылки. Основная причина тупика[3] это циклическое приобретение каналы в сети.[4] Например, представьте, что в сети четыре канала. Четыре пакета заполнили входные буферы этих четырех каналов и должны быть перенаправлены на следующий канал. Теперь предположим, что выходные буферы всех этих каналов также заполнены пакетами, которые необходимо передать на следующий канал. Если эти четыре канала образуют цикл, дальнейшая передача пакетов невозможна, поскольку буферы вывода и входные буферы всех каналов уже заполнены. Это называется циклическим захватом каналов, и это приводит к тупиковой ситуации.

Решение тупиковой ситуации

Тупики могут быть обнаружен, сломанный или избегали от всего происходящего.[5] Обнаружение и устранение тупиков в сети обходится дорого с точки зрения задержка и ресурсы. Таким образом, простое и недорогое решение - избежать взаимоблокировок за счет выбора методов маршрутизации, предотвращающих циклический захват каналов.[6]

Рис. 2: Все возможные повороты в сети - по и против часовой стрелки.

Логика маршрутизации с ограничением поворота

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

Рис.3: Маршрутизация с упорядоченным размером (X-Y)

Примеры маршрутизации с ограничением поворота

Маршрутизация с ограничением поворотов может быть получена путем запрета по крайней мере одного из четырех возможных поворотов по часовой стрелке и по крайней мере одного из четырех возможных поворотов против часовой стрелки в алгоритме маршрутизации. Это означает, что есть не менее 16 (4x4)[5] возможные методы маршрутизации с ограничением поворотов, так как у вас есть 4 поворота по часовой стрелке и 4 поворота против часовой стрелки на выбор. Некоторые из этих методов перечислены ниже.

Рис.4: Западный первый маршрут
Рис. 5: Маршрут на север.
Рис.6: Первая отрицательная маршрутизация

Маршрутизация по размеру (X-Y)

Размерная маршрутизация (X-Y)[2][5] (показан на рис. 3) ограничивает все повороты от размера y до размера x. Это запрещает два поворота против часовой стрелки и два поворота по часовой стрелке, что больше, чем фактически требуется. Даже тогда, поскольку он ограничивает число разрешенных поворотов, мы можем сказать, что это пример маршрутизации с ограничением поворотов.

Запад первый маршрут

Запад первый маршрут[2][5] (показан на рис. 4) ограничивает все повороты в западном направлении. Это означает, что при необходимости в предлагаемом маршруте сначала следует выбрать западное направление.

Северный последний маршрут

Северный последний маршрут[2][7] (показано на рис. 5) ограничивает поворот в любом другом направлении, если текущее направление - север. Это означает, что северное направление следует выбирать последним, если это необходимо в предлагаемом маршруте.

Отрицательная первая маршрутизация

Отрицательная первая маршрутизация[2][7] (показано на рис. 6) ограничивает поворот в отрицательном направлении, в то время как текущее направление положительное. Запад считается отрицательным направлением в X-измерении, а юг считается отрицательным направлением в Y-измерении. Это означает любой хмель в одном из отрицательных направлений следует двигаться, прежде чем делать любой другой поворот.

Преимущества маршрутизации с ограничением поворота

  • Предотвращение взаимоблокировок обходится дешевле, чем методы обнаружения и устранения взаимоблокировок.
  • Ограничения поворота предусматривают альтернативный минимальная длина пути а также пути не минимальной длины от одного узла к другому, что позволяет обходить перегружен или неудачные ссылки.[8]

Например, рассмотрите рисунок 7 ниже. Предположим, имеется несколько маршрутизаторов, F1, F2 и т. Д., Которые подают пакеты на перегруженный, но недорогой канал от исходного маршрутизатора S до конечного маршрутизатора D. Реализация маршрутизации с ограничением поворотов означает, что некоторые из поворотов от любого из подающих маршрутизаторов к перегруженный маршрутизатор S теперь может быть ограничен. Этим фидерным маршрутизаторам, возможно, придется использовать более длинный путь, чтобы добраться до пункта назначения D, тем самым уменьшив нагрузку на канал от S к D.

Рис. 7. Топология четырех маршрутизаторов F1, F2, S и D, подключенных друг к другу. Ограничения поворотов могут до некоторой степени уменьшить перегрузку на линии S-D.

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

использованная литература

  1. ^ Солихин, Ян (2016). основы параллельной компьютерной архитектуры. солихин книги. С. 390–392. ISBN  9780984163007.
  2. ^ а б c d е КРИСТОФЕР Дж. Гласс и Лайонел М. Н. «Модель поворота для адаптивной маршрутизации» (PDF). Университет штата Мичиган.
  3. ^ Солихин, Ян (2016). основы параллельной компьютерной архитектуры. солихин книги. С. 388–389. ISBN  9780984163007.
  4. ^ Кулурис, Джордж (2012). Концепции и дизайн распределенных систем. Пирсон. ISBN  978-0-273-76059-7.
  5. ^ а б c d Солихин, Ян (2016). основы параллельной компьютерной архитектуры. солихин книги. п. 390. ISBN  9780984163007.
  6. ^ Хэвендер, Джеймс В. (1968). «Как избежать тупика в многозадачных системах». Журнал IBM Systems. 7 (2): 74–84. Дои:10.1147 / sj.72.0074.
  7. ^ а б Солихин, Ян (2016). Основы параллельной компьютерной архитектуры. Книги Солихина. С. 390–391. ISBN  9780984163007.
  8. ^ Солихин, Ян (2016). основы параллельной компьютерной архитектуры. солихин книги. п. 392.