Традиционным и одновременно наиболее простым алгоритмом управления очередями является TailDrop, как правило, реализованный на базе очереди с дисциплиной обслуживания «первый пришел
- первый обслужен» (First Come First Served, далее - FCFS). Сброс поступающего пакета осуществляется только тогда, когда в очереди нет свободных мест. Как только в очереди появляется место
- туда помещается пакет, поступивший первым с момента освобождения места. TailDrop в силу своей простоты обладает рядом существенных недостатков, среди которых необходимо отметить возможность занятия очереди пакетами одного или нескольких потоков (lock-out), т.е. реализация принципа «справедливого распределения ресурсов» невозможна. Также к существенным недостаткам можно отнести и невозможность заблаговременного определения момента перегрузки, т.е. констатация перегрузки возможна только после того, как первый пакет будет потерян вследствие переполнения очереди.
Таким образом, рассматриваемая очередь достаточно долгое время может быть полностью загружена или почти полностью загружена, но источники нагрузки об этом не будут проинформированы. В этом случае поступление пачки пакетов от какого-либо источника TCP, когда источник не извещен о перегрузке или близком к ней состоянии очереди и окно cwnd имеет достаточно большой размер, может привести к потери нескольких пакетов, возможно даже всех посланных. Такая ситуация может привести к «глобальной синхронизации» (global synchronization), т.е. все TCP-источники, передающие данные через маршрутизатор, в котором находится рассматриваемая очередь, в связи с обнаруженной перегрузкой резко и одновременно понизят размер окна cwnd, в результате чего существенно понизится нагрузка на очередь и ресурсы будут простаивать; а потом эти источники опять же одновременно будут повышать нагрузку, что опять приведет к перегрузке. В результате моменты перегрузки будут сменяться моментами низкого использования ресурсов, т.е. средняя пропускная способность соединений TCP будет мала и ресурсы будут использоваться неэффективно.
Наличие буферов в маршрутизаторах должно позволять обрабатывать пачечный трафик. В соответствии с [RFC2309] главной задачей буфера является возможность принимать и обрабатывать пачки пакетов. Можно предположить, что для того, чтобы буфер мог принимать пачку достаточно большого размера, необходимо увеличить его размер. Однако при увеличении размера буфера увеличивается время пребывания пакетов в очереди, а, как известно, протокол TCP по истечении некоторого предопределенного таймера понижает размер окна cwnd и опять посылает те же самые пакеты, предположив, что те пакеты, которые находятся на самом деле в буфере, уже потеряны - возникает перегрузка. Таким образом получается, что размер буфера, с одной стороны, должен быть достаточным для приема пачки пакетов, а с другой стороны, не слишком большим, чтобы обеспечить желаемое качество обслуживания (ограниченный размер задержки).
После обнаружения проблем алгоритма TailDrop и их изучения было разработано несколько алгоритмов, улучшающих функционирование этого алгоритма. Среди них необходимо отметить следующие [Lakshman96]:
• «вероятностный сброс пакета» (random drop on full): при переполнении очереди осуществляется вычисление вероятности, с которой некоторый пакет сбрасывается;
• «сброс начала очереди» (drop front on full): при переполнении очереди осуществляется вычисление вероятности, с которой первый стоящий в очереди на обслуживание пакет сбрасывается.
Обе стратегии позволяют избежать проблемы захвата очереди пакетами одного или нескольких потоков, однако проблема отсутствия возможности заблаговременного обнаружения перегрузки остается. Отметим, что при определенных условиях эти алгоритмы могут конкурировать с более сложными алгоритмами активного управления очередями, представленными ниже.
⇐Алгоритмы управления очередями | Управление трафиком и качество обслужевания в сети | Алгоритмы активного управления очередями⇒