802.1Qbv 네트워크 대역폭 활용 및 게이트 제어 목록 구성 최적화 (논문 번역)

페이지 1: 제목, 초록, 서론

제목

802.1Qbv 네트워크에서 대역폭 활용 및 게이트 제어 목록 구성 최적화

저자 및 소속

ANNA ARESTOVA, KAI-STEFFEN J. HIELSCHER, AND REINHARD GERMAN
독일 에를랑겐-뉘른베르크 프리드리히-알렉산더 대학교 컴퓨터 과학 7, 컴퓨터 네트워크 및 통신 시스템

초록 (ABSTRACT)

IEEE 802.1 TSN(Time-Sensitive Networking) 태스크 그룹은 2012년부터 IEEE 802 네트워크를 통해 결정론적이고 시간 민감성 서비스를 제공하기 위한 다양한 표준을 개발해왔습니다. TAS(Time-Aware Shaper)는 시간 민감성 네트워크 트래픽의 정밀한 전달 및 형성을 가능하게 하는 TSN의 핵심 요소입니다. TAS 기반 네트워크에서 스트림의 종단 간 전송 시간을 최적화하는 스케줄링 알고리즘들이 다수 제시되었지만, 대부분의 기존 연구는 중요 네트워크 트래픽 스케줄링이 하드웨어에서 제한된 슬롯 수와 다른 트래픽 클래스의 대역폭 활용에 미치는 영향을 다루지 않습니다. 본 논문에서는 휴리스틱 및 메타-휴리스틱 알고리즘을 사용하여 네트워크 자원 활용도를 분석하고, 압축 알고리즘을 통해 TAS 구성을 개선하는 방법을 제안합니다.

I. 서론 (INTRODUCTION)

TSN의 도입으로 실시간 시스템에서 이더넷 기술을 사용할 수 있게 되었습니다. 이는 중요 트래픽과 비중요 트래픽이 동일 네트워크에 공존할 수 있게 하고, 공급업체 종속성을 피하며 상호운용성을 확보할 수 있어 매력적입니다. 특히 시간 민감성 트래픽(TSN 스트림)과 관련하여 QoS(서비스 품질), 낮은 지연 시간 및 지터 보장 메커니즘을 제공합니다. TAS는 트래픽 클래스에 타임 슬롯을 할당하는 원리로 작동하며, 이는 표준 자체에서 지원되지 않는 적절한 구성을 필요로 합니다. 부적절한 구성은 지연, 지터, 대역폭 활용도를 악화시키고, 안전이 중요한 애플리케이션에서는 심각한 결과를 초래할 수 있습니다.

페이지 1 핵심 요약

문제 제기: 기존 TSN 스케줄링 연구는 하드웨어의 슬롯 수 제한이나 대역폭 낭비 문제를 충분히 고려하지 않았습니다.
목표: 대역폭 활용도를 높이고 게이트 제어 목록(GCL) 구성을 최적화하는 새로운 스케줄링 알고리즘을 제안하고 평가합니다.
의의: 자율 주행 등 안전이 중요한 시스템에서 네트워크 자원을 효율적으로 사용하는 기반을 마련합니다.

페이지 2: 기본 개념 (Fundamentals)

A. TIME-AWARE SHAPER (TAS)

TSN은 시간, 신뢰성, 자원 관리 동기화 메커니즘 외에도 지연 시간을 보장하기 위해 TAS를 포함한 여러 셰이퍼와 스케줄러를 제공합니다. TAS의 핵심 기능은 네트워크 트래픽을 여러 클래스로 분류하는 것입니다. VLAN 태그의 PCP(Priority Code Point) 값을 기반으로 0-7까지의 8개 트래픽 클래스로 나뉩니다.

TAS는 TDMA(시분할 다중 접속) 원리에 따라 작동하며, 시간을 여러 슬롯으로 나누어 하나 이상의 트래픽 클래스에 예약할 수 있습니다. 이 타임 슬롯 스케줄은 GCL(Gate Control List)로 표현됩니다. 각 물리적 포트의 송신 큐마다 '게이트(gate)'가 있으며, 일반적으로 8개의 송신 큐가 있습니다. GCL 항목에서 활성화된 게이트는 트래픽을 통과시키고, 비활성화된 게이트는 막습니다. 여러 게이트가 동시에 활성화되면, 엄격한 우선순위 스케줄링(SP)에 따라 가장 높은 우선순위 큐부터 처리됩니다.

또한, 비중요 트래픽이 중요 타임 슬롯을 침범하는 것을 막기 위해 '가드 밴드(guard band)'가 사용됩니다. 가드 밴드가 활성화된 간격 동안에는 전송 준비가 된 패킷이 보류되어, 중요 슬롯을 침범하지 않도록 합니다.

페이지 2 핵심 요약

TAS 작동 원리: TDMA 방식을 사용해 트래픽 클래스별로 전송 시간을 예약합니다.
GCL (Gate Control List): 각 포트의 8개 큐(트래픽 등급)에 대한 게이트(열림/닫힘) 상태와 시간을 정의한 목록입니다.
가드 밴드: 중요 트래픽 슬롯의 시작 직전에 비중요 트래픽의 전송을 막아 슬롯을 보호하는 시간 간격입니다.
문제점: 이 메커니즘은 구성이 복잡하며, 잘못 구성하면 대역폭이 낭비될 수 있습니다.

페이지 3: 유전 알고리즘 (Genetic Algorithms)

B. 유전 알고리즘

본 논문에서 고려하는 일부 알고리즘은 유전 알고리즘(GA)을 사용하므로, 이 섹션에서 소개합니다. GA는 자연 선택과 유전학을 포함하는 생물학적 진화 과정에서 영감을 받은 무작위 탐색 기법으로, 다음 단계로 구성됩니다.

초기화: 개체(individual)들의 초기 집단(population)을 생성합니다. 각 개체는 문제에 대한 하나의 해(solution)를 나타내며, 인코딩된 염색체(chromosome)로 구성됩니다.
적합도 평가: 각 개체는 적합도 함수를 통해 해의 품질을 나타내는 적합도 값을 할당받습니다.
선택: 다음 세대로 살아남을 개체들이 선택됩니다. 적합도가 높은 개체가 선택될 확률이 높습니다.
재생산 (교차 및 돌연변이): 선택된 개체들은 교차(crossover) 및 돌연변이(mutation) 연산을 통해 새로운 자손(offspring)을 생성합니다.
대체: 생성된 자손이 기존 집단의 일부를 대체하며, 집단 크기는 유지됩니다. (엘리트주의 접근법)
반복 또는 종료: 종료 조건(예: 세대 수, 실행 시간)이 충족될 때까지 1-5 단계를 반복합니다.

TSN 스트림 스케줄링 문제는 순열 문제로 매핑될 수 있습니다. 각 염색체는 스케줄링할 모든 스트림의 순서를 인코딩하며, 각 유전자(gene)는 스트림의 고유 식별자를 포함합니다 (그림 2 참조). 본 논문에서는 PBX(Position-based Crossover)와 Swap 돌연변이 연산자가 가장 적합하다는 것을 발견했습니다.

페이지 3 핵심 요약

유전 알고리즘(GA): 최적의 스트림 전송 순서를 찾기 위해 사용되는 메타-휴리스틱 기법입니다.
염색체와 유전자: 염색체는 전체 스트림의 전송 순서(하나의 해)를, 유전자는 개별 스트림을 나타냅니다.
프로세스: '선택, 교차, 돌연변이' 과정을 반복하여 더 나은 해(최적의 스케줄)를 찾아갑니다.
적용: 이 논문에서는 스케줄링 순서 최적화를 위해 GA를 활용합니다.

페이지 4: 관련 연구 및 시스템 모델

III. 관련 연구 (RELATED WORK)

본 연구에서는 TSN 스트림 스케줄링 알고리즘과 TAS 구성 방법을 함께 제시하며 네트워크 자원 사용량을 심층적으로 평가합니다. 기존 연구들은 대부분 종단 간 스트림 지연 시간을 준수하는 데 초점을 맞추고, GCL 구성이나 자원 활용 문제는 간과했습니다. Craciunas 등의 연구[14]는 SMT(Satisfiability Modulo Theories)를 사용하여 대규모 TSN 스트림을 스케줄링했지만, 런타임 성능 외 성공률이나 지연 시간 데이터는 제공하지 않았습니다. Dürr와 Nayak[5]는 Tabu 탐색 알고리즘과 'no-wait' 원칙을 사용하고 스케줄 압축을 수행했지만, 우리는 이들의 연구보다 더 나은 런타임 성능을 보이며 다양한 주기 유형을 허용합니다.

IV. 시스템 모델 (SYSTEM MODEL)

네트워크는 양방향 그래프 G(N, L)로 모델링됩니다. N은 네트워크 노드 집합, L은 노드 간 링크 집합입니다. 스케줄링할 스트림은 집합 S로 표시되며, 각 스트림 sk는 (주기 pk, 오프셋 øk, 마감 시간 dk, 크기 lk, 경로 ptk)의 튜플로 정의됩니다. 그림 4는 스트림 S1의 특성과 지연 요소를 보여줍니다.

페이지 4 핵심 요약

관련 연구와의 차별점: 기존 연구들이 스케줄링 성공 여부에만 집중한 반면, 본 연구는 GCL 구성, 대역폭 낭비, 자원 활용도까지 종합적으로 고려하여 더 실용적인 접근법을 제시합니다.
시스템 모델링: 네트워크를 그래프로, 데이터 흐름(스트림)을 주기, 크기, 경로 등을 포함하는 튜플로 수학적으로 정의하여 분석의 기반을 마련합니다.

페이지 5: TAS 스케줄링 알고리즘

V. TAS를 위한 스케줄링 알고리즘

이 섹션에서는 TAS 지원 네트워크를 위한 스케줄링 알고리즘의 분류를 제시합니다. 주된 목표는 스트림의 종단 간 마감 시간을 준수하고, 스케줄의 유효 길이인 '메이크스팬(makespan)'을 최소화하는 것입니다. 우리는 입력 데이터 속성, 순서 지정, 스케줄링 절차, GCL 구성을 고려한 알고리즘 변형을 제안합니다.

A. 스케줄링 알고리즘 클래스

그림 6에서 볼 수 있듯이, TAS 알고리즘의 계층적 분류를 식별했습니다. 최상위 레벨에서는 스트림 주기가 서로 배수 관계인 '조화(harmonic)' 주기와 그렇지 않은 '비조화(non-harmonic)' 주기로 나뉩니다. 이는 스케줄 품질과 네트워크 자원 활용에 영향을 미칩니다. 조화 주기는 산업용 실시간 시스템의 특징이며, 비조화 주기는 자동차 시스템에서 중요합니다.

페이지 5 핵심 요약

알고리즘 목표: 1) 모든 스트림의 마감 시간 준수. 2) 전체 스케줄 길이(makespan) 최소화. 3) 대역폭 및 GCL 구성 효율성 극대화.
알고리즘 분류: 스트림 주기 특성에 따라 '조화 주기'와 '비조화 주기' 알고리즘으로 크게 나눕니다. 이 분류는 GCL 구성 방식과 자원 활용 전략에 직접적인 영향을 줍니다.

페이지 6: 알고리즘 분류 상세

알고리즘 분류 (그림 6)

모든 스케줄링 알고리즘은 모든 스트림 주기의 최소공배수인 '초주기(hyperperiod)' 길이의 스케줄을 생성합니다. GCL 주기는 초주기와 같게 설정하거나, 조화 주기의 경우 최대공약수(GCD)로 축소할 수 있습니다. GCD로 GCL 주기를 줄이면 중요한 트래픽에 필요한 GCL 항목 수를 줄일 수 있습니다.

GCD 방식: GCL 주기를 스트림 주기들의 GCD로 설정합니다. 스트림은 GCD 세그먼트 경계를 넘어 계획되지 않습니다.
HYPO (Hyperperiod) 방식: GCL 주기를 초주기로 설정합니다. 스트림이 GCD 경계를 넘어 배치될 수 있습니다 (그림 7b).
정렬(Sorted) vs. 무작위(Random): 스트림을 처리하는 순서를 주기가 짧은 순서로 정렬할지, 무작위로 할지 결정합니다.
교대(Alternated) 방식: 부하 분산을 위해, 점유율이 가장 낮은 GCD 세그먼트에 스트림을 먼저 할당하는 최적화 방식입니다.

페이지 6 핵심 요약

GCL 주기 설정: 알고리즘은 GCL 주기를 스트림 주기의 '최대공약수(GCD)'로 할지, '초주기(HYPO)'로 할지에 따라 나뉩니다. GCD 방식은 GCL 항목 수를 줄여 메모리를 절약하지만 유연성이 떨어지고, HYPO 방식은 유연하지만 GCL 항목 수가 많아집니다.
최적화 전략: 스트림 처리 순서를 '정렬'하거나, 부하를 분산시키는 '교대' 방식을 추가하여 스케줄링 효율을 높이는 다양한 변형을 탐구합니다.

페이지 14: 토론 및 결론

D. 토론 (DISCUSSION)

본 연구에서는 이상적인 클럭을 가정했지만, 실제 환경에서는 장치 간 클럭 편이가 발생합니다. IEEE 802.1AS-2020 표준은 1µs 이내의 클럭 편차를 보장하므로, 이 편차를 시스템 모델에 통합하여 실제 적용 가능성을 확보할 수 있습니다. 또한, 장치의 시간 정밀도, 유니캐스트 외 멀티캐스트 전송 모드 등도 향후 연구에서 고려될 수 있습니다. 분석은 중요 슬롯 내의 대역폭 낭비에 초점을 맞추었으나, 실제로는 비중요 트래픽 클래스에 할당된 가드 밴드로 인해 추가적인 대역폭 낭비가 발생할 수 있습니다.

VII. 결론 (CONCLUSION)

본 논문에서는 'no-wait' 접근 방식으로 중요 TSN 스트림을 스케줄링하는 휴리스틱 및 메타-휴리스틱 알고리즘 집합을 제시했습니다. 이 알고리즘들은 입력 데이터 순서, 스케줄링 절차, GCL 구성에 다양한 수정을 적용하여 필요한 GCL 슬롯 수와 대역폭 활용에 미치는 영향을 분석했습니다.

주요 발견:

조화 주기(Harmonic): '교대(alternating)' 접근법이 적은 GCL 항목과 낮은 대역폭 낭비를 보였습니다. 런타임이 중요하지 않다면 GA를 결합하는 것이 최상의 결과를 냈습니다.
GCD 기반 알고리즘: GCL 항목 수를 줄이는 데 효과적입니다.
HYPO 기반 알고리즘: 대역폭 낭비 측면에서 우수하지만, 대규모 네트워크에서는 GCL 항목 수가 많아질 수 있습니다.
비조화 주기(Non-harmonic): 대규모 네트워크에서 성공률이 낮았으며, GA를 추가하면 성공률이 향상되었습니다.

결론적으로, 스케줄링 알고리즘의 세부적인 수정은 특히 조화 주기 알고리즘 클래스에서 네트워크 자원 사용량에 큰 영향을 미친다는 것을 보여주었습니다.

페이지 14 핵심 요약

최종 결론: 어떤 스케줄링 전략을 선택하는지가 네트워크 자원 효율성(GCL 항목 수, 대역폭 낭비)에 지대한 영향을 미칩니다.
상황별 최적 전략: - 메모리(GCL) 절약이 중요하면 GCD 기반 접근법이 유리합니다. - 대역폭 효율이 중요하면 HYPO 기반 접근법이 낫습니다. - 조화 주기 환경에서는 '교대(Alternating)' 전략이 전반적으로 우수합니다. - 복잡한 문제에서는 시간이 더 걸리더라도 유전 알고리즘(GA)을 사용하는 것이 좋은 해답을 줍니다.