Алгоритм общего расчета скорости передачи ячеек

Алгоритм общей скорости ячеек (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 в его Интерфейсе «пользователь-сеть» (UNI) ^[1] и МСЭ -Т в рекомендации 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 . Это предотвращает накопление кредита, когда в передаче есть пробел (эквивалентно тому, что ведро становится менее чем пустым).

Эта версия алгоритма работает, потому что τ определяет, насколько раньше может прибыть ячейка, чем если бы не было джиттера: см. leaky bucket: delay variation permit . Другой способ увидеть это — TAT представляет, когда ведро в следующий раз опустеет, поэтому время τ до этого — это когда ведро точно заполнено до предельного значения. Таким образом, в любом представлении, если оно прибывает больше, чем за τ до TAT , слишком рано для соответствия.

GCRA, в отличие от реализаций алгоритма token bucket , не имитирует процесс обновления bucket (утечку или регулярное добавление токенов). Вместо этого, каждый раз, когда поступает ячейка, он вычисляет объем, на который утечет bucket с момента последнего расчета его уровня или когда bucket в следующий раз опустеет (= TAT ). По сути, это замена процесса утечки на часы (реального времени), которые, скорее всего, уже есть в большинстве аппаратных реализаций.

Эта замена процесса на RTC возможна, поскольку ячейки ATM имеют фиксированную длину (53 байта), поэтому T всегда является константой, а расчет нового уровня ведра (или TAT ) не включает в себя умножение или деление. В результате расчет может быть выполнен быстро в программном обеспечении, и хотя при поступлении ячейки выполняется больше действий, чем выполняется токен-ведром, с точки зрения нагрузки на процессор, выполняющий задачу, отсутствие отдельного процесса обновления более чем компенсирует это. Более того, поскольку нет моделирования обновления ведра, нет никакой нагрузки на процессор, когда соединение находится в состоянии покоя.

Однако, если бы GCRA использовался для ограничения полосы пропускания, а не частоты пакетов/кадров в протоколе с пакетами переменной длины (PDU уровня связи), это включало бы умножение: в основном значение, добавляемое к ведру (или к TAT) для каждого соответствующего пакета, должно было бы быть пропорционально длине пакета: тогда как с GCRA, как описано, вода в ведре имеет единицы времени, для пакетов переменной длины она должна была бы иметь единицы, которые являются произведением длины пакета и времени. Следовательно, применение GCRA для ограничения полосы пропускания пакетов переменной длины без доступа к быстрому аппаратному умножителю (как в FPGA ) может быть непрактичным. Однако его всегда можно использовать для ограничения скорости пакетов или ячеек, пока их длины игнорируются.

Несколько реализаций GCRA могут применяться одновременно к VC или VP, в функции контроля трафика с двойным дырявым ведром или функции формирования трафика, например, применяемой к VC с переменной скоростью передачи битов (VBR). Это может ограничить ячейки ATM на этом VC с VBR до постоянной скорости передачи ячеек (SCR) и максимального размера пакета (MBS). В то же время функция контроля трафика с двойным дырявым ведром может ограничить скорость ячеек в пакетах до пиковой скорости передачи ячеек (PCR) и максимального допуска изменения задержки ячеек (CDVt): см. Traffic Contract#Traffic Parameters .

Это можно лучше всего понять, когда передача по VBR VC осуществляется в форме сообщений фиксированной длины (CPCS-PDU), которые передаются с некоторым фиксированным интервалом или временем между сообщениями (IMT) и требуют для своей передачи несколько ячеек, MBS; однако описание трафика VBR и использование двойного дырявого ведра не ограничиваются такими ситуациями. В этом случае средняя скорость ячеек в интервале IMT — это SCR (=MBS/IMT). Отдельные сообщения могут передаваться с PCR, которая может быть любым значением между пропускной способностью физического канала (1/ δ ) и SCR. Это позволяет передавать сообщение в течение периода, который меньше интервала сообщения IMT, с промежутками между экземплярами сообщения.

В двойном дырявом ведре один ведёрко применяется к трафику с интервалом эмиссии 1/SCR и предельным значением τ _SCR , которое даёт MBS, равный числу ячеек в сообщении: см. дырявое ведро#Максимальный размер пакета . Второй ведёрко имеет интервал эмиссии 1/PCR и предельное значение τ _PCR , которое допускает CDV до этой точки на пути соединения: см. дырявое ведро#Допуск вариации задержки . Затем ячейки пропускаются в PCR с джиттером τ _PCR до максимального числа ячеек MBS. Следующий пакет ячеек MBS затем будет пропущен через MBS x 1/SCR после первого.

Если ячейки поступают пачкой со скоростью, превышающей 1/PCR (ячейки MBS поступают менее чем за (MBS - 1)/PCR - τ _PCR ), или в PCR поступает больше ячеек MBS, или пачки ячеек MBS поступают на расстояние, меньшее, чем IMT, двойной дырявый механизм обнаружит это и задержит (формирует), отбросит или деприоритезирует (контролирует) достаточное количество ячеек, чтобы соединение стало согласованным.

На рисунке 3 показан эталонный алгоритм для контроля SCR и PCR для обоих значений Cell Loss Priority (CLP) 1 (низкий) и 0 (высокий) потоков клеток, т.е. где клетки с обоими значениями приоритета обрабатываются одинаково. Аналогичные эталонные алгоритмы, где клетки с высоким и низким приоритетом обрабатываются по-разному, также приведены в Приложении A к I.371. ^[2]

• Асинхронный режим передачи
• Дырявое ведро
• UPC и NPC
• ННИ
• Договор на перевозку
• Контроль допуска к подключению
• Формирование трафика
• Дорожная полиция (связь)
• Ведро токенов