Случайное раннее обнаружение

Разделение процессора

Справедливая организация очередей

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

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

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

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

Этот недостаток можно преодолеть с помощью схемы справедливой организа­ции очередей с побитовым циклом (Bit-Round Fair Queuing, BRFQ), в которой при планировании пакетов учитываются не только идентификаторы пакетов, но и дли­на пакетов.

Чтобы понять, как работает метод справедливой организации очередей с по­битовым циклом, рассмотрим сначала идеальную политику, которая на практике не применяется. Сформируем несколько очередей, как в схеме справедливой орга­низации очередей, но будем передавать в каждом цикле не целый пакет, а всего один бит. Таким образом, более длинные пакеты не получат преимущества, и каж­дому источнику будет предоставлена равная пропускная способность.

В частно­сти, если имеются N очередей и в каждой из этих очередей всегда есть пакет для передачи, тогда каждая очередь получает ровно 1/N доступной пропускной спо­собности.

Такой идеальный побитовый подход известен также как разделение процессо­ра (Processor Sharing, PS).

Чтобы дальнейшее обсуждение было понятнее, введем следующие обозначения:

§ R(t) — количество циклов обслуживания с разделением процессора, кото­рые произошли к моменту времени t, нормализованное относительно выход­ной скорости передачи данных;

§ N(t) — количество непустых очередей в момент времени t;

§ Р^α_i — время передачи для пакета i в очереди α, приведенное к выходной ско­рости передачи данных;

§ τ^α_i — время прибытия пакета i в очередь α;

§ S^α_i — значение R(t) в момент начала передачи пакета i в очереди α;

§ F^α_i — значение R{t) в момент завершения передачи пакета i в очереди α.

 

Значение R(t) можно рассматривать как виртуальное время, соответствующее скорости обслуживания пакета, находящегося в начале очереди. Эквивалентное определение выглядит следующим образом:

Для примера рассмотрим три очереди, трафик которых описывается таблицей:

Таблица. Трафик трех очередей, обслуживаемый по схеме PS

	Очередь α	Очередь β	Очередь γ
Пакет 1	Пакет 2	Пакет 1	Пакет 2	Пакет 1
Реальное время прибытия τi
Время передачи Рi
Виртуальное время начала Si
Виртуальное время конца Fi

Значения τ_i, и Р_i, задаются; значения S_i, и F_i определяются политикой разделения процессора. На рисунке черные линии иллюстрируют обслуживание трех очередей. Первый прибывший в очередь α пакет получает одну единицу обслужи­вания в реальном интервале времени [0, 1] с виртуальным временем R(l) = 1 к кон­цу этого интервала.

В реальном интервале времени [1,3] биты передаются из двух очередей, в результате чего каждая очередь получает скорость обслуживания R'= 1/2 и виртуальное время растягивается в 2 раза. Аналогично, в течение интервала времени [3, 9] все три очереди сохраняют активность, поэтому каждая получает обслуживание со скоростью R'= 1/3 и виртуальное время растягивается в 2 раза.

Следующее рекуррентное соотношение показывает, как система разделения процессора развивается в виртуальном времени: это виртуальные времена завершения передачи пакета и начала передачи.

 

По этим соотношениям мы можем сосчитать вир­туальное время окончания передачи пакета в момент прибытия пакета. Однако мы не можем вычислить реальное время окончания передачи пакета в момент его при­бытия, потому оно зависит от прибы­тия других пакетов.

 

Другой подход к борьбе с перегрузкой в объединенных сетях представляет собой упреждающее отбрасывание пакетов, т.е. маршрутизатор отбрасывает один или несколько входящих пакетов прежде, чем переполнится выходной буфер. Упреждающее отбрасывание пакетов может быть реализова­но в одной или нескольких очередях.

 

Наиболее важный вариант схемы упреждающего отбрасывания пакетов называется случайное раннее обнаружение (Random Early Detection, RED). Сначала обсудим причины для применения схемы RED и цели ее разработки, после чего перейдем к деталям.