Управление потоком червоточины , также называемое переключением червоточины или маршрутизацией червоточины , представляет собой систему простого управления потоком в компьютерных сетях , основанную на известных фиксированных каналах. Это подмножество методов управления потоком, называемое Flit-Buffer Flow Control. [1] : Глава 13.2.1.
Переключение является более подходящим термином, чем маршрутизация, поскольку «маршрутизация» определяет маршрут или путь, используемый для достижения пункта назначения. [2] [3] Метод «червоточины» не определяет маршрут к месту назначения, а решает, когда пакет будет отправлен от маршрутизатора.
Коммутация «червоточина» широко используется в мультикомпьютерах из-за низкой задержки и небольших требований на узлах. [3] : 376
Маршрутизация «червоточины» поддерживает высокоскоростную, гарантированную доставку пакетов с очень малой задержкой , подходящую для связи в реальном времени . [4]
При управлении потоком червоточины каждый пакет разбивается на небольшие части, называемые флитами (единицы управления потоком или цифры управления потоком).
Обычно первые флеты, называемые флитами заголовка, содержат информацию о маршруте этого пакета (например, адрес назначения) и устанавливают поведение маршрутизации для всех последующих флитов, связанных с пакетом. За сменами заголовка следует ноль или более смен тела, которые содержат фактическую полезную нагрузку данных. Некоторые заключительные этапы, называемые хвостовыми, выполняют некоторую бухгалтерию, чтобы закрыть соединение между двумя узлами.
При коммутации червоточины каждый буфер либо простаивает, либо выделяется для одного пакета. Смещение заголовка может быть перенаправлено в буфер, если этот буфер свободен. Это выделяет буфер для пакета. Флит тела или трейлера может быть перенаправлен в буфер, если этот буфер выделен для его пакета и не заполнен. Последняя операция освобождает буфер. Если flit заголовка заблокирован в сети, буфер заполняется, и после его заполнения больше не может быть отправлено flit: этот эффект называется «обратным давлением» и может распространяться обратно к источнику.
Название «червоточина» играет роль в способе отправки пакетов по ссылкам: адрес настолько короткий, что его можно транслировать до того, как придет само сообщение. Это позволяет маршрутизатору быстро настроить маршрутизацию фактического сообщения, а затем «отключиться» от остальной части разговора. Поскольку пакет передается порциями, они могут занимать несколько буферов на своем пути, создавая червеобразный образ.
Такое поведение очень похоже на сквозную коммутацию , [5] обычно называемую «виртуальной сквозной коммутацией», основное отличие состоит в том, что сквозное управление потоком распределяет буферы и полосу пропускания канала на уровне пакетов, тогда как управление потоком «червоточины» делает это на уровне пакетов. уровень полета.
В случае циклической зависимости это противодавление может привести к тупику.
Во многих отношениях червоточина очень похожа на пересылку ATM или MPLS , за исключением того, что ячейку не нужно ставить в очередь .
Особенностью управления потоком червоточин является реализация виртуальных каналов:
Виртуальный канал сохраняет состояние, необходимое для координации обработки потоков пакета по каналу. Как минимум, это состояние идентифицирует выходной канал текущего узла для следующего прыжка маршрута и состояние виртуального канала (бездействующий, ожидающий ресурсов или активный). Виртуальный канал также может включать в себя указатели на потоки пакета, которые буферизованы на текущем узле, и количество буферов, доступных на следующем узле. [1] : 237
Рассмотрим сеть 2x2 на рисунке справа, в которой необходимо отправить 3 пакета: розовый, состоящий из 4 флитов, «UVWX», от C до D; синий, состоящий из 4 крыльев abcd, от A до F; и зеленый, состоящий из 4 флитов «ijkl», от E до H. Мы предполагаем, что маршрутизация была рассчитана, как показано на рисунке, и подразумевает конфликт буфера в нижнем левом маршрутизаторе. Пропускная способность составляет один флит в единицу времени.
Во-первых, рассмотрим розовый поток: в момент времени 1 сигнал «U» отправляется в первый буфер; в момент времени 2 сообщение «U» проходит через следующий буфер (при условии, что вычисление маршрута не занимает много времени), а сообщение «V» отправляется в первый буфер и так далее.
Синий и зеленый потоки требуют пошагового представления:
Методы червоточин в основном используются в многопроцессорных системах, особенно в гиперкубах . В компьютере-гиперкубе каждый процессор подключен к нескольким соседям по фиксированной схеме, что уменьшает количество переходов от одного процессора к другому. Каждому ЦП присваивается номер (обычно от 8 до 16 бит ), который является его сетевым адресом, и пакеты ЦП отправляются с этим номером в заголовке. Когда пакет поступает на промежуточный маршрутизатор для пересылки, маршрутизатор проверяет заголовок (очень быстро), устанавливает соединение со следующим маршрутизатором, а затем прекращает диалог. Это заметно снижает задержку (задержку) по сравнению с коммутацией с промежуточным хранением , при которой перед пересылкой ожидает весь пакет. Совсем недавно управление потоком червоточин нашло свое применение в системах Network On Chip (NOC), одной из разновидностей которых являются многоядерные процессоры. Здесь множество процессорных ядер или, на более низком уровне, даже функциональные блоки могут быть объединены в сеть на одном корпусе микросхемы . Поскольку задержки в проводах и многие другие немасштабируемые ограничения на связанные элементы обработки становятся доминирующим фактором при проектировании, инженеры стремятся упростить организованные сети межсоединений, в которых методы управления потоками играют важную роль.
Технологии IEEE 1355 и SpaceWire используют червоточину.
Расширением управления потоком через червоточину является управление потоком виртуальных каналов , при котором несколько виртуальных каналов могут быть мультиплексированы в один физический канал. Каждый однонаправленный виртуальный канал реализуется независимо управляемой парой (flit) буферов. Затем различные пакеты могут совместно использовать физический канал на индивидуальной основе. Виртуальные каналы изначально были введены, чтобы избежать проблемы тупиковой ситуации, но их также можно использовать для уменьшения блокировки червоточин, улучшения задержки и пропускной способности сети. Блокировка «червоточины» происходит, когда пакет захватывает канал, что предотвращает использование канала другими пакетами и приводит к их остановке. Предположим, пакет P0 захватил канал между двумя маршрутизаторами. При отсутствии виртуальных каналов пакет P1, пришедший позже, будет заблокирован до тех пор, пока не будет завершена передача P0. В случае реализации виртуальных каналов возможны следующие улучшения:
Использование виртуальных каналов для уменьшения блокировки червоточин во многом похоже на использование виртуальных очередей вывода для уменьшения блокировки начала строки .
В одном и том же пакете, коммутируемом через червоточину, может использоваться сочетание маршрутизации от источника и логической маршрутизации. Значение первого байта пакета Myrinet или SpaceWire является адресом пакета. Каждый коммутатор SpaceWire использует адрес, чтобы решить, как маршрутизировать пакет. [7]
При маршрутизации от источника отправитель пакета выбирает способ маршрутизации пакета через коммутатор.
Если первый байт входящего пакета SpaceWire находится в диапазоне от 1 до 31, это указывает на соответствующий порт от 1 до 31 коммутатора Spacewire. Затем коммутатор SpaceWire отбрасывает этот символ маршрутизации и отправляет остальную часть пакета через этот порт. Это предоставляет следующий байт исходного пакета следующему коммутатору SpaceWire. Отправитель пакета может выбрать использование исходной маршрутизации , чтобы таким образом явно указать полный путь через сеть к конечному пункту назначения. [7]
При логической маршрутизации коммутатор Spacewire сам решает, как маршрутизировать пакет.
Если адрес (первый байт) входящего пакета SpaceWire находится в диапазоне от 32 до 255, коммутатор SpaceWire использует это значение в качестве индекса во внутренней таблице маршрутизации, которая указывает, на какой порт(ы) отправить пакет и следует ли его удалять. или сохраните этот первый байт. [7]
Адрес 0 используется для прямой связи с коммутатором и может использоваться для установки записей таблицы маршрутизации для этого коммутатора. [7]