Реализация низкой гранулярности таймера для ретрансляции по TCP

Как алгоритм timer-wheel может снизить непроизводительные издержки

В статье объясняется, как можно снизить объём вычислений на цикл (per-tick) с помощью алгоритма timer-wheel, реализующего таймер ретрансляции. Протокол Transmission Control Protocol (TCP) системы AIX® имеет семь таймеров (на каждое соединение), и для их реализации использует функции глобального таймера с двумя значениями гранулярности. Из этой статьи можно узнать, как снизить гранулярность таймера ретрансляции, используя быстрый таймер AIX TCP, и воспользоваться другими преимуществами низкой гранулярности таймера.

Венкат Венкатсубра, разработчик ПО, IBM

Photo of Venkat VenkatsubraВенкат Венкатсубра (Venkat Venkatsubra) занимает должности Technical Chief Engineering Manager (TCEM) и разработчика систем ввода/вывода AIX (STREAMS и протоколы TCP/IP) в команде IBM AIX Network. Венкат занимался разработкой сетевых функций AIX в течение восьми лет. Сейчас он работает над программной реализацией использования технологии Infiniband в кластерах баз данных. Венкат имеет степень бакалавра информатики Индийского института технологий города Карагпур (IIT Kharagpur), Индия. Связаться с ним можно по адресу venkats@us.ibm.com.



Джи Шантала, технический руководитель, IBM

Photo Shantala GШантала Джи (Shantala G) — разработчик и ведущий технический специалист в команде IBM AIX TCP/IP в области ввода/вывода AIX. Она участвовала в разработке TCP/IP и проектах поддержки на платформах OS/2® и AIX в течение десяти лет. Шантала имеет степень бакалавра по электронике и коммуникациям Мангалорского университета (Mangalore University), Индия. Связаться с ней можно по адресу gshantal@in.ibm.com.



17.09.2010

Введение

AIX® TCP поддерживает семь таймеров для каждого соединения:

  • таймер установления соединения;
  • таймер ретрансляции;
  • таймер задержки подтверждения (ACK);
  • таймер запросов (persist);
  • таймер контроля работоспособности (keepalive);
  • таймер FIN_WAIT_2;
  • таймер TIME_WAIT.

Для реализации этих таймеров TCP использует функции глобального таймера, предлагающего два значения гранулярности:

  • tcp_fasttimo: активизируется каждые 200 мс и реализует быстрый таймер;
  • tcp_slowtimo: Iактивизируется каждые 500 мс и реализует медленный таймер.

В TCP-реализации таймера ретрансляции время задержки ретрансляции хранится в единицах цикла (tick) в контрольном блоке TCP, где один цикл равен 500 мс. Каждый раз, когда истекают 500 мс медленного таймера TCP, вызывается tcp_slowtimo. Эта подпрограмма проходит по таблице контрольных блоков TCP и уменьшает на одну единицу значение задержки для каждого соединения, обозначенное в циклах (tick). Когда значение циклов для таймера достигает нуля, вызывается обработчик задержки для данного соединения. В этой реализации нижний предел TCP-таймера определён в 500 мс.

Как известно, TCP динамически рассчитывает время задержки, основываясь на времени двусторонней передачи сигнала, измеряемом самим TCP. В настоящее время минимальное значение задержки ретрансляции по TCP составляет 3 секунды. Тем не менее, в высокоскоростных сетях, например Gigabit Ethernet и 10 Gigabit Ethernet, время двусторонней передачи сигнала (а значит, и задержка ретрансляции), скорее всего, будет намного ниже. В таком случае, при отсутствии передачи данных, теряется 120 МБ трафика в секунду. Для работы с высокоскоростными сетями и сетями с малой задержкой нужен другой, более эффективный метод.

Один из способов достичь более низкой гранулярности для таймера ретрансляции — это использование быстрого таймера TCP (200 мс), который можно настроить на активизацию каждые 50 мс вместо 200 мс. Недостаток этого подхода — вынужденная обработка издержек сканирования всех управляющих блоков протокола (protocol control blocks, PCB) с большей частотой. PCB — это внутренняя структура, которая хранит контрольную информацию соединения. В данной статье объясняется альтернативный метод реализации таймера ретрансляции TCP на основе алгоритма timer wheel.

Алгоритм timer wheel

Кольцо таймеров имеет N слотов. Слот представляет собой единицу времени, такую, как si (slot interval, интервал слота). Указатель в кольце таймеров смещается на одну позицию за каждую единицу времени, как секундная стрелка на часах. Когда указатель перемещается в слот, например в cs (current slot, текущий слот), подразумевается, что время таймеров в этом слоте, если таковые имеются, истекает либо в этот момент, либо в момент, когда указатель достигает того же самого слота в последующих циклах.

При добавлении к кольцу нового таймера с интервалом ti (timer interval) слот для нового таймера ts (timer slot) рассчитывается следующим образом:

ts = ( cs + (ti / si)) % N

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

Например, в кольце таймеров на рисунке 1 есть 8 слотов, от 0 до 7. Видно, что к слотам 1, 3, 4, 5 и 6 привязаны таймеры. Текущее положение указателя — в слоте 1. Три таймера, закреплённые за этим слотом, срабатывают в этот момент или же тогда, когда указатель достигает того же слота в последующем цикле.

Рисунок 1. Кольцо таймеров
Кольцо таймеров

Реализация RTO с помощью алгоритма timer wheel

Данный раздел объясняет реализацию RTO (retransmission time-out, интервала до повторной передачи) с помощью алгоритма timer wheel в AIX. В системе AIX количество слотов установлено как N=7000. Интервал слота (si) в реализации timer wheel настраивается с помощью цифрового значения timer_wheel_tick. Диапазон значений для timer_wheel_tick— от нуля до 100 циклов (tick), где один цикл равен 10 мс. Например, если timer_wheel_tick установлен на единицу, например 10 мс, то период цикла таймера составляет N * si = 70 секунд. Поскольку максимальное значение (tmax) для AIX TCP RTO равно 64 секундам, то этого вполне достаточно для того, чтобы убедиться, что все таймеры ретрансляции в слоте истекают в одно и то же время, а не в последующих циклах.

Значение RTO настраивается с помощью числового значения tcp_low_rto. Диапазон значений tcp_low_rto— от нуля до 3000 мс. Значение RTO в случае его настройки будет установлено как изначальный тайм-аут ретрансляции для всех TCP-соединений в системе.

Даже если tcp_low_rto настроен, алгоритм даёт желаемый результат только при потерях пакетов в соединении, как показано на рисунке 2. В других случаях использование алгоритма неэффективно. В традиционном способе реализации таймера ретрансляции для соединений, где нет потерь пакетов, требуется только установить количество циклов (tick) в контрольном блоке TCP для запуска таймера ретрансляции. Когда приходит подтверждение, таймер ретрансляции сбрасывается, устанавливая значение, равное нулю. Этот метод лучше всего работает для нужд запуска и останова, когда таймер ретрансляции никогда не истекает.v

Можно продолжать использовать традиционный метод реализации таймера ретрансляции, пока не возникнут какие-либо из этих условий:

  • истекает таймер ретрансляции;
  • для данного соединения включена фаза быстрой повторной передачи
Рисунок 2. Соединение с низкой гранулярностью
Соединение с низкой гранулярностью
A. Включение низкого RTO
Таймер ретрансляции истекает для соединения впервые или включена фаза быстрой повторной передачи. Задействуется более низкая гранулярность для таймера ретрансляции в этом соединении, и пакет снова пересылается. Поскольку это повторная передача, то для расчёта RTT (время распространения пакета туда и обратно) этот сегмент не измеряется. Таймер ретрансляции запускается добавлением таймера в соответствующий слот кольца таймеров.
B. Получение подтверждения
Подтверждение для переданного пакета получено. Отключение таймера ретрансляции (удаление таймера из кольца таймеров).
C. Измерение времени сегмента
Сегмент посылается с последовательностью 'b' и таймер ретрансляции запускается. Время этого сегмента для расчёта RTT измеряется сохранением временной метки. Таймер ретрансляции запускается добавлением таймера в соответствующий слот кольца таймеров.
D. Получен ACK для сегмента
Получено подтверждение 'c' больше 'b'. Таймер ретрансляции останавливается удалением таймера из соответствующего слота кольца таймеров. Новое RTT измеряется как текущее время минус сохранённая временная метка посланного сегмента с последовательностью 'b'. Измеренное RTT используется для вычисления нового значения тайм-аута передачи.
E. Передача сегмента с RTO, рассчитанным в соответствии с низким значением RTO
Таймер передачи помещается в соответствующий слот кольца таймеров.
F. Истечение таймера ретрансляции
Для соединения, использующего алгоритм timer wheel, истекает время таймера ретрансляции. Указатель перемещается в тот слот колеса таймеров, куда был помещён таймер ретрансляции в предыдущий раз. Вызывается процедура управления таймером для обработки истечения таймера ретрансляции.

Заключение

При использовании алгоритма timer wheel запуск и остановка таймера обходятся довольно дорого. Если таймеры в слоте реализованы в виде связанных списков, то добавление или удаление таймера из списка должно быть синхронизировано с помощью блокировки цепочки слотов.

С другой стороны, использование алгоритма timer wheel для реализации таймера ретрансляции уменьшает количество вычислений на цикл (tick). При использовании timer wheel в слоте находятся только те таймеры, время которых истекает, когда указатель достигает этого слота. Нет необходимости сканировать все PCB для проверки, какой таймер для какого соединения установлен.

Реализация низкой гранулярности таймера позволяет администратору устанавливать малое значение RTO, вплоть до 10 мс. Это особенно полезно для TCP-соединений в высокоскоростных сетях и в сетях с малой задержкой, таких, как Gigabit и 10 Gigabit Ethernet, где иногда случаются потери пакетов.

Ресурсы

Научиться

Получить продукты и технологии

  • Ознакомительные версии ПО IBM®: используйте в вашем следующем проекте программное обеспечение, которое можно загрузить непосредственно с сайта developerWorks.(EN)

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=AIX и UNIX
ArticleID=523757
ArticleTitle=Реализация низкой гранулярности таймера для ретрансляции по TCP
publish-date=09172010