칸 알고리즘
Karn's algorithmKarn의 알고리즘은 컴퓨터 네트워킹에서 TCP(Transmission Control Protocol)를 사용할 때 메시지의 왕복 시간 추정치를 정확하게 얻는 문제를 다룬다. Karn-Partridge 알고리즘이라고도 불리는 이 알고리즘은 1987년 필 칸과 크레이그 파트리지에 의해 논문에서 제안되었다.[2]
TCP의 정확한 왕복 추정치는 재전송된 세그먼트에 의해 생성된 모호성 때문에 계산하기 어려울 수 있다. 라운드 트립 시간은 세그먼트가 전송된 시간과 그 수신확인이 송신자에게 반환된 시간의 차이로 추정되지만 패킷이 재전송될 때 모호한 점이 있다. 즉, 수신확인은 세그먼트의 첫 번째 전송이나 후속 재전송에 대한 응답일 수 있다.
Karn의 알고리즘은 왕복 시간 추정치를 업데이트할 때 재전송된 세그먼트를 무시한다. 왕복 운행 시간 추정은 한 번만 전송된 세그먼트에 대한 승인인 모호하지 않은 승인만 기반으로 한다.
Karn의 알고리즘을 이렇게 단순하게 구현하는 것 또한 문제를 일으킬 수 있다. 지연이 급격히 증가한 후 TCP가 세그먼트를 전송할 때 어떤 일이 발생하는지 고려하십시오. 이전 왕복 시간 추정치를 사용하여 TCP는 시간 초과를 계산하고 세그먼트를 재전송한다. 만약 TCP가 모든 재전송된 패킷의 왕복 시간을 무시한다면, 왕복 예상치는 결코 업데이트되지 않을 것이고, TCP는 증가된 지연에 결코 적응하지 않고 모든 세그먼트를 계속 재전송할 것이다.
이 문제에 대한 해결책은 타이머 백업 전략과 함께 전송 시간 초과를 통합하는 것이다. 타이머 백오프 전략은 초기 타임아웃을 계산한다. 타이머가 만료되어 재전송을 유발하는 경우, TCP는 일반적으로 시간 초과를 2배수로 증가시킨다. 이 알고리즘은 패킷 손실이 높은 네트워크에서 성능과 효율성의 균형을 유지하는 데 매우 효과적이라는 것이 입증되었다.[3][page needed] 이상적으로는 칸의 알고리즘이 필요하지 않을 것이다. 왕복 시간 및 재전송 시간 초과가 많은 네트워크는 근본 원인 분석 기법을 사용하여 조사해야 한다. [4]
참조
- ^ 컴퓨터 네트워크: 시스템 접근 방식, 네트워킹 분야의 Morgan Kaufmann 시리즈, Larry L. Peterson, Bruce S. Davie Edition 5, Exvier, 2011 페이지 418
- ^ Karn, Phil; Partridge, Craig (1987). Improving Round-Trip Time Estimates in Reliable Transport Protocols (PostScript). Proc. ACM SIGCOMM. pp. 2–7.
- ^ Comer, Douglas (2006). Internetworking with TCP/IP (Fifth ed.). Prentice Hall.
- ^ "What Is Karn's Algorithm?". Archived from the original on 2016-11-14. Retrieved 2016-09-07.
