Tail Drop и Head Drop

Tail Drop — наиболее простой механизм управления очередью — отбрасываем все вновь пришедшие пакеты, не помещающиеся в буфер.
Head Drop отбрасывает пакеты, которые стоят в очереди уже очень долго. Их уже лучше выбросить, чем пытаться спасти, потому что они, скорее всего, бесполезны. Зато у более актуальных пакетов, пришедших в конец очереди, будет больше шансов прийти вовремя. Плюс к этому Head Drop позволит не загружать сеть ненужными пакетами. Естественным образом самыми старыми пакетами оказываются те, что в самой голове очереди, откуда и название подхода.
У Head Drop есть и ещё одно неочевидное преимущество — если пакет отбросить в начале очереди, то получатель быстрее узнает о перегрузке на сети и сообщит отправителю. В случае Tail Drop информация об отброшенном пакете дойдёт, возможно, на сотни миллисекунд позже — пока будет добираться с хвоста очереди до её головы. Оба механизма работают с дифференциацией по очередям. То есть на самом деле не обязательно, чтобы весь буфер переполнился. Если 2-ая очередь пустая, а нулевая под завязку, то отбрасываться буду только пакеты из нулевой.
Tail Drop и Head Drop могут работать одновременно.
Tail и Head Drop — это Congestion Avoidance «в лоб». Даже можно сказать — это его отсутствие.
Ничего не предпринимаем, пока очередь не заполнится на 100%. А после этого все вновь прибывшие (или надолго задержавшиеся) пакеты начинаем отбрасывать.
Если для достижения цели не нужно ничего делать, значит где-то есть нюанс.
И этот нюанс — TCP. Вспомним (поглубже и экстремально глубоко), как работает TCP — речь про современные реализации. Есть Скользящее окно(Sliding Window или rwnd — Reciever's Advertised Window), которым управляет получатель, сообщая отправителю, сколько можно посылать. А есть окно перегрузки (CWND — Congestion Window), которое реагирует на проблемы в сети и управляется отправителем.
Процесс передачи данных начинается с медленного старта (Slow Start) с экспоненциальным ростом CWND. С каждым подтверждённым сегментом к CWND прибавляется 1 размер MSS, то есть фактически оно удваивается за время, равное RTT (туда данные, обратно ACK) (Речь про Reno/NewReno).
Например,
Экспоненциальный рост продолжается до значения, называемого ssthreshold (Slow Start Threshold), которое указывается в конфигурации TCP на хосте.
Далее начинается линейный рост по 1/CWND на каждый подтверждённый сегмент до тех пор, пока либо не упрётся в RWND, либо не начнутся потери (о потерях свидетельсв повторное подтверждение (Duplicated ACK) или вообще отсутствие подтверждения). Как только зафиксирована потеря сегмента, происходит TCP Backoff — TCP резко уменьшает окно, фактически снижая скорость отправки, — и запускается механизм Fast Recovery:
  1. 1.
    отправляются потерянные сегменты (Fast Retransmission),
  2. 2.
    окно скукоживается в два раза,
  3. 3.
    значение ssthreshold тоже становится равным половине достигнутого окна,
  4. 4.
    снова начинается линейный рост до первой потери,
  5. 5.
    Повторить.
Потеря может означать либо полный развал какого-то сегмента сети и тогда считай, что пропало, либо перегрузку на линии (читай переполнение буфера и отбрасывание сегмента данной сессии).
Таков у TCP метод максимальной утилизации доступной полосы и борьбы с перегрузками. И он достаточно эффективен.
Однако к чему приводит Tail Drop?
  1. 1.
    Допустим через маршрутизатор лежит путь тысячи TCP-сессий. В какой-то момент трафик сессий достиг 1,1 Гб/с, скорость выходного интерфейса — 1Гб/с.
  2. 2.
    Трафик приходит быстрее, чем отправляется, буферы заполняются всклянь.
  3. 3.
    Включается Tail Drop, пока диспетчер не выгребет из очереди немного пакетов.
  4. 4.
    Одновременно десятки или сотни сессий фиксируют потери и уходят в Fast Recovery (а то и в Slow Start).
  5. 5.
    Объём трафика резко падает, буферы прочищаются, Tail Drop выключается.
  6. 6.
    Окна затронутых TCP-сессий начинают расти, и вместе с ними скорость поступления трафика на узкое место.
  7. 7.
    Буферы переполняются.
  8. 8.
    Fast Recovery/Slow Start.
  9. 9.
    Повторить.
    Подробнее об изменениях в механизмах TCP в RFC 2001 (TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms). Это характерная иллюстрация ситуации, называемой глобальной синхронизацией TCP (Global TCP Synchronization):
Глобальная — потому что страдают много сессий, установленных через этот узел. Синхронизация, потому что страдают они одновременно. И ситуация будет повторяться до тех пор, пока имеет место перегрузка. TCP — потому что UDP, не имеющий механизмов контроля перегрузки, ей не подвержен.
Ничего плохого в этой ситуации не было бы, если бы она не вызывала неоптимальное использование полосы — промежутки между зубцами пилы — потраченные зря деньги. Вторая проблема — это TCP Starvation — истощение TCP. В то время, как TCP сбавляет свою скорость для снижения нагрузки (не будем лукавить — в первую очередь, чтобы наверняка передать свои данные), UDP эти все моральные страдания вообще по датаграмме — шлёт сколько может.
Итак, количество трафика TCP снижается, а UDP растёт (возможно), следующий цикл Потеря — Fast Recovery случается на более низком пороге. UDP занимает освободившееся место. Общее количество TCP-трафика падает.
Чем решать проблему, лучше её избежать. Давайте попробуем снизить нагрузку до того, как она заполнит очередь, воспользовавшись Fast Recovery/Slow Start, который только что был против нас.