요약

  • 고전 라운드 로빈은 전송 기회를 균등화할 뿐, 전송되는 바이트를 균등화하지는 않습니다. DRR은 각 큐에 퀀텀을 부여하고 패킷 전체 크기를 차감하며, 계속 활성 상태인 큐가 다음 패킷을 처리할 수 없을 때 잔액을 보관합니다.
  • 달성되는 공정성은 큐 사이, 그리고 구성된 가중치 사이의 장기 처리량에 관한 것입니다. 기본 DRR은 패킷 지연을 상한하지 않고, 사용자를 분류하지 않으며, 도착을 조절하지 않고, AQM도 혼잡 제어도 아닙니다.

같은 두 바퀴, 서로 다른 두 서비스

라운드 로빈이 안심시키는 이유는 절차가 눈에 보이기 때문입니다. 활성 큐 목록, 앞으로 전진하는 포인터, 단계마다 하나씩 처리되는 패킷: 어떤 큐도 스케줄러를 독점할 수 없어 보입니다. 이 구조는 빠른 경로에서도 매력적입니다. 복잡한 전역 순서 안에서 다음 패킷을 계속 찾을 필요가 없기 때문입니다.

그러나 패킷 크기가 같지 않아지는 순간 대칭은 깨집니다. 큐 A가 늘 1,500바이트를 내놓고 큐 B가 500바이트를 내놓는다면, A-B 교대는 각 큐에 패킷 하나씩을 분배하지만 A에는 세 바이트, B에는 한 바이트를 줍니다. 장치는 껍데기를 세고 링크는 비트를 소모합니다.

바로 이 간극을 M. Shreedhar와 George Varghese가 1994년 보고서, 그리고 SIGCOMM 이후 발표된 논문에서 분리해냈습니다. 이상적 fair queuing에 가까운 변형들은 더 비싼 처리 비용을 치르고 좋은 정밀도를 제공했고, 단순한 순환 방식은 빠르지만 크기가 달라지면 불공정해질 수 있었습니다. 두 사람의 질문은 순환을 없애는 것이 아니라, 그에게 올바른 단위로 표현된 기억을 부여하는 것이었습니다.

사라지지 않는 잔액

각 DRR 큐는 퀀텀Q_i를 받고 디피시트 카운터DC_i를 갖습니다. 활성 큐가 방문될 때 퀀텀이 카운터에 더해집니다. 머리 패킷은 크기가 가용 크레딧 안에 들어오면 나갈 수 있고, 길이만큼 차감한 뒤 새 패킷이 또 들어오는 한 연산을 계속합니다.

다음 패킷이 너무 크면 분할되지도 않고 그냥 내보내지지도 않습니다. 큐에 계속 데이터가 쌓여 있다면 잔액은 그 큐에 붙어 남습니다. 다음 라운드에서 새 퀀텀이 그 위에 더해집니다. 따라서 퀀텀이 1,000바이트일 때 1,500바이트 패킷은 한 라운드를 기다려 2,000을 쌓고, 온전히 나간 뒤 500 단위를 남깁니다.

‘디피시트(적자)’라는 말은 가끔 도덕적으로 읽히곤 합니다. 그러나 이 카운터는 고객이 입은 손실도, 네트워크의 계약적 채무도 기록하지 않습니다. 이는 내부 회계 상태, 즉 이 규율의 틀 안에서 해당 큐가 소비하지 못한 서비스입니다. 큐가 비면 카운터는 0으로 돌아갑니다. 따라서 오래 잠자던 출처가 크레딧을 무한히 쌓아 두었다가 미래의 버스트를 청구할 수는 없습니다.

퀀텀은 가중치에 대한 결정이다

퀀텀이 같으면 계속 차 있는 큐들은 장기적으로 동등한 몫을 지향합니다. 퀀텀이 다르면 가중치를 표현합니다. 그 비율이 상대적 몫을 조직하되, 패킷 단위의 세분성과 활성 큐의 구성이 그 한계를 만듭니다.

Shreedhar와 Varghese의 분석은 서비스를 ‘기회 수 × 퀀텀’ 주위로 한정하며, 오차는 최대 패킷 크기와 연관됩니다. 이 정식화는 막연한 완벽의 약속보다 훨씬 의미가 있습니다. 짧은 구간에서는 패킷의 불가분성 때문에 어느 큐가 앞설 수 있습니다. 보관된 카운터는 이후 통과마다 이력을 지우지 않고 보상할 수 있게 해 줍니다.

계산의 절약도 이 단순함에서 나옵니다. 활성 목록 하나, 순환 이동 하나, 덧셈, 비교, 뺄셈. 알고리즘은 모든 큐를 가상 타임스탬프 순서로 정렬할 필요가 없습니다. 원 논문은 자신의 퀀텀 및 최대 크기 가정 안에서, 패킷당 O(1) 작업으로 거의 완벽한 처리량 공정성과 하드웨어에 적합한 구조를 주장합니다.

O(1)은 모든 ASIC, 모든 큐 계층, 모든 분류 기능이 정확히 같은 사이클 수를 소모한다는 뜻이 아닙니다. 그것은 스케줄링 연산 비용이 성장하는 방식을 기술합니다. 마찬가지로 공정성 상한은 온전한 패킷을 나눌 수 있는 유체로 바꾸지 않습니다.

공정성은 분류기에서 시작된다

DRR은 제시되는 큐들 사이에서 서비스를 분배합니다. 한 큐는 하나의 플로우가 될 수도, 해시된 플로우 묶음, 구독자, 트래픽 클래스, 자식 스케줄러가 될 수도 있습니다. 열 개 애플리케이션이 한 큐를 공유하고 열한 번째 애플리케이션에 전용 큐가 있다면, DRR은 두 큐 사이를 중재할 뿐 그 안에 숨은 열 개의 신원은 보지 못합니다.

따라서 ‘플로우 사이의 공정함’이라는 말은 사전 결정을 전제합니다. 어떤 키가 플로우를 정의하는지, 큐가 몇 개 존재하는지, 충돌이 어디로 가는지, 각 클래스에 어떤 퀀텀이 배정되는지. 결함 있는 분류기는 수학적으로 올바른 규율을 사회적으로 터무니없게 만들 수 있습니다. 산술은 가중치를 존중할 줄 알지만, 누가 그 가중치를 받을 자격이 있는지는 정하지 못합니다.

크기 분포도 영수증의 일부입니다. 1,500/500 예제는 메커니즘을 보여줄 뿐, Cisco 라우터나 인터넷 백본 어딘가에서 찍은 측정이 아닙니다. 실제 패킷은 다양합니다. 카운터를 해석하려면 최대 크기, 관측된 혼합, 부하 기간, 활성 목록의 구성을 알아야 합니다.

처리량은 도착 시각을 알려주지 않는다

원 논문은 처리량 공정성과 지연을 명시적으로 구분합니다. 기본 DRR은 전자를 제공하되 후자에 대한 상한은 없으며, 이후 저자들은 확장을 검토합니다. 한 큐가 긴 기간에 걸쳐 자기 몫을 받는 동안, 한 패킷은 다른 여러 활성 큐들이 지나가기를 기다릴 수 있습니다. 큐 수, 퀀텀, 패킷 크기, 계층 구조가 이 지연을 결정합니다.

DRR은 또한 그 패킷이 들어왔어야 했는지를 결정하지 않습니다. 어드미션은 부하를 수용하거나 거부하고, 셰이핑은 속도를 조절하고, AQM은 포화 전에 표시하거나 폐기하며, 혼잡 제어는 송신자의 행동을 바꿉니다. RFC 7567은 DRR을 포함한 fair queuing 스케줄러를 언급하면서도 이를 AQM의 역할과 분리합니다.

이 메커니즘들은 결합될 수 있습니다. 그러나 혼동하면 측정의 가치가 사라집니다. 낮은 카운터가 혼잡 부재를 증명하지 않습니다. 높은 디피시트는 사용자에 대한 부채가 아닙니다. 좋은 바이트 몫이 낮은 애플리케이션 지연을 확립하지 않고, 큐에서 빠져나간 패킷은 아직 종단 간에 도착하지 않았습니다.

빠른 경로 역사 속의 Varghese

UCLA Samueli는 George Varghese를 Distinguished Professor of Computer Science이자 Jonathan B. Postel Chair in Networking 보유자로 소개합니다. 그의 분야에는 네트워크 알고리듬(network algorithmics)과 네트워크 검증이 있습니다. 병목을 찾아내고, 알고리듬과 하드웨어, 구현 제약을 서로 대화하게 하는 일입니다. 그는 Microsoft Research와 UC San Diego, Washington University in St. Louis에서의 교직을 거쳐 2016년 UCLA에 합류했습니다.

ACM SIGCOMM은 2014년, 연구와 산업에 깊은 영향을 미친 네트워크 알고리듬에 대한 지속적 기여로 그를 표창했습니다. 2021년에 그를 영입한 Internet Hall of Fame은 DRR과 그 역사적 용례인 Cisco Gigabit Switch Router를 언급합니다.

그러나 이런 인정이 단독 서사를 허락하지는 않습니다. 기념비적 저작에는 M. Shreedhar와 George Varghese 두 이름이 함께 있습니다. Varghese의 프로필은 하나의 방법론을 드러냅니다. 빠른 구조를 유지하고, 실제로 희소한 단위를 찾아내고, 편차를 바로잡는 최소한의 상태를 더하는 것. 그러나 그 방법론은 Shreedhar의 공동 저작권을 빼앗지 않습니다.

계약을 발명하지 않고 카운터 읽기

퀀텀, 패킷 길이, dequeue 이력을 앞에 두면 카운터는 어느 큐가 전송할 수 있었고 어느 큐가 기다려야 했는지를 설명합니다. 분류기가 그 연결을 제공하지 않는 한, 카운터는 고객을 식별하지 않습니다. 하류의 혼잡도, 전체 경로도, 애플리케이션 결과도 보지 못합니다.

유용한 감사는 활성 큐 구성, 퀀텀, 점유, 머리 패킷, 이월된 디피시트, 전송된 바이트를 함께 보존합니다. 폐기, ECN 표시, 셰이핑 상태, 분류기 변경은 각자의 계열에 남겨집니다. 처리량 몫은 맞는데 대기 지연이 늘어난다면, 두 측정은 모순이 아닙니다. 서로 다른 질문에 답할 뿐입니다.

역사적 교훈은 계산 단위에 담겨 있습니다. 대칭 포인터만으로는 공정이 만들어지지 않습니다. 자원이 무엇을 소모하는지, 스케줄러가 어떤 이력을 보관하는지, 각 카운터 뒤에 어떤 집단이 묶여 있는지를 알아야 합니다. DRR은 순환에 바이트를 세도록 가르쳤을 뿐, 큐 안에 누가 숨어 있는지를 대신 판단하지 않았습니다.

출처