Общий алгоритм скорости передачи ячеек - Generic cell rate algorithm

В общий алгоритм скорости передачи ячеек (GCRA) - это дырявое ведро -тип алгоритм планирования для сетевой планировщик что используется в асинхронный режим передачи (Банкоматы) сети.[1][2] Он используется для измерения времени клетки на виртуальные каналы (VC) и или Виртуальные пути (ПО) против пропускная способность и дрожь ограничения, содержащиеся в договор перевозки для VC или VP, которым принадлежат ячейки. Ячейки, которые не соответствуют ограничениям, указанным в контракте на трафик, могут быть затем повторно синхронизированы (отложены) в формирование трафика, или может быть отброшен (отброшен) или понижен в приоритете (понижен в должности) в контроль дорожного движения. Несоответствующие ячейки, приоритет которых понижен, могут затем быть отброшены, вместо ячеек с более высоким приоритетом, нисходящими компонентами в сети, которые испытывают перегрузку. В качестве альтернативы они могут достичь пункта назначения (завершение VC или VP), если для них достаточно емкости, несмотря на то, что они являются избыточными ячейками в соответствии с контрактом: см. приоритетный контроль.

GCRA используется в качестве справочного материала для проверки трафика на соединениях в сети, т.е. использование / контроль параметров сети (UPC / NPC) в пользовательско-сетевые интерфейсы (UNI) или межсетевые интерфейсы или сетевые интерфейсы (INI / NNI).[3] Он также используется в качестве эталона для синхронизации ячеек, передаваемых (Data_Requests ATM PDU) в сеть ATM посредством сетевая карта (NIC) на хосте, то есть на стороне пользователя UNI.[3] Это гарантирует, что UPC / NCP не отбрасывают ячейки в сети, то есть на сетевой стороне UNI. Однако, поскольку GCRA приводится только для справки, сетевые провайдеры и пользователи могут использовать любой другой алгоритм, который дает такой же результат.

Описание GCRA

Рисунок 1: Эквивалентные версии общего алгоритма скорости передачи ячеек

GCRA описывается Форум банкоматов в его Пользовательско-сетевой интерфейс (UNI)[1] и по ITU-T в рекомендации I.371 Контроль трафика и контроль перегрузки в B-ISDN .[2] Оба источника описывают GCRA двумя эквивалентными способами: как алгоритм виртуального планирования и как алгоритм дырявого ведра с непрерывным состоянием (рисунок 1).

Описание протекающего ведра

Описание с точки зрения дырявое ведро алгоритм может быть более легким для понимания с концептуальной точки зрения, поскольку он основан на простой аналогии ведра с утечкой: см. рисунок 1 на дырявое ведро страница. Однако в литературе существует путаница по поводу применения аналогии дырявого ведра для создания алгоритма, который перешел на GCRA. GCRA следует рассматривать как версию дырявое ведро как метр скорее, чем дырявое ведро как очередь.

Однако, хотя понимание этого описания дырявого ведра дает возможные преимущества, оно не обязательно приводит к получению наилучшего (самого быстрого) кода, если реализовано напрямую. Об этом свидетельствует относительное количество действий, которые необходимо выполнить, на блок-схемах для двух описаний (рисунок 1).

Описание в терминах алгоритма дырявого ведра в непрерывном состоянии дается ITU-T следующим образом: «Дырявое ведро в непрерывном состоянии можно рассматривать как ведро с конечной емкостью, реальное содержимое которого истекает с непрерывной скоростью 1 единица. содержания в единицу времени, и содержание которого увеличивается с шагом Т для каждой соответствующей ячейки ... Если при поступлении ячейки содержимое корзины меньше или равно предельному значению τ, значит клетка конформная; в противном случае ячейка не соответствует требованиям. Вместимость ковша (верхняя граница счетчика) составляет (Т + τ)” .[2] Стоит отметить, что, поскольку утечка составляет одну единицу содержимого в единицу времени, приращение для каждой ячейки Т и предельное значение τ в единицах времени.

Рассмотрение блок-схемы алгоритма дырявого ведра в непрерывном состоянии, в котором Т - интервал эмиссии и τ является предельным значением: что происходит, когда прибывает ячейка, так это то, что состояние корзины вычисляется из ее состояния, когда прибыла последняя соответствующая ячейка, Икс, и сколько просочилось за интервал, та – LCT. Это текущее значение сегмента затем сохраняется в ИКС' и сравнивается с предельным значением τ. Если значение в ИКС' не больше чем τ, ячейка не пришла слишком рано и соответствует параметрам контракта; если значение в ИКС' больше, чем τ, то это не соответствует. Если он соответствует, то, если он соответствует, потому что было поздно, т.е. ведро пустое (ИКС' <= 0), Икс установлен на Т; если было рано, но не рано, (τ >= ИКС' > 0), Икс установлен на ИКС' + Т.

Таким образом, блок-схема воспроизводит аналогию с протекающим ведром (используемым в качестве счетчика) напрямую, с Икс и ИКС' выступающий аналог ведра.

Описание виртуального расписания

Алгоритм виртуального планирования, хотя и не так явно связан с такой легкодоступной аналогией, как дырявое ведро, дает более четкое представление о том, что делает GCRA и как его лучше всего реализовать. В результате прямая реализация этой версии может привести к более компактному и, следовательно, более быстрому коду, чем прямая реализация описания дырявого ведра.

Описание в терминах алгоритма виртуального планирования дается ITU-T следующим образом: «Алгоритм виртуального планирования обновляет теоретическое время прибытия (TAT), которое является« номинальным »временем прибытия ячейки, предполагая, что ячейки отправляются через равные промежутки времени. при интервале выбросов Т соответствует скорости передачи ячеек Λ [= 1/Т], когда источник активен. Если фактическое время прибытия ячейки не слишком раннее по сравнению с ТАТ и терпимость τ связано со скоростью передачи ячеек, т.е. если фактическое время прибытия превышает его теоретическое время прибытия минус предельное значение (tа > ТАТ – τ), то клетка конформная; в противном случае ячейка не соответствует требованиям ».[2] Если ячейка не соответствует требованиям, тогда ТАТ оставлен без изменений. Если ячейка соответствует требованиям и прибыла до своего TAT (эквивалентно тому, что корзина не пуста, но меньше предельного значения), то следующая ячейка ТАТ просто ТАТ + Т. Однако, если клетка прибывает после своего ТАТ, то ТАТ для следующей ячейки рассчитывается из времени прибытия этой ячейки, а не ее ТАТ. Это предотвращает накопление кредита, когда есть перерыв в передаче (что эквивалентно тому, что ведро становится меньше пустого).

Эта версия алгоритма работает, потому что τ определяет, насколько раньше ячейка может прибыть, чем если бы не было дрожания: см. дырявое ведро: допуск отклонения задержки. Другой способ увидеть это - ТАТ обозначает, когда ведро опустеет в следующий раз, поэтому время τ до этого ведро наполняется точно до предельного значения. Таким образом, в любом случае, если он прибывает более чем τ перед ТАТ, пока рано соглашаться.

Сравнение с ведром токенов

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

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

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

Контроллер двойного протекающего ведра

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

Рисунок 2: Пример тайминга ячеек при подключении VBR

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

Рисунок 3: Эталонный алгоритм для устойчивой скорости ячеек (SCR) и пиковой скорости ячеек (PCR) для CLP = 0 + 1 поток ячеек

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

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

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

Смотрите также

использованная литература

  1. ^ а б ATM Forum, Пользовательский сетевой интерфейс (UNI), версия 3.1, ISBN  0-13-393828-X, Prentice Hall PTR, 1995.
  2. ^ а б c d е МСЭ-Т, Контроль трафика и контроль перегрузки в B ISDN, Рекомендация I.371, Международный союз электросвязи, 2004 г., Приложение A, стр. 87.
  3. ^ а б МСЭ-Т, Контроль трафика и контроль перегрузки в B ISDN, Рекомендация I.371, Международный союз электросвязи, 2004 г., стр. 17