Алгоритм дырявого ведра

Представьте себе ведро с маленькой дырочкой в днище, как показано на рис. 5.28, а. Независимо от скорости, с которой вода наливается в ведро, выходной поток об­ладает постоянной скоростью, когда в ведре есть вода, и нулевой скоростью, ко­гда ведро пустое. Кроме того, когда ведро наполняется, вся лишняя вода вылива­ется через край и теряется (то есть не попадает в выходной поток под дырочкой).

Та же самая идея применима к пакетам, как показано на рис. 5.28, 6. Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро, то есть конечную внутреннюю очередь. Если пакет появляется в очереди, когда очередь полная, пакет игнорируется. Другими словами, если несколько процессов хоста пытаются послать пакеты, когда в очереди уже стоит макси­мально допустимое число пакетов, новый пакет игнорируется. Такой интерфейс может быть реализован как аппаратно, так и программно операционной системой хоста. Он был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра. По сути это не что иное, как однолинейная система массового обслуживания с постоянным временем обслуживания.

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

Когда размер всех пакетов одинаков (например, в ячейках ATM), этот алго­ритм может применяться, как описано ранее. Однако при использовании паке­тов переменного размера часто бывает лучше ограничивать количество байтов, переданных в сеть за такт, нежели передавать один пакет за такт. Так, если пра­вилом установлена передача 1024 байт за тактовый интервал, то за этот период могут быть переданы в сеть либо один пакет размером 1024 байта, либо два паке­та по 512 байт, либо четыре пакета по 256 байт и т. д. Если оставшееся количест­во байт меньше размера следующего пакета, следующий пакет должен ждать на­чала следующего такта.

Реализация исходного алгоритма дырявого ведра проста. Дырявое ведро со­стоит из конечной очереди. Когда прибывает пакет и в очереди есть место, пакет добавляется к очереди, в противном случае пакет игнорируется. Если очередь не пуста, то в течение каждого тактового интервала в сеть передается по одному па­кету.

Алгоритм дырявого ведра со счетчиком байтов реализуется почти также. В каж­дом тактовом интервале значение счетчика устанавливается равным п. Если раз­мер первого пакета в очереди меньше текущего значения счетчика, он передает­ся, а значение счетчика уменьшается на его размер. Если значение счетчика еще достаточно велико, могут быть посланы и другие пакеты. Когда значение счетчи­ка становится меньше размера следующего пакета в очереди, передача прекраща­ется до следующего такта, после чего все начинается сначала, а остаток счетчика обнуляется.

В качестве примера представьте, что компьютер может производить данные со скоростью 25 млн байт в секунду (200 Мбит/с) и что сеть также работает на этой скорости. Однако маршрутизаторы могут поддерживать эту скорость пере­дачи данных лишь на коротких интервалах (пока не заполнится их буферная па­мять). В течение больших интервалов времени они могут обеспечить не более 2 млн байт в секунду. Теперь предположим, что данные поступают пачками по 1 млн байт, одна пачка продолжительностью 40 мс в каждую секунду. Чтобы уменьшить среднюю скорость до 2 Мбайт/с, можно воспользоваться алгоритмом дырявого ведра с выходной скоростью р = 2 Мбайт/с и емкостью С = 1 Мбайт. Это означает, что пачки до 1 Мбайта могут обрабатываться без потерь и что та­кие пачки будут передаваться в сеть за 500 мс независимо от того, как быстро они приходят.

На рис. 5.29, а показан вход дырявого ведра, на который со скоростью 25 Мбайт/с поступает пачка в течение 40 мс. На рис. 5.29, б показан выход, через который данные проходят с постоянной скоростью 2 Мбайт/с в течение 500 мс.