Алгоритм родового скорость ячеек (GCRA) представляет собой дырявое ведро типа планирование алгоритма для сетевого планировщика , который используется в Asynchronous Transfer Mode сетей (ATM). [1] [2] Он используется для измерения синхронизации ячеек на виртуальных каналах (VC) и / или виртуальных трактах (VP) в сравнении с пределами полосы пропускания и джиттера, содержащимися в контракте трафика для VC или VP, которым принадлежат ячейки. Ячейки, которые не соответствуют ограничениям, указанным в контракте на трафик, могут затем быть повторно синхронизированы (отложены) при формировании трафика., или могут быть отброшены (отброшены) или с пониженным приоритетом (пониженным) при контроле трафика . Несоответствующие ячейки, приоритет которых понижен, могут затем быть отброшены, вместо ячеек с более высоким приоритетом, нисходящими компонентами в сети, которые испытывают перегрузку. В качестве альтернативы они могут достичь своего пункта назначения (завершение VC или VP), если для них достаточно пропускной способности, несмотря на то, что они являются избыточными ячейками с точки зрения контракта: см. Управление приоритетом .
GCRA приводится в качестве справочного материала для проверки трафика на соединениях в сети, т. Е. Использования / управления параметрами сети (UPC / NPC) на пользовательско-сетевых интерфейсах (UNI) или межсетевых интерфейсах или сетевых-сетевых интерфейсах (INI / NNI). ). [3] Он также используется в качестве эталона для синхронизации ячеек, передаваемых (Data_Requests ATM PDU) в сеть ATM картой сетевого интерфейса (NIC) в хосте, то есть на стороне пользователя UNI. [3] Это гарантирует, что UPC / NCP не отбрасывают ячейки в сети, т. Е. На сетевой стороне UNI. Однако, поскольку GCRA приводится только для справки, сетевые провайдеры и пользователи могут использовать любой другой алгоритм, который дает тот же результат.
Описание 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 канального уровня), это потребовало бы умножения: в основном значение, добавляемое к ведру (или to TAT) для каждого соответствующего пакета должен быть пропорционален длине пакета: тогда как с GCRA, как описано, вода в ведре имеет единицы времени, для пакетов переменной длины она должна иметь единицы, которые являются продуктом длина и время пакета. Следовательно, применение GCRA для ограничения пропускной способности пакетов переменной длины без доступа к быстрому аппаратному умножителю (как в FPGA ) может оказаться непрактичным. Однако его всегда можно использовать для ограничения скорости передачи пакетов или ячеек, если их длина игнорируется.
Контроллер Dual Leaky Bucket [ править ]
Множественные реализации GCRA могут применяться одновременно к VC или VP, в функции контроля трафика с двумя дырявыми ведрами или формирования трафика, например, применительно к VC с переменной скоростью передачи данных (VBR). Это может ограничить ячейки ATM на этом VBR VC до устойчивой скорости ячеек (SCR) и максимального размера пакета (MBS). В то же время функция контроля трафика двойного дырявого ведра может ограничивать скорость ячеек в пакетах до пиковой скорости ячеек (PCR) и максимального допуска изменения задержки ячеек (CDVt): см. Контракт трафика № Параметры трафика .
Лучше всего это понять, когда передача по VBR VC осуществляется в форме сообщений фиксированной длины (CPCS-PDUs), которые передаются с некоторым фиксированным интервалом или временем между сообщениями (IMT) и занимают несколько ячеек, MBS, носить их; однако описание трафика VBR и использование двойного дырявого ведра не ограничиваются такими ситуациями. В этом случае средняя скорость передачи ячеек в интервале IMT равна SCR (= MBS / IMT). Отдельные сообщения могут передаваться в PCR, которое может иметь любое значение между полосой пропускания физического канала (1 / δ ) и SCR. Это позволяет передавать сообщение в период, меньший, чем интервал IMT сообщения, с промежутками между экземплярами сообщения.
В двойном дырявом ведре одно ведро применяется к трафику с интервалом передачи 1 / SCR и предельным значением τ SCR, которое дает MBS, которое представляет собой количество ячеек в сообщении: см. Дырявое ведро # Максимальный размер пакета . Второе ведро имеет интервал излучения 1 / PCR и предельное значение τ PCR, которое учитывает CDV до этой точки на пути соединения: см. « Дырявый бакет» # Delay Variation Tolerance . Затем ячейки пропускаются в PCR с джиттером τ PCR до максимального количества ячеек MBS. Следующий пакет ячеек MBS будет разрешен через запуск MBS x 1 / SCR после первого.
Если ячейки прибывают пачкой со скоростью выше 1 / ПЦР (ячейки MBS прибывают с менее чем (MBS - 1) / ПЦР - τ ПЦР ), или больше ячеек MBS прибывает на ПЦР, либо прибывают пачки ячеек MBS ближе, чем IMT, двойное дырявое ведро обнаружит это и задержит (формирование), отбросит или отменит приоритет (применение политик) достаточного количества ячеек, чтобы соединение соответствовало.
На рисунке 3 показан эталонный алгоритм управления SCR и PCR для потоков ячеек со значениями 1 (низкий) и 0 (высокий) приоритета потери ячеек (CLP), то есть где ячейки с обоими значениями приоритета обрабатываются одинаково. Аналогичные эталонные алгоритмы, в которых ячейки с высоким и низким приоритетом обрабатываются по-разному, также приведены в Приложении A к I.371. [2]
См. Также [ править ]
- асинхронный режим передачи
- Дырявое ведро
- UPC и NPC
- NNI
- Контракт на движение
- Контроль допуска подключения
- Формирование трафика
- Контроль за дорожным движением (связь)
- Ведро токенов
Ссылки [ править ]
- ^ a b ATM Forum, Пользовательский сетевой интерфейс (UNI), версия 3.1, ISBN 0-13-393828-X , Prentice Hall PTR, 1995.
- ^ a b c d e ITU-T, Управление трафиком и управление перегрузкой в B ISDN , Рекомендация I.371, Международный союз электросвязи, 2004 г., Приложение A, стр. 87.
- ^ a b ITU-T, Управление трафиком и управление перегрузкой в B ISDN , Рекомендация I.371, Международный союз электросвязи, 2004 г., стр. 17
