코델
CoDel코델(CoDel, Controlled Delay; "coddle"로 발음됨)은 네트워크 라우팅의 활성 대기열 관리(AQM) 알고리즘으로, 밴 제이콥슨과 캐슬린 니콜스가 개발하여 RFC8289로 출판되었다.[1]라우터 등 네트워킹 하드웨어의 버퍼블로를 이 장비에서 버퍼를 통과할 때 네트워크 패킷 지연 경험에 대한 한계를 설정해 극복하도록 설계됐다.CoDel은 Jacobson이 인지하고 있는 근본적인 오해의 일부를 해결하고 관리하기 쉽도록 함으로써 RED(Random Early Detection) 알고리즘의 전반적인 성능을 향상시키는 것을 목표로 한다.
2012년, CoDel의 구현은 GNU General Public License와 3-clause BSD 라이선스에 따라 Linux 커널 및 이중 라이선스 Dave Tht와 Eric Dumazet에 의해 작성되었다.두마제의 CoDel 개선은 FQ-CoDel이라고 불리며, "Fair/Flow Queue CoDel"을 의미하며, "Barrier Breaker"라는 OpenWrt 릴리스에서 표준 AQM 및 패킷 스케줄링 솔루션으로 처음 채택되었다.거기서부터 CoDel과 FQ-CoDel은 토마토, dd-wrt, OPNsense, 유비쿼티티의 "스마트 큐" 기능과 같은 다양한 다운스트림 프로젝트로 이주했다.
이론
CoDel은 데이터 버퍼의 영향 하에 패킷 교환 네트워크에서 패킷 동작의 관찰을 기반으로 한다.이러한 관측 중 일부는 대기열의 근본적인 특성과 완충제의 원인에 관한 것이며, 다른 일부는 대체 대기열 관리 알고리즘의 약점과 관련이 있다.CoDel은 완충성 문제를 해결하기 위한 시도로 개발되었다.[2]
완충류
패킷의 흐름은 고속 네트워크와 저속 네트워크 사이의 네트워크 링크를 통해 이동하는 동안 느려지는데, 특히 TCP 세션이 시작될 때, 패킷이 갑자기 터지고 느린 네트워크가 버스트를 충분히 빨리 받아들일 수 없을 수 있다.버퍼는 고속 네트워크에 패킷을 저장하여 자체 속도로 느린 네트워크에 의해 읽힐 수 있는 공간을 제공함으로써 이 문제를 완화하기 위해 존재한다.[3]즉, 완충기는 충격 흡수제처럼 작용하여 버스트 도착을 부드럽고 꾸준한 출발로 바꾼다.그러나 버퍼의 용량은 제한적이다.이상적인 버퍼의 크기는 통신의 갑작스런 폭발을 처리할 수 있고, 그 버스트의 속도를 느린 네트워크의 속도에 맞출 수 있도록 한다.이상적으로 충격 흡수 상황은 전송 버스트 동안 버퍼의 패킷이 일시적으로 지연되는 것이 특징이며, 그 후에는 지연이 빠르게 사라지고 패킷 제공과 처리에서 네트워크가 균형에 도달한다.[3]
TCP 정체 제어 알고리즘은 두 통신 장치 사이에 사용 가능한 대역폭을 결정하기 위해 패킷 드롭에 의존한다.패킷이 떨어지기 시작할 때까지 데이터 전송 속도를 높인 뒤 전송 속도를 늦춘다.이상적으로는 링크의 속도로 평형을 찾으면서 속도를 계속 올리고 속도를 늦춘다.이를 위해서는 알고리즘이 적절한 전송 속도를 신속하게 선택할 수 있도록 패킷 감소가 적시에 발생해야 한다.패킷이 지나치게 큰 버퍼에 저장되면 패킷은 목적지에 도착하지만 지연 시간은 더 높지만 패킷이 삭제되지 않아 TCP 속도가 느려지지 않는다.이러한 조건 하에서 TCP는 연결 경로가 변경되었다고 판단하고 새로운 평형을 찾기 위한 검색을 반복할 수도 있다.[4][5]
특히 같은 채널에서 두 개 이상의 동시 전송을 볼 때 전송 지연 증가와 상호 작용성 저하를 유발하는 크고 지속적으로 완전한 버퍼를 갖는 것을 완충재라고 한다.사용 가능한 채널 대역폭은 느린 대상에 대한 전송 대기 데이터로 인해 버퍼 막힘으로 인해 일부 빠른 대상에 도달하지 못할 수 있기 때문에 사용되지 않을 수도 있다.
좋거나 나쁜 대기열
CoDel은 두 가지 유형의 대기열을 구분한다.[3][6]좋은 대기열은 완충력을 보이지 않는 대기열이다.통신 버스트는 대기열 지연을 일시적으로 증가시키는 것에 지나지 않는다.네트워크 링크 활용도를 극대화한다.나쁜 줄에는 완충이 있다.통신 버스트는 버퍼의 충만과 충만 상태를 유지하게 하여 활용도가 낮고 지속적으로 높은 버퍼 지연을 초래한다.버퍼블로에 효과적으로 대응하기 위해서는 AQM(Active Queue Management) 알고리즘 형태의 솔루션이 버퍼블로의 발생을 인지하고 효과적인 대응책을 전개하여 대응할 수 있어야 한다.
Van Jacobson은 2006년에 기존 알고리즘이 버퍼블로를 인식하는 잘못된 수단을 사용해 왔다고 주장했다.[5]RED와 같은 알고리즘은 평균 대기열 길이를 측정하고 평균이 너무 커지면 완충제의 사례로 간주한다.Jacobson은 통신 폭발의 경우 평균 대기열 길이가 급격히 증가하기 때문에 이 측정치가 좋은 측정 기준이 아니라는 것을 2006년에 입증했다.그러면 대기열이 빠르게 소멸되거나(좋은 대기열) 대기열이 될 수 있다(나쁜 대기열).네트워크 트래픽의 다른 요인도 거짓 긍정이나 부정의 원인이 되어 불필요하게 대응책이 전개될 수 있다.Jacobson은 평균 대기열 길이가 실제로 패킷 수요나 네트워크 부하에 대한 정보를 전혀 포함하지 않는다고 제안했다.[3][5]그는 더 나은 측정 기준이 슬라이딩 시간대의 최소 대기열 길이일 수 있다고 제안했다.[3]
알고리즘.
CoDel은 2006년부터 Jacobson의 개념을 바탕으로 실행 중인 버퍼 창에서 패킷이 경험하는 최소 지연을 제어하는 큐를 관리하기 위해 개발되었다.목표는 이 최소 지연 시간을 5밀리초 이하로 유지하는 것이다.최소 지연이 너무 높은 값으로 상승하면 지연이 최대 레벨 아래로 떨어질 때까지 패킷이 대기열에서 삭제된다.[3]Nichols와 Jacobson은 이 미터법 이상을 사용하지 않는 것의 몇 가지 이점을 인용한다.[3]
- CoDel은 매개 변수가 없다.(제이콥슨에 따르면) RED 알고리즘의 약점 중 하나는 특히 동적 링크 비율이 있는 환경에서 구성하기가 너무 어렵다는 것이다.
- CoDel은 좋은 큐와 나쁜 큐를 다르게 취급한다.양호한 대기열은 특성상 지연이 적어 관리 알고리즘이 이를 무시할 수 있는 반면, 불량 대기열은 패킷을 떨어뜨리는 형태의 관리 개입을 받게 된다.
- CoDel은 완전히 로컬로 결정된 매개변수로 작동한다. CoDel은 로컬 버퍼에 의해 제어되거나 예측될 수 없는 왕복 지연, 링크 속도, 트래픽 부하 및 기타 요인과 무관하다.
- 로컬 최소 지연은 패킷이 버퍼에서 나갈 때만 결정할 수 있으므로 대기열을 실행하여 대기열을 관리하기 위한 통계를 수집하는 데 추가 지연이 필요하지 않다.
- CoDel은 이용률에 부정적인 영향을 주지 않으면서 동적으로 변화하는 링크 속도에 적응한다.
- CoDel 구현은 비교적 간단하며 따라서 로우엔드 홈 라우터에서 하이엔드 라우팅 솔루션까지 주파수를 포괄할 수 있다.
CoDel은 버퍼 창의 최소 지연 시간이 허용된 최대값보다 낮을 경우 버퍼를 관리하기 위해 아무것도 하지 않는다.또한 버퍼가 상대적으로 비어 있는 경우에도(버퍼에 MTU의 바이트 값이 1개 미만인 경우) 아무 것도 하지 않는다.[3]이러한 조건이 유지되지 않으면 CoDel은 패킷을 확률적으로 삭제한다.[3]
알고리즘은 각 네트워크 홉에서 독립적으로 계산된다.알고리즘은 처음에는 100밀리초 간격으로 작동한다.홉을 통해 패킷별 대기열 지연을 모니터링한다.각 패킷이 전달을 위해 디큐레이션되면 대기열 지연(패킷이 대기열에서 대기하는 데 소요된 시간)이 계산된다.간격의 가장 낮은 대기열 지연이 저장된다.간격의 마지막 패킷을 디큐레이션할 때 간격의 가장 낮은 대기열 지연이 5밀리초보다 크면 이 단일 패킷이 삭제되고 다음 패킷 그룹에 사용되는 간격이 단축된다.간격의 가장 낮은 대기열 지연이 5밀리초 미만일 경우 패킷이 전달되고 간격은 100밀리초로 재설정된다.
간격이 짧아지면 과도한 대기 지연으로 패킷이 삭제된 연속 간격 수의 역제곱근에 따라 이루어진다.간격 순서는 }}, 3 4 5{\ ...},
시뮬레이션 결과
CoDel은 Nichols와 Jacobson의 시뮬레이션 테스트에서 서로 다른 MTU, 링크 속도 및 기타 조건의 변화에서 테스트되었다.일반적으로 결과는 다음을 나타낸다.[3][7]
- RED와 비교하여, CoDel은 전체 대역폭 범위(3 ~ 100 Mbit/s)에서 패킷 지연을 목표 값에 더 가깝게 유지한다.측정된 링크 활용도는 링크 대역폭의 100%에 지속적으로 근접한다.
- 낮은 MTU에서는 패킷 지연이 높은 MTU보다 적다. MTU가 높을수록 링크 활용도가 높아지고, MTU가 낮을수록 낮은 대역폭에서 좋은 링크 활용도가 제공되며, 높은 대역폭에서 공정한 활용률로 저하된다.
그렉 화이트와 조이 패든이 케이블랩스에서 시뮬레이션도 했다.[8]
실행
CoDel의 완전한 구현은 2012년 5월에 실현되었고 오픈 소스 소프트웨어로 이용 가능하게 되었다.[3]리눅스 커널 내에서 구현되었다(3.5 메인라인부터).[9]Dave Thth는 CeroWrt 프로젝트를 위해 CeroWrt에 CoDel을 Linux 커널 3.3으로 역포팅했는데,[10] 이 커널은 완충재료를 사용하여 CeroWrt를 완전히 테스트했다.CoDel은 2013년부터 일부 독점/턴키 대역폭 관리 플랫폼에 옵션으로 등장하기 시작했다.[11]FreeBSD는 2016년에 CoDel을 11.x와[12] 10.x[13] 코드 지점에 통합했다.[14]OpenB를 사용하여 구현을 배포6.2 버전 이후 SD.[15]
참고 항목
참조
- ^ Nichols, K.; Jacobson, V.; McGregor, A.; Iyengar, J. (Jan 2018). Controlled Delay Active Queue Management. IETF. doi:10.17487/RFC8289. RFC 8289.
- ^ Joe Brockmeier (2012-05-08). "Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution". ReadWriteWeb. Archived from the original on 2012-07-12. Retrieved 2012-08-16.
- ^ a b c d e f g h i j k Nichols, Kathleen; Jacobson, Van (6 May 2012). "Controlling Queue Delay". ACM Queue. ACM Publishing. 55 (7): 42–50. doi:10.1145/2209249.2209264. S2CID 381738. Retrieved 12 August 2012.
- ^ Jacobson, Van; Karels, MJ (1988). "Congestion avoidance and control" (PDF). ACM SIGCOMM Computer Communication Review. 18 (4): 314–329. doi:10.1145/52325.52356. Archived from the original (PDF) on 2004-06-22.
- ^ a b c Jacobson, Van (2006). "A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA" (PDF). Retrieved 12 August 2012.
- ^ Iljitsch van Beijnum (2012-05-10). "CoDel buffer management could solve the Internet's bufferbloat jams". Ars Technica. Retrieved 2012-08-16.
- ^ Nichols, Kathleen (July 2012). "Controlled Delay (CoDel) Active Queue Management". Pollere Inc. Archived from the original on 22 August 2012. Retrieved 12 August 2012.
- ^ Greg White; Joey Padden (November 2012). "Preliminary Study of Codel AGM in a Docsis Network" (PDF). cablelabs.com. Retrieved 2015-06-14.
- ^ Gettys, Jim (22 May 2012). "A Milestone Reached: CoDel is in Linux!". jg's Ramblings. Retrieved 12 August 2012.
- ^ "Cerowrt - Overview". Bufferbloat. Retrieved 2014-01-24.
- ^ "Procera Packetlogic Changelog". proceranetworks.com. Archived from the original on 2013-07-24. Retrieved 2013-07-24.
- ^ truckman (2016-05-26). "Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)".
- ^ truckman (2016-06-10). "MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE)".
- ^ Al Saadi, Rasool; Armitage, Grenville. "Implementing AQM in FreeBSD".
- ^ "OpenBSD 6.2". Retrieved 13 October 2017.