Общий алгоритм скорости передачи ячеек (GCRA) — это алгоритм планирования типа «дырявого ведра » для сетевого планировщика , который используется в сетях с асинхронным режимом передачи (ATM). [1] [2] Он используется для измерения синхронизации ячеек в виртуальных каналах (VC) и/или виртуальных путях (VP) в зависимости от ограничений полосы пропускания и джиттера , содержащихся в контракте трафика для VC или VP, которым принадлежат ячейки. Ячейки, которые не соответствуют ограничениям, установленным контрактом трафика, могут затем быть повторно синхронизированы (задержаны) при формировании трафика или могут быть удалены (отброшены) или понижены в приоритете (понижены) при контроле трафика . Несоответствующие ячейки с пониженным приоритетом могут затем быть отброшены, предпочтительнее ячеек с более высоким приоритетом, нижестоящими компонентами сети, которые испытывают перегрузку. В качестве альтернативы они могут достичь места назначения (завершение VC или VP), если для них достаточно емкости, несмотря на то, что они являются избыточными ячейками с точки зрения контракта: см. Управление приоритетом.
GCRA задается как эталон для проверки трафика на соединениях в сети, то есть контроля параметров использования/сети (UPC/NPC) на интерфейсах пользователь-сеть (UNI), межсетевых интерфейсах или интерфейсах сеть-сеть (INI/NNI). ) . [3] Он также задается в качестве эталона для синхронизации ячеек, передаваемых (ATM PDU Data_Requests) в сеть ATM с помощью сетевой интерфейсной карты (NIC) в хосте, то есть на стороне пользователя UNI. [3] Это гарантирует, что ячейки не будут затем отброшены UPC/NCP в сети, т.е. на сетевой стороне UNI. Однако, поскольку GCRA приводится только для справки, сетевые провайдеры и пользователи могут использовать любой другой алгоритм, который дает тот же результат.
GCRA описан ATM Forum в его интерфейсе пользователь-сеть (UNI) [1] и ITU-T в рекомендации I.371 «Управление трафиком и управление перегрузкой в B-ISDN» . [2] Оба источника описывают GCRA двумя эквивалентными способами: как алгоритм виртуального планирования и как алгоритм дырявого ведра с непрерывным состоянием (рис. 1).
Описание в терминах алгоритма дырявого ведра может быть более простым для понимания с концептуальной точки зрения, поскольку оно основано на простой аналогии ведра с утечкой: см. рисунок 1 на странице дырявого ведра . Однако в литературе возникла путаница по поводу применения аналогии с дырявым ведром для создания алгоритма, который перешел на GCRA. GCRA следует рассматривать как версию «дырявого ведра» как счетчика, а не «дырявого ведра» как очереди .
Однако, несмотря на возможные преимущества в понимании этого описания дырявого ведра, оно не обязательно приводит к созданию лучшего (самого быстрого) кода, если его реализовать напрямую. Об этом свидетельствует относительное количество действий, которые необходимо выполнить в блок-схемах для двух описаний (рисунок 1).
Описание с точки зрения алгоритма дырявого ведра с непрерывным состоянием дано ITU-T следующим образом: «Дырявое ведро с непрерывным состоянием можно рассматривать как ведро с конечной емкостью, реальное содержимое которого истощается с непрерывной скоростью 1 единица. содержимого в единицу времени и содержимое которого увеличивается на приращение T для каждой соответствующей ячейки... Если при прибытии ячейки содержимое сегмента меньше или равно предельному значению τ , то в противном случае ячейка является соответствующей; ячейка не соответствует. Емкость ведра (верхняя граница счетчика) равна ( T + τ )" . [2] Стоит отметить, что поскольку утечка составляет одну единицу контента в единицу времени, приращение для каждой ячейки T и предельное значение τ измеряются в единицах времени.
Рассмотрим блок-схему алгоритма дырявого ведра с непрерывным состоянием, в котором T — интервал эмиссии, а τ — предельное значение: Что происходит, когда прибывает ячейка, так это то, что состояние ведра рассчитывается на основе его состояния, когда прибыла последняя соответствующая ячейка. , X , и сколько утекло за интервал t a – LCT . Это текущее значение сегмента затем сохраняется в X' и сравнивается с предельным значением τ . Если значение X' не превышает τ , ячейка прибыла не слишком рано и поэтому соответствует параметрам контракта; если значение в X' больше, чем τ , то оно не соответствует. Если он соответствует, если он соответствует, потому что было поздно, т.е. ведро пусто ( X' <= 0), X устанавливается в T ; если это было раньше, но не слишком рано ( τ >= X' > 0), X устанавливается в X' + T .
Таким образом, блок-схема напрямую имитирует аналогию с дырявым ведром (используемым в качестве счетчика), где X и X' действуют как аналог ведра.
Алгоритм виртуального планирования, хотя и не так явно связан с такой легкодоступной аналогией, как «дырявое ведро», дает более четкое понимание того, что делает GCRA и как его лучше всего реализовать. В результате прямая реализация этой версии может привести к созданию более компактного и, следовательно, более быстрого кода, чем прямая реализация описания дырявого ведра.
Описание алгоритма виртуального планирования дано ITU-T следующим образом: «Алгоритм виртуального планирования обновляет теоретическое время прибытия (TAT), которое является «номинальным» временем прибытия ячейки при условии, что ячейки отправляются с одинаковым интервалом. с интервалом передачи T , соответствующим скорости передачи ячеек Λ [= 1/ T ], когда источник активен, если фактическое время прибытия ячейки не является «слишком ранним» относительно TAT и допуска τ , связанного со скоростью передачи ячеек . , т. е. если фактическое время прибытия наступает после теоретического времени прибытия минус предельное значение (t a > TAT – τ ), то ячейка соответствует требованиям, в противном случае ячейка является несоответствующей» . [2] Если ячейка не соответствует требованиям, TAT остается неизменным. Если ячейка соответствует требованиям и прибыла до своего TAT (что эквивалентно тому, что ведро не пусто, но меньше предельного значения), то TAT следующей ячейки — это просто TAT + T . Однако если ячейка прибывает после своего TAT , то TAT для следующей ячейки рассчитывается на основе времени прибытия этой ячейки, а не ее TAT . Это предотвращает накопление кредита в случае перерыва в передаче (что эквивалентно тому, что ведро становится менее пустым).
Эта версия алгоритма работает, потому что τ определяет, насколько раньше ячейка может прибыть, чем если бы не было джиттера: см. « Дырявое ведро: допуск на изменение задержки» . Другой способ увидеть это состоит в том, что TAT представляет собой момент, когда ведро опустеет в следующий раз, поэтому время τ до этого момента соответствует моменту, когда ведро наполняется точно до предельного значения. Таким образом, с любой точки зрения, если он прибудет более чем на τ до TAT , еще слишком рано приспосабливаться.
GCRA, в отличие от реализации алгоритма корзины токенов , не имитирует процесс обновления корзины (утечку или регулярное добавление токенов). Вместо этого каждый раз, когда приходит ячейка, она вычисляет объем утечки из ведра с момента последнего расчета уровня или когда ведро опустеет в следующий раз (= TAT ). По сути, это замена процесса утечки часами (реального времени), которые, вероятно, уже имеются в большинстве аппаратных реализаций.
Такая замена процесса на RTC возможна, поскольку ячейки ATM имеют фиксированную длину (53 байта), поэтому T всегда является константой, а вычисление нового уровня сегмента (или TAT ) не требует какого-либо умножения или деления. В результате расчет можно быстро выполнить программно, и хотя при поступлении ячейки выполняется больше действий, чем выполняется корзиной токена, с точки зрения нагрузки на процессор, выполняющий задачу, отсутствие отдельного процесса обновления более чем компенсирует это. Более того, поскольку моделирование обновления сегмента отсутствует, нагрузка на процессор вообще отсутствует, когда соединение находится в режиме ожидания.
Однако если бы GCRA использовалась для ограничения пропускной способности, а не частоты пакетов/кадров в протоколе с пакетами переменной длины (PDU канального уровня), это потребовало бы умножения: по сути, значение, добавляемое в корзину (или TAT) для каждого соответствующего пакета должно быть пропорционально длине пакета: в то время как при описанном GCRA вода в ведре имеет единицы времени, для пакетов переменной длины она должна иметь единицы, являющиеся произведением длина и время пакета. Следовательно, применение GCRA для ограничения полосы пропускания пакетов переменной длины без доступа к быстрому аппаратному умножителю (как в FPGA ) может оказаться непрактичным. Однако его всегда можно использовать для ограничения скорости пакетов или ячеек, если их длина игнорируется.
Множественные реализации GCRA могут применяться одновременно к VC или VP, в функции контроля трафика с двойной дырявой корзиной или функции формирования трафика, например, применительно к VC с переменной скоростью передачи данных (VBR). Это может ограничить ячейки ATM на этом виртуальном канале VBR до устойчивой скорости передачи ячеек (SCR) и максимального размера пакета (MBS). В то же время функция контроля трафика с двойным дырявым сегментом может ограничивать скорость ячеек в пакетах до пиковой скорости ячеек (PCR) и максимального допуска изменения задержки ячейки (CDVt): см. Контракт трафика № Параметры трафика .
Лучше всего это можно понять, когда передача по VBR VC осуществляется в форме сообщений фиксированной длины (CPCS-PDU), которые передаются с некоторым фиксированным интервалом или временем между сообщениями (IMT) и занимают несколько ячеек, MBS, носить их; однако описание трафика VBR и использование двойного дырявого сегмента не ограничиваются такими ситуациями. В этом случае средняя скорость передачи ячеек за интервал IMT представляет собой SCR (=MBS/IMT). Отдельные сообщения могут передаваться с помощью PCR, который может иметь любое значение между полосой пропускания физического канала (1/ δ ) и SCR. Это позволяет сообщению передаваться за период, меньший, чем интервал сообщения IMT, с промежутками между экземплярами сообщения.
В двойном дырявом сегменте к трафику применяется один сегмент с интервалом эмиссии 1/SCR и предельным значением τ SCR , которое дает MBS, равный количеству ячеек в сообщении: см. дырявый сегмент#Максимальный размер пакета . Второй сегмент имеет интервал эмиссии 1/PCR и предельное значение τ PCR , которое учитывает CDV до этой точки на пути соединения: см. Leaky Bucket#Delay Variation Tolerance . Затем ячейки пропускаются в PCR с джиттером τ PCR до максимального количества ячеек MBS. Затем будет разрешен следующий пакет ячеек MBS путем запуска MBS x 1/SCR после первого.
Если клетки поступают пакетом со скоростью выше 1/PCR (клетки MBS поступают менее чем (MBS - 1)/PCR - τ PCR ), или на PCR поступают более клеток MBS, или поступают пакеты клеток MBS ближе, чем IMT, двойное «дырявое» ведро обнаружит это и задержит (формирование), или отбросит, или изменит приоритеты (регулирование) достаточного количества ячеек, чтобы обеспечить соответствие соединения.
На рисунке 3 показан эталонный алгоритм для управления SCR и PCR для потоков ячеек со значениями приоритета потери ячеек (CLP) 1 (низкий) и 0 (высокий), т. е. где ячейки с обоими значениями приоритета обрабатываются одинаково. Подобные эталонные алгоритмы, в которых ячейки с высоким и низким приоритетом обрабатываются по-разному, также приведены в Приложении A к I.371. [2]