Алгоритм Карна
Алгоритм Карна направлен на определение точной оценки времени круговой задержки сообщений при использовании протокола управления передачей TCP в компьютерных сетях. Алгоритм был предложен Филом Карном в 1987 году.[1]
Точная оценка времени круговой задержки в TCP может быть сложно вычислимо из-за неопределённости, создаваемой повторно отправляемыми сегментами. Время круговой задержки определяется как разница между временем отсылки сегмента и временем получения подтверждения. Но после того, когда пакеты были отправлены повторно, создается неопределённость. Подтверждение может прийти как от первой передачи, так и последующих повторных передач.
Алгоритм Карна игнорирует повторные передачи при вычислении времени круговой задержки. Вычисление круговой задержки основывается только на известных фактах подтверждения, т.е. принятых всего один раз.
Но простота реализации этого алгоритма может привести к ещё одной проблеме. Представьте, что произойдёт, если TCP отправит пакеты после резкого увеличения задержки. TCP вычисляет интервал времени передачи и пересылает пакет. Если TCP игнорирует время круговой задержки всех пакетов, отправленных повторно, оценка времени круговой задержки никогда не произойдёт и TCP будет повторно отправлять все пакеты никогда не подстраиваясь под увеличенную задержку.
Решение проблемы заключается в объединении интервалов времени передачи со стратегией таймера отсрочки. Стратегия таймера отсрочки вычисляет начальный интервал ожидания. Если время таймера заканчивается и вызывает повторную потправку, TCP увеличивает время таймера в два раза. Этот алгоритм показал свою высокую эффективность в уравновешивании производительности и эффективности сети в условиях большого количества потерь пакетов.[2] В идеальном случае в алгоритме Карна не будет необходимости. Сети с высоким временем круговой задержки и временем повторной отправки должны быть исследованы с использованием методов анализа корневых причин.[3]
Примечания[править | править код]
- ↑ Karn, Phil; Partridge, Craig (1987). Improving Round-Trip Time Estimates in Reliable Transport Protocols (PostScript). Proc. ACM SIGCOMM. pp. 2—7. Архивировано 3 марта 2016. Дата обращения: 18 января 2017. Источник. Дата обращения: 18 января 2017. Архивировано 3 марта 2016 года.
- ↑ Comer, Douglas Internetworking with TCP/IP (англ.). — Fifth. — Prentice Hall, 2006.
- ↑ Chris Abella. What Is Karn's Algorithm? Optimizing TCP with an often overlooked algorithm for improving round-trip time estimation (англ.). ExtraHop (7 сентября 2016). Дата обращения: 18 января 2017. Архивировано из оригинала 14 ноября 2016 года.