Алгоритм RED: красный свет для лишних пакетов

Популярность технологии ATM уже не вызывает сомнений. ATM служит транспортным протоколом для передачи различных видов трафика, причем для каждого из них существует свой тип сервиса - CBR, VBR, ABR, UBR.

UBR достаточно прост в реализации, поэтому очень широко применяется для передачи трафика локальных сетей и Internet. При этом к трафику не предъявляются какие-либо жесткие требования, и сеть просто передает столько данных пользователя, сколько может (и как может). Соответственно, "поведение" трафика в сети ATM становится неконтролируемым, что приводит к нежелательным последствиям, таким как перегрузки и потери данных.

Для улучшения функциональных характеристик UBR в него был введен ряд механизмов управления трафиком, в том числе EPD (ранний сброс пакетов) и PPD (сброс остатков пакета). Данный тип сервиса получил название UBR+. Мы рассмотрим еще один используемый в UBR+ алгоритм, который вызывает большой интерес у специалистов, - RED (Random Early Detection, своевременное обнаружение перегрузок).

Изначально алгоритм RED был предложен для пакетных сетей; он хорошо себя зарекомендовал при работе с протоколом TCP. Поэтому прежде чем рассказать о его применении в сетях ATM, мы остановимся на том, как работает RED в сетях TCP/IP.

RED в сетях TCP/IP

TCP - протокол, ориентированный на соединение, в связи с чем он имеет ряд особенностей. TCP начинает свою работу с процедуры установления соединения и согласования (синхронизации) основных параметров, таких как размер окна подтверждения и максимальный размер пакета. После синхронизации TCP сразу посылает столько пакетов, сколько допускает размер окна подтверждения.

Подобный всплеск нагрузки не представляет опасности для скоростных локальных сетей. Однако в комплексных сетях, где могут существовать низкоскоростные участки и перегруженные коммутаторы, неожиданное появление большого числа пакетов способно привести к серьезному снижению пропускной способности (что обуславливается потерями трафика и последующей его ретрансляцией). В современных реализациях протокола TCP избежать этих неприятностей позволяет механизм Slow Start.

В случае использования Slow Start протокол TCP, синхронизировав параметры, сначала посылает один пакет, затем (когда получено подтверждение его доставки) - два, четыре, и так до тех пор, пока количество одновременно передаваемых пакетов не окажется соответствующим размерам окна подтверждения. При потере хотя бы одного из пакетов источник начинает процедуру Slow Start заново. В различных реализациях TCP (TCP Tahoe, TCP Reno) количество пакетов, с которого начинается повторная передача, и коэффициент увеличения числа пакетов могут динамически зависеть от времени распространения пакетов (Round-trip time - RTT). Это дает возможность достаточно адекватно реагировать на состояние сети.

Алгоритм RED позволяет контролировать нагрузку с помощью выборочного случайного уничтожения некоторых пакетов, что заставляет протоколы, подобные TCP, снижать скорость передачи. При потере хотя бы одного пакета протокол TCP начинает процедуру Slow Start заново; это снижает объем трафика, поступающего в сеть. Наиболее разумно - не дожидаться полной перегрузки сети (тогда будет удален весь трафик), а уже на подступах к опасному порогу начать выборочное уничтожение отдельных пакетов, информируя тем самым источники нагрузки о текущей пропускной способности сети.

Кроме того, алгоритм RED в сетях TCP/IP помогает избавиться от проблемы, известной под названием "тотальная синхронизация". Она возникает, когда несколько источников, работающих через один и тот же перегруженный сегмент сети, обнаруживают потери пакетов. Как следствие, эти источники одновременно снижают скорость, а затем (также одновременно) постепенно ее увеличивают, что приводит к новой перегрузке, потере пакетов и повторению всей процедуры. Таким образом, состояние сети периодически меняется от простоя до перегрузки.

RED позволяет избежать тотальной синхронизации, выборочно уничтожая пакеты определенных источников. А поскольку по чисто вероятностным причинам большие пакеты уничтожаются чаще маленьких, можно надеяться на достаточно справедливое распределение полосы пропускания. Разумеется, селективное уничтожение пакетов приводит к нужному результату, только когда источник обладает каким-либо интеллектуальным механизмом контроля за скоростью передачи.

Все вышесказанное относится и к работе протокола TCP через ATM. Поэтому алгоритм RED может вполне эффективно использоваться для управления передачей трафика TCP/IP в сетях ATM. Кроме того, в ATM-сетях он применяется в качестве механизма управления трафиком, дополняющего уже существующие методы. Как это происходит и какие дополнительные возможности дает, мы рассмотрим в следующем разделе.

RED в сетях ATM

Управление трафиком является ключевым компонентом стабильной работы ATM-сетей. В общем случае существуют два типа управления - превентивный и адаптивный.

Превентивный контроль базируется на соблюдении трафик-контракта. Источник трафика должен "вписаться" в заранее оговоренные рамки качества обслуживания с помощью, например, широко известных механизмов контроля Leaky Bucket и Virtual Scheduling. Превентивный контроль применяется в основном для CBR и VBR, в которых характеристики трафика известны или поддаются прогнозированию.

Адаптивный контроль основан на использовании свободной полосы пропускания. Обычно он реализуется для ABR и UBR, которые не имеют жестких требований к качеству обслуживания. Адаптивный контроль осуществляется с помощью обратной связи между источником и коммутатором ATM, которая может быть явной (для передачи информации о перегрузках применяются специальные ячейки, как в ABR) или скрытой (поведение источника трафика меняется в соответствии с изменением поведения сети).

Алгоритм RED в сетях ATM использует скрытую обратную связь для уведомления о перегрузках путем выборочного уничтожения ячеек пользователя. Вместо того чтобы дожидаться перегрузки и переполнения буферов, следствием чего станет уничтожение всех поступающих данных, RED уничтожает часть поступающих ячеек. Их число и частота уничтожения определяются параметром, называемым вероятностью уничтожения (Pa). Этот параметр рассчитывается каждый раз в соответствии с текущим состоянием ресурсов ATM-коммутатора, т.е. фактически определяется длиной очереди на обслуживание трафика в ATM-коммутаторе.

Средняя длина очереди (QueueLength) рассчитывается так:

QueueLength=(1-1/2ⁿ)? PreviousQueueLength+CurrentQueueLength?1/2ⁿ.

Здесь PreviousQueueLength - длина очереди при предыдущем подсчете; CurrentQueueLength - текущая длина очереди; n - весовой коэффициент (n>1), который определяет администратор сети, исходя из следующих соображений.

Если n имеет малое значение, средняя длина очереди QueueLength фактически определяется текущей длиной очереди CurrentQueueLength. Тогда алгоритм RED четко и быстро реагирует на любые изменения текущей длины очереди, что позволяет ATM-коммутатору практически мгновенно избавляться от лишних ячеек при малейшей опасности перегрузки. Однако при очень малых значениях n RED станет необоснованно сбрасывать ячейки даже при небольших временных увеличениях очередей, которые не представляют опасности и могут быть обработаны без потерь.

Если коэффициент n имеет большое значение, средняя длина очереди QueueLength становится функцией от предыдущей длины очереди PreviousQueueLength. Алгоритм RED достаточно медленно реагирует на изменения длины очереди, что позволяет ATM-коммутатору как бы сглаживать "пики" и "провалы" трафика без удаления ячеек. Но при очень больших значениях n RED может оказаться настолько медлительным, что будет продолжать уничтожение ячеек, даже когда длина очереди станет меньше минимального порога срабатывания этого алгоритма.

Работу алгоритма RED можно описать следующим образом.

Если средняя длина очереди QueueLength меньше либо равна минимально допустимому значению порога срабатывания MinThreshold алгоритма RED (QueueLength

Если средняя длина очереди QueueLength находится внутри некоторого предопределенного диапазона (MinThreshold < QueueLength < MaxThreshold), то RED начнет уничтожать некоторую часть ячеек. Доля уничтожаемых ячеек определяется значением Pa, рассчитываемым в соответствии с состоянием ресурсов коммутатора. Пересчет вероятности Pa и сам процесс отбрасывания ячеек будут продолжаться до тех пор, пока значение средней длины очереди QueueLength не опустится ниже минимального порога MinThreshold.

Вероятность уничтожения пакетов Pa подсчитывается следующим образом:

Здесь

Pb=Pmax?(QueueLength-MinThreshold)/(MaxThreshold-MinThreshold)?PacketSize/MaxPacketSize, (2)

где Pmax - максимальная вероятность уничтожения ячеек; Count - количество ячеек, помещенных в очередь с момента последнего сброса; PacketSize - длина пакета протокола, инкапсулированного в ATM; MaxPacketSize - максимальная длина пакета, инкапсулированного в ATM.

Если средняя длина очереди QueueLength больше или равна максимально допустимому значению MaxThreshold (QueueLength > MaxThreshold), то поступившая на вход коммутатора ячейка обязательно будет уничтожена.

Как видно из формул (1) и (2), вероятность уничтожения ячеек Pa зависит от размеров инкапсулированных пакетов. Следовательно, большие пакеты (например, при перекачке файлов по протоколу FTP) будут уничтожатся чаще, чем маленькие (например, передаваемые по telnet).

В сетях ATM используются две модификации алгоритма RED: C-RED (Cell-RED) работает с каждой ячейкой, P-RED (Packet-RED) - с группой ячеек, образующих AAL5 PDU.

Алгоритм C-RED учитывает каждую отдельную ячейку и, таким образом, имеет полную картину состояния сети в каждый момент. Недостаток данного алгоритма - сложность его реализации при работе на больших скоростях. В высокоскоростных сетях ATM процедура пересчета средней длины очереди QueueLength при появлении каждой новой ячейки может оказаться достаточно сложной и дорогостоящей, поэтому в них обычно используется P-RED.

Алгоритм P-RED работает с группой ячеек, которые образуют один пакет, инкапсулированный в ATM (например, IP-пакет). Пересчет средней длины очереди осуществляется для всех ячеек пакета только один раз - в момент поступления первой ячейки. P-RED не является таким гибким, как C-RED, но зато вполне может быть реализован на самых высокоскоростных каналах.

Среди недостатков алгоритма RED при работе в сети ATM нужно отметить следующий. RED сбрасывает только одну или несколько ячеек из тех, которые образуют исходный пакет. Передача по сети остальных ячеек (неполного пакета) продолжается, они будут уничтожены только в приемнике на уровне адаптации AAL5. Эту проблему позволяет решить алгоритм Partial Packet Discard PPD, который обеспечивает удаление неполных пакетов.

В алгоритме RED вероятность уничтожения пакета является функцией от его размера - см. формулы (1) и (2). Размеры передаваемых пакетов определяются динамически в процессе передачи через ATM-коммутатор. В AAL5 границы пакета определяются значением поля PTI в заголовке ячейки, помечающего последнюю ячейку пакета. Поскольку определить размер еще не принятого пакета нельзя, его считают равным размеру последнего пакета, принятого по данному виртуальному каналу. Таким образом, удается использовать зависимость вероятности уничтожения ячейки от количества ячеек, образующих исходный пакет AAL5 PDU, т. е. от размера пакета (что не имеет места в алгоритме EPD).

В случае широкого диапазона колебаний нагрузки алгоритм RED может не отреагировать на переполнение буферов, поэтому он обычно применяется совместно с алгоритмом EPD. Последний осуществляет не выборочное уничтожение одной ячейки, а сброс целого пакета, что позволяет резко снизить нагрузку на ATM-коммутатор.

На рисунке представлена структурная схема работы совместно реализованных алгоритмов P-RED и EPD. При появлении ячейки ATM-коммутатор анализирует (используя поле PTI заголовка), является ли она первой ячейкой пакета AAL5 PDU. Если ячейка является началом пакета, ATM-коммутатор пересчитывает среднюю длину очереди QueueLength (как уже было отмечено, в алгоритме P-RED пересчет длины очереди осуществляется только для первой ячейки пакета).

Если длина очереди меньше либо равна минимальному порогу срабатывания алгоритма RED (QueueLength

У читателя может возникнуть законный вопрос: зачем нужно использовать алгоритм RED, подсчитывающий вероятность уничтожения ячеек внутри пакета, если алгоритм PPD, вступающий в работу следом, уничтожает остатки пакета невзирая на любые значения вероятности Pa. Основным достоинством алгоритма RED является возможность подсчета для каждого виртуального соединения вероятности уничтожения ячеек в зависимости от размера пакетов (AAL5 PDU), передаваемых по данному виртуальному соединению. Чем больше пакеты, тем выше вероятность их уничтожения. Это позволяет справедливо распределять полосу пропускания между потоками данных различных пользователей, чего нельзя достичь, используя алгоритмы EPD/PPD самостоятельно, а не совместно с RED.

Наконец, если длина очереди превосходит предельно допустимое значение MaxThreshold (QueueLength>MaxThreshold), то сразу же включается алгоритм EPD, способный достаточно быстро и эффективно снять перегрузку путем одновременного удаления большого числа ячеек.

Эффективное использование пропускной способности существующих сетей TCP/IP и появляющихся сетей ATM является одним из основных вопросов, стоящих перед провайдерами и производителями аппаратуры. В связи с этим настолько велик интерес к различным методам повышения пропускной способности. Алгоритм RED рекомендован к применению в Inernet (см. RFC 2309); к настоящему времени он стал практически стандартной функцией маршрутизаторов TCP/IP и коммутаторов ATM, реализованной в большинстве устройств крупных производителей.