Алгоритмы обнаружения потери пакетов
TCP использует повторную передачу для потерянных пакетов во время любой передачи, но как происходит потеря пакетов и как TCP может ее обнаружить. В этой статье мы собираемся обсудить алгоритмы обнаружения потери пакетов.
Когда происходит потеря пакетов?
Потеря пакетов происходит по следующим причинам:
- Когда буфер получателя заполнен, но отправитель отправляет пакеты в большом количестве.
- Когда буфер промежуточных устройств, т.е. маршрутизатор, заполнен, и отправитель отправляет пакеты.
Первый случай связан с управлением потоком, и получатель объявляет размер своего буфера отправителю, чтобы никогда не сталкиваться с такой ситуацией. Второй случай связан с управлением перегрузкой, и отправитель должен использовать комбинацию медленного старта и AIMD, чтобы избежать этой ситуации.
Алгоритмы обнаружения потери пакетов:
Ядро Linux использует три алгоритма обнаружения потери пакетов. Вот они:
- RTO (время повторной передачи)
- FR (быстрая повторная передача)
- RACK (недавнее подтверждение)
Эти алгоритмы обнаруживают потерю пакетов, и отправитель снижает скорость передачи пакетов получателю.
Алгоритм RTO:
Первоначально он был предложен Ван Якобсоном в «Избежании и контроле заторов» в 1988 году.
Когда отправитель отправляет пакет в полет, он запускает таймер, который является функцией RTT. Этот таймер работает в течение периода времени RTO и ожидает подтверждения. Если ACK не приходит в течение периода RTO, считается, что соответствующий пакет отброшен. RTO — это функция времени приема-передачи (RTT). Он рассчитывается либо для каждого пакета, либо для каждого окна перегрузки (cwnd). Когда таймер RTO истекает до прихода ACK, отправитель делает вывод, что сеть перегружена, повторно передает потерянный пакет и увеличивает время ожидания (RTO) в 2 раза. Это называется методом бинарной экспоненциальной отсрочки. Это делается для того, чтобы позволить сети выйти из перегруженного состояния, дать ей дышать.
Some important variables used in the computation of RTO SRTT -> Smoothed RTT RTTVar -> RTT Variation RTO -> Retransmission TimeOut R -> Current RTT measured When the first RTT measurement (R) is made, the host must set: SRTT = R RTTVar = R ÷ 2 RTO = SRTT + (K x RTTVar), where K = 4 as proposed by Van Jacobson in 1988 When a subsequent RTT measurement (R) is made, the host must set: RTTVar = (1 - β) x RTTVar + β x |SRTT - R|, where β = 1/4 SRTT = (1 - α) x SRTT + α x R, where α = 1/8 RTO = SRTT + (K x RTTVar), where K = 4
Всякий раз, когда рассчитывается RTO, если оно меньше 1 секунды, тогда RTO следует округлить до 1 секунды. Максимальное значение может быть указано для RTO при условии, что оно составляет не менее 60 секунд. Когда таймер повторной передачи истекает (т. е. ACK не получен); отправитель повторно передает потерянный пакет и RTO = RTO x 2. Максимальное значение RTO должно составлять 60 секунд.
Алгоритм быстрой повторной передачи:
Повторно передает отброшенный пакет, не дожидаясь истечения времени таймера RTO. Если получены «три» повторяющихся ACK, отправитель повторно передает потерянный пакет. Вместо того, чтобы ждать в течение периода времени RTO, отправитель просто ждет, пока не получит три дубликата ACK. Это называется быстрой повторной передачей, потому что 3 дубликата ACK занимают меньше времени, чем RTO. Теперь, почему он не выполняет повторную передачу после получения «одного» или «двух» дубликатов ACK? Поскольку пакет, который кажется отброшенным, может быть на самом деле «задержан», и не рекомендуется проявлять нетерпение и преждевременно повторно передавать пакет. Теперь, почему он не ждет более трех дублирующих ACK для повторной передачи отброшенного пакета? Потому что, если он будет ждать дольше, таймер RTO может истечь. Основная цель быстрой повторной передачи — избежать ожидания истечения срока действия RTO.
Duplicate ACK:
Sender send 6 packets to the receiver at a time. Suppose sender received the ACKs of packet 1 and 2.
Packet 3 is lost due to network congestion. Receiver received packet 4, 5 and 6.
When packet 4 is received at receiver, it sends the ACK of packet 2 but not for packet 4. ACK for packet 2 is already received. This is called Duplicate ACK.
TCP receiver always acknowledges the packets it has received in order. So, when 1-2-4-5-6 sequence goes out of order, receiver will send ACK for packet 2 only when it receives packet 4-5-6. It says that it has received till packet 2 in order. It will keep on sending duplicate ACKs until it gets all the packets in order.
After 3 duplicate ACKs for 4-5-6 packets, sender retransmits the packet 3. Receiver now gets all packets from 3-6 inorder and will send the ACK-6 which says that it has received till packet 6 inorder. This is called cumulative ACK.
Ограничения ФР:
Быстрая повторная передача — это эвристика, которая «иногда» запускает повторную передачу отброшенного пакета раньше, чем обычный механизм RTO. Механизм быстрой повторной передачи не заменяет обычные тайм-ауты; это просто увеличивает эту возможность. Например: если пакеты отбрасываются в «хвосте» TCP-соединения, механизм быстрой повторной передачи не может помочь, поскольку для этого требуется как минимум три дублирующих ACK.
Недавний алгоритм подтверждения:
Новый механизм под названием Tail Loss Probe (TLP) решает проблему потери пакетов в конце соединения TCP. Кроме того, Google представила новый метод обнаружения потери пакетов, который называется Recent Acknowledgments (RACK).
Следовательно, текущие методы обнаружения потери пакетов работают вместе, как RACK → Fast Retransmit → RTO.
Ядро Linux использует все 3 алгоритма обнаружения потерь. RACK используется первым; когда это не помогает, вступает в действие Fast Retransmit; когда оба выходят из строя, на помощь приходит RTO.