Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Причина тупика [ править ]

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

Решение тупиковой ситуации [ править ]

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

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

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

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

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

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

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

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

Маршрутизация с упорядоченным размером (XY) [ править ]

Маршрутизация с упорядоченным размером (XY) [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, подключенных друг к другу. Ограничения поворотов могут до некоторой степени уменьшить перегрузку на линии SD.

См. Также [ править ]

  • Маршрутизация на основе политик
  • Тупик
  • Эвристические алгоритмы

Ссылки [ править ]

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