기술 요약: 확장 가능한 결정적 네트워킹을 위한 비작업 보존형 무상태 코어 공정 큐잉 스케줄러

문제 정의

결정적 네트워킹(Deterministic Networking, DetNet)은 대규모 네트워크에서 참여하는 플로우(flow)들에 대해 엄격한 종단 간(E2E) 지연 시간 및 지터(jitter) 경계치를 보장하는 것을 목표로 한다. 결정적 성능은 낮은 전파 지연을 가진 소규모 네트워크에서는 달성 가능하지만, 이를 대규모 네트워크로 확장하는 데는 상당한 어려움이 따른다. 기존 방식들은 다음과 같은 구체적인 한계에 직면해 있다:

• 상태 유지형 공정 큐잉 (예: PGPS, WFQ): 이 방식들은 최적의 플로우 격리 및 지연 시간 경계치를 제공하지만, 모든 노드에서 각 플로우의 상태 정보(특히 이전 패킷의 종료 시간)를 유지해야 한다. 수백만 개의 플로우를 처리하는 코어 노드에서 이러한 상태 관리의 복잡도($O(N)$)는 라인 레이트(line-rate) 처리를 불가능하게 만든다.
• 작업 보존형 무상태 스케줄링 (예: C-SCORE): 확장성을 해결하기 위해 IETF DetNet 작업 그룹과 ITU-T는 C-SCORE를 표준화하고 있다. 이 기술은 플로우 상태를 패킷 헤더 내의 메타데이터(종료 시간, FT)로 전달하여 코어 노드가 플로우 상태를 유지할 필요가 없도록 한다. 그러나 C-SCORE는 작업 보존형(work-conserving) 방식(링크가 유휴 상태일 때 즉시 패킷을 전송함)이기 때문에, 결정적인 지터 보장을 제공하지 못한다. 지터는 E2E 지연 시간 경계치만큼 넓게 변동될 수 있다.
• 대안 메커니즘 (TSN, CJVC): IEEE 802.1 TSN의 시간 인식 셰이핑(Time-Aware Shaping, TAS) 및 주기적 큐잉 및 포워딩(Cyclic Queuing and Forwarding, CQF)은 지터 제어를 제공하지만, NP-난해(NP-hard) 스케줄링, 엄격한 동기화 요구 사항 또는 주기 시간 제한과 같은 확장성 문제를 겪는다. Core-Stateless Virtual Clock(CJVC)은 지터를 줄이려고 시도하지만, 과도한 메타데이터와 복잡한 계산(예: 전송 전 서비스 완료 시간 예측)을 필요로 하여 실시간 처리에 부담을 준다.

방법론

저자들은 결정적 지터를 제공하면서도 확장성을 희생하지 않도록 설계된 C-SCORE 프레임워크의 진화형인 N-SCORE(Non-work conserving Stateless Core fair queuing)를 제안한다.

핵심 알고리즘

N-SCORE는 플로우 상태를 패킷 메타데이터로 전달하는 C-SCORE의 무상태 특성을 유지하면서, 적격 시간(Eligible Time, ET) 파라미터를 통해 비작업 보존(Non-Work Conserving) 메커니즘을 도입한다.

1. 메타데이터 전파:
   • 종료 시간 (Finish Time, FT): 진입 노드에서 계산되어 코어 노드에서 업데이트되며, 이상적인 서비스 완료 시간을 나타낸다.
   • 적격 시간 (Eligible Time, ET): 진입 노드에서 계산되어 코어 노드에서 업데이트되는 새로운 파라미터이다. 이는 패킷이 서비스를 시작할 수 있는 가장 빠른 시간을 정의한다.
2. 스케줄링 로직:
   • 큐 내의 패킷들은 FT를 기준으로 (오름차순으로) 정렬된다.
   • 비작업 보존 제약: 패킷은 현재 시간이 해당 패킷의 ET보다 크거나 같을 때만 서비스될 수 있다. 링크가 유휴 상태이더라도, ET 이전에 도착한 패킷은 대기해야 한다.
   • 이러한 강제된 대기 기간은 작업 보존형 시스템에서 지터를 유발하는 링크 활용의 "버스트성(burstiness)"을 방지한다.
3. 수학적 공식화:
   • 노드 $h$에서의 FT는 $F_h(p) = F_{h-1}(p) + d_{h-1}(p)$로 업데이트되며, 이는 C-SCORE와 동일하다.
   • ET는 $E_h(p) = E_{h-1}(p) + d_{h-1}(p)$로 업데이트된다. 여기서 $d$는 노드 지연 요소 및 전파/클록 차이를 포함한다.
   • 서비스 구간은 $(E_h(p), F_h(p)]$로 정의된다. 저자들은 동일한 플로의 연속된 패킷들에 대해 이 구간들이 서로 겹치지 않음을 증명한다.

이론적 도출

본 논문은 다음 경계치에 대한 엄밀한 수학적 증명을 제공한다:

• E2E 지연 시간 상한 (Upper Bound): 상태 유지형 공정 큐잉(PGPS) 및 C-SCORE와 동일함을 증명되었다. 이 경계치는 네트워크 활용도와 무관하며, 플로우 고유 파라미터(버스트 크기, 패킷 길이, 서비스율) 및 노드 지연 요소의 함수이다.
• E2E 지연 시간 하한 (Lower Bound): ET 제약을 기반으로 도출되었으며, 패킷이 경험해야 하는 최소 지연 시간을 설정한다.
• 지터 경계치 (Jitter Bound): 지연 시간 상한과 하한의 차이로 정의된다. 분석 결과, N-SCORE는 비작업 보존 동작에 의해 하한이 높아짐으로써 작업 보존형 방식에 비해 지터를 크게 감소시킨다.
• 버퍼 점유 (Buffer Occupancy): 노드당 버퍼 요구량은 약 $3NL$ (여기서 $N$은 플로우 수, $L$은 최대 패킷 크기)로 제한된다. 이 완만한 요구량은 겹치지 않는 서비스 구간으로부터 도출된다.

주요 기여

1. N-SCORE 제안: 코어 노드에서 개별 플로우 상태를 유지할 필요 없이 대규모 네트워크에서 결정적 지터 보장을 달성하는 새로운 스케줄러를 제안하였다.
2. 최적성 이론적 증명: N-SCORE가 상태 유지형 공정 큐잉의 최적 E2E 지연 시간 상한을 보존하면서도 우수한 지터 억제를 제공한다는 엄밀한 증명을 제공하였다.
3. 버퍼 복잡도 분석: 노드의 버퍼 요구량을 특성화하여 $\approx 3NL$의 상한을 설정함으로써, 다른 문맥의 PIFO(Push-In First-Out) 큐잉에 비해 구현 복잡도를 완화하였다.
4. 표준화 맥락: 본 연구는 IETF DetNet WG의 워킹 그룹 드래프트로 채택되었음을 명시하였다.

결과

저자들은 SimPy 프레임워크를 사용하여 부분 메시 네트워크 토폴로지(7 홉, 1 Gbps 링크)에서 광범 Expansive한 시뮬레이션을 통해 N-SCORE를 검증하였다. 연구에서는 차량 내 네트워크의 전형적인 세 가지 플로우 유형(Audio, Video, Command & Control)에 대해 N-SCORE를 CQF, ECQF, ATS with ECQF, CJVC, C-SCORE와 비교하였다.

• 지연 시간 성능:
  • N-SCORE는 C-SCORE 및 CJVC와 동일한 E2E 지연 시간 경계치를 달성하였다.
  • CQF를 제외한 모든 스케줄러가 높은 활용도(93.6%) 하에서도 Video 플로우의 10 ms 마감 기한을 충족하였다.
  • C-SCORE는 가장 낮은 절대 지연 시간을 기록하였으나(작업 보존형이므로), N-SCORE는 동일한 이론적 상한을 유지하였다.
• 지터 성능:
  • Audio 및 Command & Control 플로우의 경우, N-SCORE와 CJVC는 CQF 기반 스케줄러보다 훨씬 뛰어난 가장 낮은 지터 수준을 보여주었다.
  • Video 플로우의 경우, N-SCORE를 포함한 모든 스케줄러(CJVC, CQF, ECQF 포함)가 약 8 ms의 유사한 지터 수준을 보였다. 이는 마감 기한을 충족하기 위해 적용된 Video 플로우의 셰이핑 지연이 해당 플로우 유형의 지터 특성을 지배했기 때문이다.
  • C-SCORE는 작업 보존형 특성으로 인해 Audio 및 Command & Control 플로우에서 N-SCORE 및 CJVC보다 높은 지터를 보였으며, 이는 링크 효율성과 지터 제어 사이의 트레이드오프를 확인시켜 준다.
• 버퍼 점유:
  • 93.6% 활용도 하에서의 시뮬레이션 결과, 모든 노드에서 관찰된 최대 버퍼 점유량은 논문에서 도출된 이론적 상한보다 지속적으로 낮게 유지됨을 확인하였다.

의의

본 논문은 N-SCORE를 결정적 네트워킹을 위한 핵심적인 발전으로 자리매김한다. N-SCORE의 주요 의의는 확장성과 결정적 지터 사이의 오랜 트레이드오프를 해결했다는 점에 있다.

• 코어 노드가 플로우 상태를 유지할 필요를 제거함으로써, N-SCORE는 상태 유지형 방식이 계산적으로 불가능한 대규모 네트워크에서 공정 큐잉 원칙을 배포할 수 있게 한다.
• 적격 시간(ET)을 통한 비작업 보존 메커니즘을 도입함으로써, N-SCORE는 CJVC의 높은 메타데이터나 계산 오버헤드 없이 C-SCORE의 근본적인 한계(지터 보장 부재)를 극복한다.
• 저자들은 N-SCORE가 상태 유지형 공정 큐잉의 최적 지연 시간 경계와 비작업 보존형 시스템의 지터 억제라는 "두 마리 토끼"를 모두 잡으면서도, 하드웨어 구현에 관리가 가능한 버퍼 풋프린트를 유지하는 실용적인 경로를 제공한다고 결론짓는다.

논문은 N-SCORE가 지터를 크게 개선하지만, 단일 플로우로부터 발생하는 큰 버스트는 여전히 버스트 내 첫 패킷과 마지막 패킷 간의 E2E 지연 차이로 인해 지터를 유발할 수 있다고 언급하였다. 저자들은 이러한 효과를 더욱 완화하기 위해 버스트를 단일 엔티티(예: "flowlet")로 취급하는 후속 연구를 제안하였다.