Управление потоком червоточин , также называемое переключением червоточин или маршрутизацией червоточин , представляет собой систему простого управления потоком в компьютерных сетях, основанную на известных фиксированных каналах. Это подмножество методов управления потоком, называемое 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' отправляется в первый буфер и так далее.
Синий и зеленый потоки требуют пошагового представления:
- Время 1: и синий, и зеленый потоки отправляют свои первые пробеги «i» и «a».
- Время 2: флит «i» может перейти в следующий буфер. Но буфер выделен для пакета от его первого до последнего флит, и поэтому флит 'a' не может быть переадресован. Это начало эффекта противодавления . Прыжок с буквой «j» может заменить слет с буквой «i». Флит 'b' можно отправить.
- Время 3: зеленый пакет продолжается. Синий флит "c" не может быть переадресован (буфер занят флитами "b" и "a"): этот эффект обратного давления достигает источника пакета.
- Время 4: Как и во время 3
- Время 5: зеленый пакет больше не использует левый нижний буфер. Синий пакет разблокирован и может быть переадресован (при условии, что «разблокированная» информация может быть переадресована за нулевое время)
- Время 6-10: синий пакет проходит по сети.
Преимущества
- Управление потоком через червоточину позволяет более эффективно использовать буферы, чем сквозные. Там, где для сквозного прохождения требуется много пакетов размером в буферное пространство, метод червоточины требует очень мало флит-буферов (сравнительно).
- Не требуется буферизация всего пакета для перехода к следующему узлу, что снижает задержку в сети по сравнению с коммутацией с промежуточным хранением .
- Полоса пропускания и распределение каналов не связаны
Применение
Методы червоточин в основном используются в многопроцессорных системах, особенно в гиперкубах . В компьютере с гиперкубом каждый ЦП прикреплен к нескольким соседям по фиксированной схеме, что уменьшает количество переходов от одного ЦП к другому. Каждому ЦП дается номер (обычно от 8 до 16 бит ), который является его сетевым адресом, и пакеты ЦП отправляются с этим номером в заголовке. Когда пакет прибывает на промежуточный маршрутизатор для пересылки, маршрутизатор проверяет заголовок (очень быстро), устанавливает канал к следующему маршрутизатору и затем отключается от разговора. Это заметно снижает задержку (задержку) по сравнению с коммутацией с промежуточным хранением, которая ожидает весь пакет перед пересылкой. Совсем недавно управление потоком через червоточину нашло свое применение в системах Network On Chip (NOC), одной из разновидностей которых являются многоядерные процессоры. Здесь многие процессорные ядра или на более низком уровне даже функциональные блоки могут быть соединены в сеть на одном корпусе IC . Поскольку задержки в проводах и многие другие немасштабируемые ограничения на связанные элементы обработки становятся доминирующим фактором при проектировании, инженеры стремятся упростить организованные сети межсоединений, в которых методы управления потоком играют важную роль.
Виртуальные каналы
Расширение управления потоком червячно-отверстие виртуального канала- управления потоком , где несколько виртуальных каналов могут быть мультиплексированы по одному физическому каналу. Каждый однонаправленный виртуальный канал реализуется независимо управляемой парой (flit) буферов. Затем разные пакеты могут совместно использовать физический канал на поэтапной основе. Виртуальные каналы изначально были введены, чтобы избежать проблемы взаимоблокировок, но они также могут использоваться для уменьшения блокировки червоточины, улучшения задержки и пропускной способности сети. Блокировка червоточины происходит, когда пакет захватывает канал, тем самым предотвращая использование канала другими пакетами и вынуждая их останавливаться. Предположим, пакет P0 получил канал между двумя маршрутизаторами. При отсутствии виртуальных каналов пакет P1, поступающий позже, будет заблокирован до тех пор, пока передача P0 не будет завершена. Если реализованы виртуальные каналы, возможны следующие улучшения:
- По прибытии P1 физический канал может быть мультиплексирован между ними по отдельности, так что оба пакета проходят с половинной скоростью (в зависимости от схемы арбитража).
- Если P0 - это полноразмерный пакет, тогда как P1 - это только небольшой контрольный пакет размером в несколько флот, тогда эта схема позволяет P1 проходить через оба маршрутизатора, в то время как P0 замедляется на короткое время, что соответствует передаче нескольких пакетов. Это уменьшает задержку для P1.
- Предположим, что P0 временно заблокирован в нисходящем направлении от текущего маршрутизатора. Пропускная способность увеличивается, позволяя P1 работать на полной скорости физического канала. Без виртуальных каналов P0 занимал бы канал, фактически не используя доступную полосу пропускания (поскольку она блокируется). [6]
Использование виртуальных каналов для уменьшения блокировки червоточины имеет много общего с использованием виртуальной очереди вывода для уменьшения блокировки заголовка .
Маршрутизация
В одном пакете с коммутацией «червоточина» может использоваться сочетание маршрутизации от источника и логической маршрутизации. Значение первого байта пакета Myrinet или SpaceWire - это адрес пакета. Каждый коммутатор SpaceWire использует адрес, чтобы решить, как маршрутизировать пакет. [7]
Маршрутизация источника
При маршрутизации от источника отправитель пакета выбирает способ маршрутизации пакета через коммутатор.
Если первый байт входящего пакета SpaceWire находится в диапазоне от 1 до 31, он указывает соответствующий порт с 1 по 31 коммутатора Spacewire. Затем коммутатор SpaceWire отбрасывает этот символ маршрутизации и отправляет остальную часть пакета через этот порт. Это открывает следующий байт исходного пакета следующему коммутатору SpaceWire. Отправитель пакета может выбрать использование исходной маршрутизации, чтобы таким образом явно указать полный путь через сеть до конечного пункта назначения. [7]
Логическая маршрутизация
При логической маршрутизации коммутатор Spacewire сам решает, как маршрутизировать пакет.
Если адрес (первый байт) входящего пакета SpaceWire находится в диапазоне от 32 до 255, коммутатор SpaceWire использует это значение в качестве индекса во внутренней таблице маршрутизации, которая указывает, какой порт (а) отправить пакет и следует ли удалить или сохранить этот первый байт. [7]
Адрес 0 используется для прямой связи с коммутатором и может использоваться для установки записей таблицы маршрутизации для этого коммутатора. [7]
Смотрите также
Рекомендации
- ^ а б Уильям Джеймс Далли; Брайан Таулз (2004). «13.2.1». Принципы и практика межсетевых соединений . ISBN издательства Morgan Kaufmann Publishers, Inc. 978-0-12-200751-4.
- ^ Джон Л. Хеннесси и Дэвид А. Паттерсон (2006). «Приложение Е.5». Компьютерная архитектура: количественный подход (четвертое изд.). ISBN издательства Morgan Kaufmann Publishers, Inc. 978-0-12-370490-0.
- ^ а б Mohapatra, Prasant (1998), "Методы Wormhole маршрутизации напрямую подключённым многомашинных систем" (PDF) , ACM Computing Surveys , 30 (3): 374-410, CiteSeerX 10.1.1.11.9098 , DOI : 10,1145 / 292469,292472
- ^ Шарад Сундаресан; Риккардо Беттати. «Распределенное управление подключениями для связи в реальном времени по сетям с маршрутизацией через червоточины» . 1997 г.
- ^ Стефан Хаас. «Стандарт IEEE 1355: разработки, характеристики и применение в физике высоких энергий» . 1998. с. 59.
- ^ Павел Tvrdik. «Почему маршрутизация червоточин - важный метод переключения»
- ^ a b c d Доктор Барри М. Кук; Пол Уокер. «Ethernet через SpaceWire - программные проблемы» . 2007. с. 2.