Маршрутизация ограничения поворота
Алгоритм маршрутизации определяет путь, по которому следует пакет от источника к маршрутизаторам назначения в сети . Важным аспектом, который следует учитывать при разработке алгоритма маршрутизации, является предотвращение тупиковых ситуаций . Маршрутизация ограничения поворота [1] — это алгоритм маршрутизации для ячеек семейства топологий , который позволяет избежать взаимоблокировок за счет ограничения типов поворотов, разрешенных в алгоритме, при определении маршрута от исходного узла к узлу назначения в сети.
Причина тупика
[ редактировать ]Тупик (показанный на рис. 1) — это ситуация, в которой дальнейшая транспортировка пакетов невозможна из-за насыщения сетевых ресурсов, таких как буферы или каналы связи . Основная причина тупика – циклическое приобретение каналов в сети. [2] Например, предположим, что в сети четыре канала. Четыре пакета заполнили входные буферы этих четырех каналов, и их необходимо переслать на следующий канал. Теперь предположим, что выходные буферы всех этих каналов также заполнены пакетами, которые необходимо передать в следующий канал. Если эти четыре канала образуют цикл, то передавать пакеты дальше невозможно, поскольку выходные и входные буферы всех каналов уже заполнены. Это называется циклическим захватом каналов и приводит к тупику.
Решение тупиковой ситуации
[ редактировать ]Взаимные блокировки можно либо обнаружить , сломать, либо избежать вообще . Обнаружение и устранение взаимоблокировок в сети требует больших затрат с точки зрения задержки и ресурсов. Таким образом, простое и недорогое решение — избежать взаимоблокировок, выбрав методы маршрутизации, предотвращающие циклическое получение каналов. [3]
Логика маршрутизации ограничения поворота
[ редактировать ]Логика маршрутизации с ограничением поворота вытекает из ключевого наблюдения. Циклический захват каналов может происходить только в том случае, если произошли все четыре возможных поворота по часовой стрелке (или против часовой стрелки). Это означает, что тупиков можно избежать, запретив хотя бы один поворот по часовой стрелке и один поворот против часовой стрелки. Все повороты по часовой стрелке и против часовой стрелки, которые возможны в алгоритме неограниченной маршрутизации, показаны на рис. 2.
Примеры маршрутизации с ограничением поворота
[ редактировать ]Маршрут с ограничением поворота можно получить, запретив в алгоритме маршрутизации по меньшей мере один из четырех возможных поворотов по часовой стрелке и хотя бы один из четырех возможных поворотов против часовой стрелки. Это означает, что существует как минимум 16 (4x4) возможных методов маршрутизации с ограничением поворота, поскольку у вас есть на выбор 4 поворота по часовой стрелке и 4 поворота против часовой стрелки. Некоторые из этих методов перечислены ниже.
Маршрутизация в размерном порядке (XY)
[ редактировать ]Маршрутизация по размеру (XY) [1] (показано на рис. 3) ограничивает все повороты из измерения y в измерение x. Это запрещает два поворота против часовой стрелки и два поворота по часовой стрелке, что превышает фактически требуемую величину. Даже в этом случае, поскольку он ограничивает количество разрешенных поворотов, мы можем сказать, что это пример маршрутизации с ограничением поворотов.
Первый западный маршрут
[ редактировать ]Первый западный маршрут [1] (показано на рис. 4) ограничивает все повороты в западном направлении. Это означает, что в случае необходимости на предлагаемом маршруте в первую очередь следует выбрать западное направление.
Северный последний маршрут
[ редактировать ]Северный последний маршрут [1] (показано на рис. 5) ограничивает поворот в любом другом направлении, если текущее направление — север. Это означает, что северное направление на предлагаемом маршруте при необходимости следует выбирать последним.
Отрицательная первая маршрутизация
[ редактировать ]Отрицательная первая маршрутизация [1] (показано на рис. 6) ограничивает поворот в отрицательном направлении, пока текущее направление положительное. Запад считается отрицательным направлением в измерении X, а юг — отрицательным направлением в измерении Y. Это означает, что любой прыжок в одном из отрицательных направлений следует совершить перед любым другим поворотом.
Преимущества маршрутизации с ограничением поворота
[ редактировать ]- Предотвращение взаимоблокировок обходится дешевле, чем методы обнаружения и устранения взаимоблокировок.
- Ограничения поворота обеспечивают альтернативные пути минимальной длины , а также пути не минимальной длины от одного узла к другому, что позволяет маршрутизировать маршрут вокруг перегруженных или вышедших из строя каналов.
Например, рассмотрим рисунок 7 ниже. Предположим, имеется несколько маршрутизаторов F1, F2 и т. д., которые передают пакеты по перегруженному, но недорогому каналу от исходного маршрутизатора S к целевому маршрутизатору D. Реализация маршрутизации с ограничением поворотов означает, что некоторые повороты от любого из питающих маршрутизаторов к перегруженный маршрутизатор S теперь может быть ограничен. Этим фидерным маршрутизаторам, возможно, придется использовать более длинный путь, чтобы добраться до пункта назначения D, тем самым в некоторой степени разгружая канал от S до D.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д и КРИСТОФЕР Дж. ГЛАСС И ЛАЙОНЕЛ М. НИ. «Модель поворота для адаптивной маршрутизации» (PDF) . Мичиганский государственный университет . Архивировано из оригинала (PDF) 3 декабря 2016 г. Проверено 2 декабря 2016 г.
- ^ Кулурис, Джордж (2012). Концепции и проектирование распределенных систем . Пирсон. ISBN 978-0-273-76059-7 .
- ^ Хавендер, Джеймс В. (1968). «Как избежать тупиковых ситуаций в многозадачных системах» . IBM Systems Journal . 7 (2): 74–84. дои : 10.1147/sj.72.0074 . Архивировано из оригинала 24 февраля 2012 г. Проверено 28 ноября 2016 г.