Коммутация по принципу червоточины

В режиме червоточинной коммутации каждый пакет разбивается на небольшие части — так называемые флиты (единицы управления потоком данных).

Обычно первые флиты, называемые заголовочными (header flits), содержат информацию о маршруте пакета (например, адрес назначения) и определяют маршрутизацию всех последующих флитов, связанных с данным пакетом. За ними следуют один или более флитов тела (body flits), несущих полезные данные. Завершающие флиты («tail flits») выполняют операции учёта для закрытия соединения между двумя узлами.

В червоточинной коммутации каждый буфер маршрутизатора либо свободен, либо выделен одному пакету. Заголовочный флит может быть передан в буфер, если тот свободен; после этого буфер закрепляется за данным пакетом. Флиты тела или завершения пакета могут быть переданы, если буфер уже назначен соответствующему пакету и не заполнен полностью. Последний флит освобождает буфер. Если заголовочный флит блокируется в сети, буфер постепенно заполняется; после полного заполнения передача новых флитов невозможна: этот эффект называется «обратное давление» (back-pressure) и может распространяться вплоть до источника пакета.

Название связано со способом передачи пакетов: адрес настолько компактен, что может быть переведён до поступления сообщения, что позволяет маршрутизатору быстро определить маршрут, а затем «устраниться» из дальнейшего диалога. Так как пакет передаётся пофлитно, он может занимать одновременно несколько буферов — образуя своеобразный «червеобразный» след.

Такое поведение близко к частичной коммутации (англ. cut-through switching), часто называемой «виртуальной частичной коммутацией» (англ. virtual cut-through). Главное отличие: частичная коммутация резервирует буферы и ширину канала на уровне всего пакета, а червоточинная — на уровне отдельного флита^[5].

В случае циклических зависимостей обратное давление может привести к взаимоблокировке.

По большинству характеристик червоточинная коммутация схожа с техникой передачи ячеек в ATM или MPLS, но, в отличие от них, здесь «ячейка» не обязательно должна быть полностью занесена в очередь.

Особенностью червоточинной коммутации является применение виртуальных каналов:

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

Три потока в сети 2×2 при червоточинной коммутации

Рассмотрим сеть размером 2×2 (см. рисунок справа), в которой требуется передать 3 пакета: розовый из 4 флитов «UVWX» — от C к D; синий из 4 флитов «abcd» — от A к F; зелёный из 4 флитов «ijkl» — от E к H. Предположим, что маршруты рассчитаны заранее, и возникает конфликт буфера в левом нижнем маршрутизаторе. Пропускная способность равна 1 флиту за единицу времени.

Сначала рассмотрим передачу розового потока: на первом такте флит «U» занимает первый буфер; на втором такте он переходит в следующий буфер (считается, что вычисление маршрута моментальное), а «V» поступает в первый буфер и так далее.

Синий и зелёный потоки требуют пошагового описания:

• Момент 1: оба потока передают по первому флиту: «i» и «a».
• Момент 2: флит «i» проходит к следующему буферу. Но буфер выделяется пакету с первого до последнего флита, поэтому флит «a» не может быть передан дальше. Начинается эффект обратного давления. Флит «j» замещает «i» в буфере, «b» передаётся.
• Момент 3: зелёный пакет проходит вперёд. Синий флит «c» не может быть передан (буфер занят флитами «a» и «b»): обратное давление доходят до источника пакета.
• Моменты 4: ситуация аналогична моменту 3.
• Момент 5: зелёный пакет более не использует левый нижний буфер, синий поток разблокируется и передаётся (учитываем моментальную передачу информации о разблокировке).
• Моменты 6–10: синий пакет полностью проходит через сеть.

• Червоточинная коммутация значительно эффективнее использует буферы, чем частичная коммутация: если последняя требует большие буферы, достаточные для целых пакетов, то по принципу червоточины достаточно нескольких буферов на флиты.
• Перемещение пакета на следующий узел возможно не дожидаясь накопления всего пакета, чем достигается снижение задержки сети по сравнению с коммутацией с промежуточным хранением.
• Разделяется (декуплируется) процесс выделения полосы пропускания и буферизация.

Червоточинная коммутация в первую очередь применяется в многопроцессорных системах, особенно в гиперкубах. В гиперкубических компьютерах каждый процессор (CPU) соединён с несколькими соседями по фиксированной схеме, что сокращает число переходов между процессорами. Каждому процессору присваивается номер (обычно 8- или 16-битный), выступающий в роли адреса; пакеты адресуются по этому номеру в заголовке. При поступлении на промежуточный маршрутизатор тот быстро читает заголовок, настраивает цепочку до следующего маршрутизатора — и «устраняется» из дальнейшей передачи, что существенно снижает задержку в сравнении с классическим хранением и последующей передачей (store-and-forward).

В последнее время червоточинная коммутация активно применяется в сетях на кристалле (англ. Network on a chip, NOC) — как на уровне процессорных ядер, так и на уровне отдельных функциональных блоков единого интегрального микросхемного устройства. По мере роста задержек на проводах и других ограничений при увеличении числа связанных элементов значение структурированной сети и эффективного управления потоком только возрастает.

Технологии IEEE 1355 и SpaceWire реализуют червоточинную коммутацию.

Расширением червоточинной коммутации служит режим виртуальных каналов, где несколько виртуальных каналов мультиплексируются по одному физическому. Каждый односторонний виртуальный канал реализован независимой парой буферов для флитов. Таким образом, разные пакеты могут параллельно использовать физический канал на уровне флитов.

Первоначально виртуальные каналы вводились для предотвращения взаимоблокировок (deadlock), однако они также снижают блокировки по принципу червоточины и улучшают производительность сети по задержке и пропускной способности. Блокировка по принципу червоточины происходит, когда пакет занимает канал и не позволяет другим пакетам его использовать — другие вынуждены ждать.

Рассмотрим, что произойдёт при отсутствии и наличии виртуальных каналов:

• Пусть пакет P0 занял канал между двумя маршрутизаторами; без виртуальных каналов следующий пакет P1 вынужден ждать, пока P0 полностью не передастся.
• Если задействованы виртуальные каналы:

   * При прибытии P1 физический канал можно разделить между ними на уровне флитов, оба пакета проходят с половинной скоростью (детально — в зависимости от схемы арбитража).
   * Если P0 — длинный пакет, а P1 — короткий управляющий (на несколько флитов), P1 сможет быстро пройти оба маршрутизатора, пока P0 временно замедляется; это понижает задержку для P1.
   * Если P0 временно заблокирован дальше по пути, пропускная способность повышается за счёт возможности передачи P1 по свободному каналу, тогда как без виртуальных каналов весь канал был бы занят P0, не использующим реальную пропускную способность.[6].

Использование виртуальных каналов для снятия блокировок аналогично применению виртуального выходного буфера для снижения блокировки у головы очереди.

В рамках одного пакета, передаваемого по принципу червоточины, может совмещаться как исходная маршрутизация (source routing), так и логическая маршрутизация.

Значение первого байта в пакетах Myrinet или SpaceWire определяет адрес назначения. Каждый коммутатор SpaceWire использует этот адрес для выбора направления передачи^[7].